llvm/lib/CodeGen/MachineBasicBlock.cpp

   1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Collect the sequence of machine instructions for a basic block.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/CodeGen/MachineBasicBlock.h"
  14 #include "llvm/ADT/STLExtras.h"
  15 #include "llvm/ADT/StringExtras.h"
  16 #include "llvm/CodeGen/LiveIntervals.h"
  17 #include "llvm/CodeGen/LivePhysRegs.h"
  18 #include "llvm/CodeGen/LiveVariables.h"
  19 #include "llvm/CodeGen/MachineDominators.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  23 #include "llvm/CodeGen/MachineLoopInfo.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/SlotIndexes.h"
  26 #include "llvm/CodeGen/TargetInstrInfo.h"
  27 #include "llvm/CodeGen/TargetLowering.h"
  28 #include "llvm/CodeGen/TargetRegisterInfo.h"
  29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  30 #include "llvm/Config/llvm-config.h"
  31 #include "llvm/IR/BasicBlock.h"
  32 #include "llvm/IR/DebugInfoMetadata.h"
  33 #include "llvm/IR/ModuleSlotTracker.h"
  34 #include "llvm/MC/MCAsmInfo.h"
  35 #include "llvm/MC/MCContext.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include "llvm/Target/TargetMachine.h"
  39 #include <algorithm>
  40 #include <cmath>
  41 using namespace llvm;
  42
  43 #define DEBUG_TYPE "codegen"
  44
  45 static cl::opt<bool> PrintSlotIndexes(
  46     "print-slotindexes",
  47     cl::desc("When printing machine IR, annotate instructions and blocks with "
  48              "SlotIndexes when available"),
  49     cl::init(true), cl::Hidden);
  50
  51 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
  52     : BB(B), Number(-1), xParent(&MF) {
  53   Insts.Parent = this;
  54   if (B)
  55     IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
  56 }
  57
  58 MachineBasicBlock::~MachineBasicBlock() = default;
  59
  60 /// Return the MCSymbol for this basic block.
  61 MCSymbol *MachineBasicBlock::getSymbol() const {
  62   if (!CachedMCSymbol) {
  63     const MachineFunction *MF = getParent();
  64     MCContext &Ctx = MF->getContext();
  65
  66     // We emit a non-temporary symbol -- with a descriptive name -- if it begins
  67     // a section (with basic block sections). Otherwise we fall back to use temp
  68     // label.
  69     if (MF->hasBBSections() && isBeginSection()) {
  70       SmallString<5> Suffix;
  71       if (SectionID == MBBSectionID::ColdSectionID) {
  72         Suffix += ".cold";
  73       } else if (SectionID == MBBSectionID::ExceptionSectionID) {
  74         Suffix += ".eh";
  75       } else {
  76         // For symbols that represent basic block sections, we add ".__part." to
  77         // allow tools like symbolizers to know that this represents a part of
  78         // the original function.
  79         Suffix = (Suffix + Twine(".__part.") + Twine(SectionID.Number)).str();
  80       }
  81       CachedMCSymbol = Ctx.getOrCreateSymbol(MF->getName() + Suffix);
  82     } else {
  83       const StringRef Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
  84       CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
  85                                              Twine(MF->getFunctionNumber()) +
  86                                              "_" + Twine(getNumber()));
  87     }
  88   }
  89   return CachedMCSymbol;
  90 }
  91
  92 MCSymbol *MachineBasicBlock::getEHCatchretSymbol() const {
  93   if (!CachedEHCatchretMCSymbol) {
  94     const MachineFunction *MF = getParent();
  95     SmallString<128> SymbolName;
  96     raw_svector_ostream(SymbolName)
  97         << "$ehgcr_" << MF->getFunctionNumber() << '_' << getNumber();
  98     CachedEHCatchretMCSymbol = MF->getContext().getOrCreateSymbol(SymbolName);
  99   }
 100   return CachedEHCatchretMCSymbol;
 101 }
 102
 103 MCSymbol *MachineBasicBlock::getEndSymbol() const {
 104   if (!CachedEndMCSymbol) {
 105     const MachineFunction *MF = getParent();
 106     MCContext &Ctx = MF->getContext();
 107     auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
 108     CachedEndMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB_END" +
 109                                               Twine(MF->getFunctionNumber()) +
 110                                               "_" + Twine(getNumber()));
 111   }
 112   return CachedEndMCSymbol;
 113 }
 114
 115 raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
 116   MBB.print(OS);
 117   return OS;
 118 }
 119
 120 Printable llvm::printMBBReference(const MachineBasicBlock &MBB) {
 121   return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
 122 }
 123
 124 /// When an MBB is added to an MF, we need to update the parent pointer of the
 125 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
 126 /// operand list for registers.
 127 ///
 128 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
 129 /// gets the next available unique MBB number. If it is removed from a
 130 /// MachineFunction, it goes back to being #-1.
 131 void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
 132     MachineBasicBlock *N) {
 133   MachineFunction &MF = *N->getParent();
 134   N->Number = MF.addToMBBNumbering(N);
 135
 136   // Make sure the instructions have their operands in the reginfo lists.
 137   MachineRegisterInfo &RegInfo = MF.getRegInfo();
 138   for (MachineInstr &MI : N->instrs())
 139     MI.addRegOperandsToUseLists(RegInfo);
 140 }
 141
 142 void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
 143     MachineBasicBlock *N) {
 144   N->getParent()->removeFromMBBNumbering(N->Number);
 145   N->Number = -1;
 146 }
 147
 148 /// When we add an instruction to a basic block list, we update its parent
 149 /// pointer and add its operands from reg use/def lists if appropriate.
 150 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
 151   assert(!N->getParent() && "machine instruction already in a basic block");
 152   N->setParent(Parent);
 153
 154   // Add the instruction's register operands to their corresponding
 155   // use/def lists.
 156   MachineFunction *MF = Parent->getParent();
 157   N->addRegOperandsToUseLists(MF->getRegInfo());
 158   MF->handleInsertion(*N);
 159 }
 160
 161 /// When we remove an instruction from a basic block list, we update its parent
 162 /// pointer and remove its operands from reg use/def lists if appropriate.
 163 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {
 164   assert(N->getParent() && "machine instruction not in a basic block");
 165
 166   // Remove from the use/def lists.
 167   if (MachineFunction *MF = N->getMF()) {
 168     MF->handleRemoval(*N);
 169     N->removeRegOperandsFromUseLists(MF->getRegInfo());
 170   }
 171
 172   N->setParent(nullptr);
 173 }
 174
 175 /// When moving a range of instructions from one MBB list to another, we need to
 176 /// update the parent pointers and the use/def lists.
 177 void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList,
 178                                                        instr_iterator First,
 179                                                        instr_iterator Last) {
 180   assert(Parent->getParent() == FromList.Parent->getParent() &&
 181          "cannot transfer MachineInstrs between MachineFunctions");
 182
 183   // If it's within the same BB, there's nothing to do.
 184   if (this == &FromList)
 185     return;
 186
 187   assert(Parent != FromList.Parent && "Two lists have the same parent?");
 188
 189   // If splicing between two blocks within the same function, just update the
 190   // parent pointers.
 191   for (; First != Last; ++First)
 192     First->setParent(Parent);
 193 }
 194
 195 void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
 196   assert(!MI->getParent() && "MI is still in a block!");
 197   Parent->getParent()->deleteMachineInstr(MI);
 198 }
 199
 200 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
 201   instr_iterator I = instr_begin(), E = instr_end();
 202   while (I != E && I->isPHI())
 203     ++I;
 204   assert((I == E || !I->isInsideBundle()) &&
 205          "First non-phi MI cannot be inside a bundle!");
 206   return I;
 207 }
 208
 209 MachineBasicBlock::iterator
 210 MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
 211   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 212
 213   iterator E = end();
 214   while (I != E && (I->isPHI() || I->isPosition() ||
 215                     TII->isBasicBlockPrologue(*I)))
 216     ++I;
 217   // FIXME: This needs to change if we wish to bundle labels
 218   // inside the bundle.
 219   assert((I == E || !I->isInsideBundle()) &&
 220          "First non-phi / non-label instruction is inside a bundle!");
 221   return I;
 222 }
 223
 224 MachineBasicBlock::iterator
 225 MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I,
 226                                           Register Reg, bool SkipPseudoOp) {
 227   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 228
 229   iterator E = end();
 230   while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
 231                     (SkipPseudoOp && I->isPseudoProbe()) ||
 232                     TII->isBasicBlockPrologue(*I, Reg)))
 233     ++I;
 234   // FIXME: This needs to change if we wish to bundle labels / dbg_values
 235   // inside the bundle.
 236   assert((I == E || !I->isInsideBundle()) &&
 237          "First non-phi / non-label / non-debug "
 238          "instruction is inside a bundle!");
 239   return I;
 240 }
 241
 242 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
 243   iterator B = begin(), E = end(), I = E;
 244   while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
 245     ; /*noop */
 246   while (I != E && !I->isTerminator())
 247     ++I;
 248   return I;
 249 }
 250
 251 MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
 252   instr_iterator B = instr_begin(), E = instr_end(), I = E;
 253   while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
 254     ; /*noop */
 255   while (I != E && !I->isTerminator())
 256     ++I;
 257   return I;
 258 }
 259
 260 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminatorForward() {
 261   return find_if(instrs(), [](auto &II) { return II.isTerminator(); });
 262 }
 263
 264 MachineBasicBlock::iterator
 265 MachineBasicBlock::getFirstNonDebugInstr(bool SkipPseudoOp) {
 266   // Skip over begin-of-block dbg_value instructions.
 267   return skipDebugInstructionsForward(begin(), end(), SkipPseudoOp);
 268 }
 269
 270 MachineBasicBlock::iterator
 271 MachineBasicBlock::getLastNonDebugInstr(bool SkipPseudoOp) {
 272   // Skip over end-of-block dbg_value instructions.
 273   instr_iterator B = instr_begin(), I = instr_end();
 274   while (I != B) {
 275     --I;
 276     // Return instruction that starts a bundle.
 277     if (I->isDebugInstr() || I->isInsideBundle())
 278       continue;
 279     if (SkipPseudoOp && I->isPseudoProbe())
 280       continue;
 281     return I;
 282   }
 283   // The block is all debug values.
 284   return end();
 285 }
 286
 287 bool MachineBasicBlock::hasEHPadSuccessor() const {
 288   for (const MachineBasicBlock *Succ : successors())
 289     if (Succ->isEHPad())
 290       return true;
 291   return false;
 292 }
 293
 294 bool MachineBasicBlock::isEntryBlock() const {
 295   return getParent()->begin() == getIterator();
 296 }
 297
 298 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 299 LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
 300   print(dbgs());
 301 }
 302 #endif
 303
 304 bool MachineBasicBlock::mayHaveInlineAsmBr() const {
 305   for (const MachineBasicBlock *Succ : successors()) {
 306     if (Succ->isInlineAsmBrIndirectTarget())
 307       return true;
 308   }
 309   return false;
 310 }
 311
 312 bool MachineBasicBlock::isLegalToHoistInto() const {
 313   if (isReturnBlock() || hasEHPadSuccessor() || mayHaveInlineAsmBr())
 314     return false;
 315   return true;
 316 }
 317
 318 StringRef MachineBasicBlock::getName() const {
 319   if (const BasicBlock *LBB = getBasicBlock())
 320     return LBB->getName();
 321   else
 322     return StringRef("", 0);
 323 }
 324
 325 /// Return a hopefully unique identifier for this block.
 326 std::string MachineBasicBlock::getFullName() const {
 327   std::string Name;
 328   if (getParent())
 329     Name = (getParent()->getName() + ":").str();
 330   if (getBasicBlock())
 331     Name += getBasicBlock()->getName();
 332   else
 333     Name += ("BB" + Twine(getNumber())).str();
 334   return Name;
 335 }
 336
 337 void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes,
 338                               bool IsStandalone) const {
 339   const MachineFunction *MF = getParent();
 340   if (!MF) {
 341     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
 342        << " is null\n";
 343     return;
 344   }
 345   const Function &F = MF->getFunction();
 346   const Module *M = F.getParent();
 347   ModuleSlotTracker MST(M);
 348   MST.incorporateFunction(F);
 349   print(OS, MST, Indexes, IsStandalone);
 350 }
 351
 352 void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
 353                               const SlotIndexes *Indexes,
 354                               bool IsStandalone) const {
 355   const MachineFunction *MF = getParent();
 356   if (!MF) {
 357     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
 358        << " is null\n";
 359     return;
 360   }
 361
 362   if (Indexes && PrintSlotIndexes)
 363     OS << Indexes->getMBBStartIdx(this) << '\t';
 364
 365   printName(OS, PrintNameIr | PrintNameAttributes, &MST);
 366   OS << ":\n";
 367
 368   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
 369   const MachineRegisterInfo &MRI = MF->getRegInfo();
 370   const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
 371   bool HasLineAttributes = false;
 372
 373   // Print the preds of this block according to the CFG.
 374   if (!pred_empty() && IsStandalone) {
 375     if (Indexes) OS << '\t';
 376     // Don't indent(2), align with previous line attributes.
 377     OS << "; predecessors: ";
 378     ListSeparator LS;
 379     for (auto *Pred : predecessors())
 380       OS << LS << printMBBReference(*Pred);
 381     OS << '\n';
 382     HasLineAttributes = true;
 383   }
 384
 385   if (!succ_empty()) {
 386     if (Indexes) OS << '\t';
 387     // Print the successors
 388     OS.indent(2) << "successors: ";
 389     ListSeparator LS;
 390     for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
 391       OS << LS << printMBBReference(**I);
 392       if (!Probs.empty())
 393         OS << '('
 394            << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
 395            << ')';
 396     }
 397     if (!Probs.empty() && IsStandalone) {
 398       // Print human readable probabilities as comments.
 399       OS << "; ";
 400       ListSeparator LS;
 401       for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
 402         const BranchProbability &BP = getSuccProbability(I);
 403         OS << LS << printMBBReference(**I) << '('
 404            << format("%.2f%%",
 405                      rint(((double)BP.getNumerator() / BP.getDenominator()) *
 406                           100.0 * 100.0) /
 407                          100.0)
 408            << ')';
 409       }
 410     }
 411
 412     OS << '\n';
 413     HasLineAttributes = true;
 414   }
 415
 416   if (!livein_empty() && MRI.tracksLiveness()) {
 417     if (Indexes) OS << '\t';
 418     OS.indent(2) << "liveins: ";
 419
 420     ListSeparator LS;
 421     for (const auto &LI : liveins()) {
 422       OS << LS << printReg(LI.PhysReg, TRI);
 423       if (!LI.LaneMask.all())
 424         OS << ":0x" << PrintLaneMask(LI.LaneMask);
 425     }
 426     HasLineAttributes = true;
 427   }
 428
 429   if (HasLineAttributes)
 430     OS << '\n';
 431
 432   bool IsInBundle = false;
 433   for (const MachineInstr &MI : instrs()) {
 434     if (Indexes && PrintSlotIndexes) {
 435       if (Indexes->hasIndex(MI))
 436         OS << Indexes->getInstructionIndex(MI);
 437       OS << '\t';
 438     }
 439
 440     if (IsInBundle && !MI.isInsideBundle()) {
 441       OS.indent(2) << "}\n";
 442       IsInBundle = false;
 443     }
 444
 445     OS.indent(IsInBundle ? 4 : 2);
 446     MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
 447              /*AddNewLine=*/false, &TII);
 448
 449     if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
 450       OS << " {";
 451       IsInBundle = true;
 452     }
 453     OS << '\n';
 454   }
 455
 456   if (IsInBundle)
 457     OS.indent(2) << "}\n";
 458
 459   if (IrrLoopHeaderWeight && IsStandalone) {
 460     if (Indexes) OS << '\t';
 461     OS.indent(2) << "; Irreducible loop header weight: " << *IrrLoopHeaderWeight
 462                  << '\n';
 463   }
 464 }
 465
 466 /// Print the basic block's name as:
 467 ///
 468 ///    bb.{number}[.{ir-name}] [(attributes...)]
 469 ///
 470 /// The {ir-name} is only printed when the \ref PrintNameIr flag is passed
 471 /// (which is the default). If the IR block has no name, it is identified
 472 /// numerically using the attribute syntax as "(%ir-block.{ir-slot})".
 473 ///
 474 /// When the \ref PrintNameAttributes flag is passed, additional attributes
 475 /// of the block are printed when set.
 476 ///
 477 /// \param printNameFlags Combination of \ref PrintNameFlag flags indicating
 478 ///                       the parts to print.
 479 /// \param moduleSlotTracker Optional ModuleSlotTracker. This method will
 480 ///                          incorporate its own tracker when necessary to
 481 ///                          determine the block's IR name.
 482 void MachineBasicBlock::printName(raw_ostream &os, unsigned printNameFlags,
 483                                   ModuleSlotTracker *moduleSlotTracker) const {
 484   os << "bb." << getNumber();
 485   bool hasAttributes = false;
 486
 487   auto PrintBBRef = [&](const BasicBlock *bb) {
 488     os << "%ir-block.";
 489     if (bb->hasName()) {
 490       os << bb->getName();
 491     } else {
 492       int slot = -1;
 493
 494       if (moduleSlotTracker) {
 495         slot = moduleSlotTracker->getLocalSlot(bb);
 496       } else if (bb->getParent()) {
 497         ModuleSlotTracker tmpTracker(bb->getModule(), false);
 498         tmpTracker.incorporateFunction(*bb->getParent());
 499         slot = tmpTracker.getLocalSlot(bb);
 500       }
 501
 502       if (slot == -1)
 503         os << "<ir-block badref>";
 504       else
 505         os << slot;
 506     }
 507   };
 508
 509   if (printNameFlags & PrintNameIr) {
 510     if (const auto *bb = getBasicBlock()) {
 511       if (bb->hasName()) {
 512         os << '.' << bb->getName();
 513       } else {
 514         hasAttributes = true;
 515         os << " (";
 516         PrintBBRef(bb);
 517       }
 518     }
 519   }
 520
 521   if (printNameFlags & PrintNameAttributes) {
 522     if (isMachineBlockAddressTaken()) {
 523       os << (hasAttributes ? ", " : " (");
 524       os << "machine-block-address-taken";
 525       hasAttributes = true;
 526     }
 527     if (isIRBlockAddressTaken()) {
 528       os << (hasAttributes ? ", " : " (");
 529       os << "ir-block-address-taken ";
 530       PrintBBRef(getAddressTakenIRBlock());
 531       hasAttributes = true;
 532     }
 533     if (isEHPad()) {
 534       os << (hasAttributes ? ", " : " (");
 535       os << "landing-pad";
 536       hasAttributes = true;
 537     }
 538     if (isInlineAsmBrIndirectTarget()) {
 539       os << (hasAttributes ? ", " : " (");
 540       os << "inlineasm-br-indirect-target";
 541       hasAttributes = true;
 542     }
 543     if (isEHFuncletEntry()) {
 544       os << (hasAttributes ? ", " : " (");
 545       os << "ehfunclet-entry";
 546       hasAttributes = true;
 547     }
 548     if (getAlignment() != Align(1)) {
 549       os << (hasAttributes ? ", " : " (");
 550       os << "align " << getAlignment().value();
 551       hasAttributes = true;
 552     }
 553     if (getSectionID() != MBBSectionID(0)) {
 554       os << (hasAttributes ? ", " : " (");
 555       os << "bbsections ";
 556       switch (getSectionID().Type) {
 557       case MBBSectionID::SectionType::Exception:
 558         os << "Exception";
 559         break;
 560       case MBBSectionID::SectionType::Cold:
 561         os << "Cold";
 562         break;
 563       default:
 564         os << getSectionID().Number;
 565       }
 566       hasAttributes = true;
 567     }
 568     if (getBBID().has_value()) {
 569       os << (hasAttributes ? ", " : " (");
 570       os << "bb_id " << getBBID()->BaseID;
 571       if (getBBID()->CloneID != 0)
 572         os << " " << getBBID()->CloneID;
 573       hasAttributes = true;
 574     }
 575     if (CallFrameSize != 0) {
 576       os << (hasAttributes ? ", " : " (");
 577       os << "call-frame-size " << CallFrameSize;
 578       hasAttributes = true;
 579     }
 580   }
 581
 582   if (hasAttributes)
 583     os << ')';
 584 }
 585
 586 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
 587                                        bool /*PrintType*/) const {
 588   OS << '%';
 589   printName(OS, 0);
 590 }
 591
 592 void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
 593   LiveInVector::iterator I = find_if(
 594       LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
 595   if (I == LiveIns.end())
 596     return;
 597
 598   I->LaneMask &= ~LaneMask;
 599   if (I->LaneMask.none())
 600     LiveIns.erase(I);
 601 }
 602
 603 MachineBasicBlock::livein_iterator
 604 MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) {
 605   // Get non-const version of iterator.
 606   LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
 607   return LiveIns.erase(LI);
 608 }
 609
 610 bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
 611   livein_iterator I = find_if(
 612       LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
 613   return I != livein_end() && (I->LaneMask & LaneMask).any();
 614 }
 615
 616 void MachineBasicBlock::sortUniqueLiveIns() {
 617   llvm::sort(LiveIns,
 618              [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
 619                return LI0.PhysReg < LI1.PhysReg;
 620              });
 621   // Liveins are sorted by physreg now we can merge their lanemasks.
 622   LiveInVector::const_iterator I = LiveIns.begin();
 623   LiveInVector::const_iterator J;
 624   LiveInVector::iterator Out = LiveIns.begin();
 625   for (; I != LiveIns.end(); ++Out, I = J) {
 626     MCRegister PhysReg = I->PhysReg;
 627     LaneBitmask LaneMask = I->LaneMask;
 628     for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
 629       LaneMask |= J->LaneMask;
 630     Out->PhysReg = PhysReg;
 631     Out->LaneMask = LaneMask;
 632   }
 633   LiveIns.erase(Out, LiveIns.end());
 634 }
 635
 636 Register
 637 MachineBasicBlock::addLiveIn(MCRegister PhysReg, const TargetRegisterClass *RC) {
 638   assert(getParent() && "MBB must be inserted in function");
 639   assert(Register::isPhysicalRegister(PhysReg) && "Expected physreg");
 640   assert(RC && "Register class is required");
 641   assert((isEHPad() || this == &getParent()->front()) &&
 642          "Only the entry block and landing pads can have physreg live ins");
 643
 644   bool LiveIn = isLiveIn(PhysReg);
 645   iterator I = SkipPHIsAndLabels(begin()), E = end();
 646   MachineRegisterInfo &MRI = getParent()->getRegInfo();
 647   const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
 648
 649   // Look for an existing copy.
 650   if (LiveIn)
 651     for (;I != E && I->isCopy(); ++I)
 652       if (I->getOperand(1).getReg() == PhysReg) {
 653         Register VirtReg = I->getOperand(0).getReg();
 654         if (!MRI.constrainRegClass(VirtReg, RC))
 655           llvm_unreachable("Incompatible live-in register class.");
 656         return VirtReg;
 657       }
 658
 659   // No luck, create a virtual register.
 660   Register VirtReg = MRI.createVirtualRegister(RC);
 661   BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
 662     .addReg(PhysReg, RegState::Kill);
 663   if (!LiveIn)
 664     addLiveIn(PhysReg);
 665   return VirtReg;
 666 }
 667
 668 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
 669   getParent()->splice(NewAfter->getIterator(), getIterator());
 670 }
 671
 672 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
 673   getParent()->splice(++NewBefore->getIterator(), getIterator());
 674 }
 675
 676 static int findJumpTableIndex(const MachineBasicBlock &MBB) {
 677   MachineBasicBlock::const_iterator TerminatorI = MBB.getFirstTerminator();
 678   if (TerminatorI == MBB.end())
 679     return -1;
 680   const MachineInstr &Terminator = *TerminatorI;
 681   const TargetInstrInfo *TII = MBB.getParent()->getSubtarget().getInstrInfo();
 682   return TII->getJumpTableIndex(Terminator);
 683 }
 684
 685 void MachineBasicBlock::updateTerminator(
 686     MachineBasicBlock *PreviousLayoutSuccessor) {
 687   LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this)
 688                     << "\n");
 689
 690   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 691   // A block with no successors has no concerns with fall-through edges.
 692   if (this->succ_empty())
 693     return;
 694
 695   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 696   SmallVector<MachineOperand, 4> Cond;
 697   DebugLoc DL = findBranchDebugLoc();
 698   bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
 699   (void) B;
 700   assert(!B && "UpdateTerminators requires analyzable predecessors!");
 701   if (Cond.empty()) {
 702     if (TBB) {
 703       // The block has an unconditional branch. If its successor is now its
 704       // layout successor, delete the branch.
 705       if (isLayoutSuccessor(TBB))
 706         TII->removeBranch(*this);
 707     } else {
 708       // The block has an unconditional fallthrough, or the end of the block is
 709       // unreachable.
 710
 711       // Unfortunately, whether the end of the block is unreachable is not
 712       // immediately obvious; we must fall back to checking the successor list,
 713       // and assuming that if the passed in block is in the succesor list and
 714       // not an EHPad, it must be the intended target.
 715       if (!PreviousLayoutSuccessor || !isSuccessor(PreviousLayoutSuccessor) ||
 716           PreviousLayoutSuccessor->isEHPad())
 717         return;
 718
 719       // If the unconditional successor block is not the current layout
 720       // successor, insert a branch to jump to it.
 721       if (!isLayoutSuccessor(PreviousLayoutSuccessor))
 722         TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
 723     }
 724     return;
 725   }
 726
 727   if (FBB) {
 728     // The block has a non-fallthrough conditional branch. If one of its
 729     // successors is its layout successor, rewrite it to a fallthrough
 730     // conditional branch.
 731     if (isLayoutSuccessor(TBB)) {
 732       if (TII->reverseBranchCondition(Cond))
 733         return;
 734       TII->removeBranch(*this);
 735       TII->insertBranch(*this, FBB, nullptr, Cond, DL);
 736     } else if (isLayoutSuccessor(FBB)) {
 737       TII->removeBranch(*this);
 738       TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 739     }
 740     return;
 741   }
 742
 743   // We now know we're going to fallthrough to PreviousLayoutSuccessor.
 744   assert(PreviousLayoutSuccessor);
 745   assert(!PreviousLayoutSuccessor->isEHPad());
 746   assert(isSuccessor(PreviousLayoutSuccessor));
 747
 748   if (PreviousLayoutSuccessor == TBB) {
 749     // We had a fallthrough to the same basic block as the conditional jump
 750     // targets.  Remove the conditional jump, leaving an unconditional
 751     // fallthrough or an unconditional jump.
 752     TII->removeBranch(*this);
 753     if (!isLayoutSuccessor(TBB)) {
 754       Cond.clear();
 755       TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 756     }
 757     return;
 758   }
 759
 760   // The block has a fallthrough conditional branch.
 761   if (isLayoutSuccessor(TBB)) {
 762     if (TII->reverseBranchCondition(Cond)) {
 763       // We can't reverse the condition, add an unconditional branch.
 764       Cond.clear();
 765       TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
 766       return;
 767     }
 768     TII->removeBranch(*this);
 769     TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
 770   } else if (!isLayoutSuccessor(PreviousLayoutSuccessor)) {
 771     TII->removeBranch(*this);
 772     TII->insertBranch(*this, TBB, PreviousLayoutSuccessor, Cond, DL);
 773   }
 774 }
 775
 776 void MachineBasicBlock::validateSuccProbs() const {
 777 #ifndef NDEBUG
 778   int64_t Sum = 0;
 779   for (auto Prob : Probs)
 780     Sum += Prob.getNumerator();
 781   // Due to precision issue, we assume that the sum of probabilities is one if
 782   // the difference between the sum of their numerators and the denominator is
 783   // no greater than the number of successors.
 784   assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
 785              Probs.size() &&
 786          "The sum of successors's probabilities exceeds one.");
 787 #endif // NDEBUG
 788 }
 789
 790 void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
 791                                      BranchProbability Prob) {
 792   // Probability list is either empty (if successor list isn't empty, this means
 793   // disabled optimization) or has the same size as successor list.
 794   if (!(Probs.empty() && !Successors.empty()))
 795     Probs.push_back(Prob);
 796   Successors.push_back(Succ);
 797   Succ->addPredecessor(this);
 798 }
 799
 800 void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
 801   // We need to make sure probability list is either empty or has the same size
 802   // of successor list. When this function is called, we can safely delete all
 803   // probability in the list.
 804   Probs.clear();
 805   Successors.push_back(Succ);
 806   Succ->addPredecessor(this);
 807 }
 808
 809 void MachineBasicBlock::splitSuccessor(MachineBasicBlock *Old,
 810                                        MachineBasicBlock *New,
 811                                        bool NormalizeSuccProbs) {
 812   succ_iterator OldI = llvm::find(successors(), Old);
 813   assert(OldI != succ_end() && "Old is not a successor of this block!");
 814   assert(!llvm::is_contained(successors(), New) &&
 815          "New is already a successor of this block!");
 816
 817   // Add a new successor with equal probability as the original one. Note
 818   // that we directly copy the probability using the iterator rather than
 819   // getting a potentially synthetic probability computed when unknown. This
 820   // preserves the probabilities as-is and then we can renormalize them and
 821   // query them effectively afterward.
 822   addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
 823                                   : *getProbabilityIterator(OldI));
 824   if (NormalizeSuccProbs)
 825     normalizeSuccProbs();
 826 }
 827
 828 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
 829                                         bool NormalizeSuccProbs) {
 830   succ_iterator I = find(Successors, Succ);
 831   removeSuccessor(I, NormalizeSuccProbs);
 832 }
 833
 834 MachineBasicBlock::succ_iterator
 835 MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
 836   assert(I != Successors.end() && "Not a current successor!");
 837
 838   // If probability list is empty it means we don't use it (disabled
 839   // optimization).
 840   if (!Probs.empty()) {
 841     probability_iterator WI = getProbabilityIterator(I);
 842     Probs.erase(WI);
 843     if (NormalizeSuccProbs)
 844       normalizeSuccProbs();
 845   }
 846
 847   (*I)->removePredecessor(this);
 848   return Successors.erase(I);
 849 }
 850
 851 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
 852                                          MachineBasicBlock *New) {
 853   if (Old == New)
 854     return;
 855
 856   succ_iterator E = succ_end();
 857   succ_iterator NewI = E;
 858   succ_iterator OldI = E;
 859   for (succ_iterator I = succ_begin(); I != E; ++I) {
 860     if (*I == Old) {
 861       OldI = I;
 862       if (NewI != E)
 863         break;
 864     }
 865     if (*I == New) {
 866       NewI = I;
 867       if (OldI != E)
 868         break;
 869     }
 870   }
 871   assert(OldI != E && "Old is not a successor of this block");
 872
 873   // If New isn't already a successor, let it take Old's place.
 874   if (NewI == E) {
 875     Old->removePredecessor(this);
 876     New->addPredecessor(this);
 877     *OldI = New;
 878     return;
 879   }
 880
 881   // New is already a successor.
 882   // Update its probability instead of adding a duplicate edge.
 883   if (!Probs.empty()) {
 884     auto ProbIter = getProbabilityIterator(NewI);
 885     if (!ProbIter->isUnknown())
 886       *ProbIter += *getProbabilityIterator(OldI);
 887   }
 888   removeSuccessor(OldI);
 889 }
 890
 891 void MachineBasicBlock::copySuccessor(const MachineBasicBlock *Orig,
 892                                       succ_iterator I) {
 893   if (!Orig->Probs.empty())
 894     addSuccessor(*I, Orig->getSuccProbability(I));
 895   else
 896     addSuccessorWithoutProb(*I);
 897 }
 898
 899 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
 900   Predecessors.push_back(Pred);
 901 }
 902
 903 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
 904   pred_iterator I = find(Predecessors, Pred);
 905   assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
 906   Predecessors.erase(I);
 907 }
 908
 909 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
 910   if (this == FromMBB)
 911     return;
 912
 913   while (!FromMBB->succ_empty()) {
 914     MachineBasicBlock *Succ = *FromMBB->succ_begin();
 915
 916     // If probability list is empty it means we don't use it (disabled
 917     // optimization).
 918     if (!FromMBB->Probs.empty()) {
 919       auto Prob = *FromMBB->Probs.begin();
 920       addSuccessor(Succ, Prob);
 921     } else
 922       addSuccessorWithoutProb(Succ);
 923
 924     FromMBB->removeSuccessor(Succ);
 925   }
 926 }
 927
 928 void
 929 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
 930   if (this == FromMBB)
 931     return;
 932
 933   while (!FromMBB->succ_empty()) {
 934     MachineBasicBlock *Succ = *FromMBB->succ_begin();
 935     if (!FromMBB->Probs.empty()) {
 936       auto Prob = *FromMBB->Probs.begin();
 937       addSuccessor(Succ, Prob);
 938     } else
 939       addSuccessorWithoutProb(Succ);
 940     FromMBB->removeSuccessor(Succ);
 941
 942     // Fix up any PHI nodes in the successor.
 943     Succ->replacePhiUsesWith(FromMBB, this);
 944   }
 945   normalizeSuccProbs();
 946 }
 947
 948 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
 949   return is_contained(predecessors(), MBB);
 950 }
 951
 952 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
 953   return is_contained(successors(), MBB);
 954 }
 955
 956 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
 957   MachineFunction::const_iterator I(this);
 958   return std::next(I) == MachineFunction::const_iterator(MBB);
 959 }
 960
 961 const MachineBasicBlock *MachineBasicBlock::getSingleSuccessor() const {
 962   return Successors.size() == 1 ? Successors[0] : nullptr;
 963 }
 964
 965 const MachineBasicBlock *MachineBasicBlock::getSinglePredecessor() const {
 966   return Predecessors.size() == 1 ? Predecessors[0] : nullptr;
 967 }
 968
 969 MachineBasicBlock *MachineBasicBlock::getFallThrough(bool JumpToFallThrough) {
 970   MachineFunction::iterator Fallthrough = getIterator();
 971   ++Fallthrough;
 972   // If FallthroughBlock is off the end of the function, it can't fall through.
 973   if (Fallthrough == getParent()->end())
 974     return nullptr;
 975
 976   // If FallthroughBlock isn't a successor, no fallthrough is possible.
 977   if (!isSuccessor(&*Fallthrough))
 978     return nullptr;
 979
 980   // Analyze the branches, if any, at the end of the block.
 981   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 982   SmallVector<MachineOperand, 4> Cond;
 983   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 984   if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
 985     // If we couldn't analyze the branch, examine the last instruction.
 986     // If the block doesn't end in a known control barrier, assume fallthrough
 987     // is possible. The isPredicated check is needed because this code can be
 988     // called during IfConversion, where an instruction which is normally a
 989     // Barrier is predicated and thus no longer an actual control barrier.
 990     return (empty() || !back().isBarrier() || TII->isPredicated(back()))
 991                ? &*Fallthrough
 992                : nullptr;
 993   }
 994
 995   // If there is no branch, control always falls through.
 996   if (!TBB) return &*Fallthrough;
 997
 998   // If there is some explicit branch to the fallthrough block, it can obviously
 999   // reach, even though the branch should get folded to fall through implicitly.
1000   if (JumpToFallThrough && (MachineFunction::iterator(TBB) == Fallthrough ||
1001                             MachineFunction::iterator(FBB) == Fallthrough))
1002     return &*Fallthrough;
1003
1004   // If it's an unconditional branch to some block not the fall through, it
1005   // doesn't fall through.
1006   if (Cond.empty()) return nullptr;
1007
1008   // Otherwise, if it is conditional and has no explicit false block, it falls
1009   // through.
1010   return (FBB == nullptr) ? &*Fallthrough : nullptr;
1011 }
1012
1013 bool MachineBasicBlock::canFallThrough() {
1014   return getFallThrough() != nullptr;
1015 }
1016
1017 MachineBasicBlock *MachineBasicBlock::splitAt(MachineInstr &MI,
1018                                               bool UpdateLiveIns,
1019                                               LiveIntervals *LIS) {
1020   MachineBasicBlock::iterator SplitPoint(&MI);
1021   ++SplitPoint;
1022
1023   if (SplitPoint == end()) {
1024     // Don't bother with a new block.
1025     return this;
1026   }
1027
1028   MachineFunction *MF = getParent();
1029
1030   LivePhysRegs LiveRegs;
1031   if (UpdateLiveIns) {
1032     // Make sure we add any physregs we define in the block as liveins to the
1033     // new block.
1034     MachineBasicBlock::iterator Prev(&MI);
1035     LiveRegs.init(*MF->getSubtarget().getRegisterInfo());
1036     LiveRegs.addLiveOuts(*this);
1037     for (auto I = rbegin(), E = Prev.getReverse(); I != E; ++I)
1038       LiveRegs.stepBackward(*I);
1039   }
1040
1041   MachineBasicBlock *SplitBB = MF->CreateMachineBasicBlock(getBasicBlock());
1042
1043   MF->insert(++MachineFunction::iterator(this), SplitBB);
1044   SplitBB->splice(SplitBB->begin(), this, SplitPoint, end());
1045
1046   SplitBB->transferSuccessorsAndUpdatePHIs(this);
1047   addSuccessor(SplitBB);
1048
1049   if (UpdateLiveIns)
1050     addLiveIns(*SplitBB, LiveRegs);
1051
1052   if (LIS)
1053     LIS->insertMBBInMaps(SplitBB);
1054
1055   return SplitBB;
1056 }
1057
1058 // Returns `true` if there are possibly other users of the jump table at
1059 // `JumpTableIndex` except for the ones in `IgnoreMBB`.
1060 static bool jumpTableHasOtherUses(const MachineFunction &MF,
1061                                   const MachineBasicBlock &IgnoreMBB,
1062                                   int JumpTableIndex) {
1063   assert(JumpTableIndex >= 0 && "need valid index");
1064   const MachineJumpTableInfo &MJTI = *MF.getJumpTableInfo();
1065   const MachineJumpTableEntry &MJTE = MJTI.getJumpTables()[JumpTableIndex];
1066   // Take any basic block from the table; every user of the jump table must
1067   // show up in the predecessor list.
1068   const MachineBasicBlock *MBB = nullptr;
1069   for (MachineBasicBlock *B : MJTE.MBBs) {
1070     if (B != nullptr) {
1071       MBB = B;
1072       break;
1073     }
1074   }
1075   if (MBB == nullptr)
1076     return true; // can't rule out other users if there isn't any block.
1077   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
1078   SmallVector<MachineOperand, 4> Cond;
1079   for (MachineBasicBlock *Pred : MBB->predecessors()) {
1080     if (Pred == &IgnoreMBB)
1081       continue;
1082     MachineBasicBlock *DummyT = nullptr;
1083     MachineBasicBlock *DummyF = nullptr;
1084     Cond.clear();
1085     if (!TII.analyzeBranch(*Pred, DummyT, DummyF, Cond,
1086                            /*AllowModify=*/false)) {
1087       // analyzable direct jump
1088       continue;
1089     }
1090     int PredJTI = findJumpTableIndex(*Pred);
1091     if (PredJTI >= 0) {
1092       if (PredJTI == JumpTableIndex)
1093         return true;
1094       continue;
1095     }
1096     // Be conservative for unanalyzable jumps.
1097     return true;
1098   }
1099   return false;
1100 }
1101
1102 class SlotIndexUpdateDelegate : public MachineFunction::Delegate {
1103 private:
1104   MachineFunction &MF;
1105   SlotIndexes *Indexes;
1106   SmallSetVector<MachineInstr *, 2> Insertions;
1107
1108 public:
1109   SlotIndexUpdateDelegate(MachineFunction &MF, SlotIndexes *Indexes)
1110       : MF(MF), Indexes(Indexes) {
1111     MF.setDelegate(this);
1112   }
1113
1114   ~SlotIndexUpdateDelegate() {
1115     MF.resetDelegate(this);
1116     for (auto MI : Insertions)
1117       Indexes->insertMachineInstrInMaps(*MI);
1118   }
1119
1120   void MF_HandleInsertion(MachineInstr &MI) override {
1121     // This is called before MI is inserted into block so defer index update.
1122     if (Indexes)
1123       Insertions.insert(&MI);
1124   }
1125
1126   void MF_HandleRemoval(MachineInstr &MI) override {
1127     if (Indexes && !Insertions.remove(&MI))
1128       Indexes->removeMachineInstrFromMaps(MI);
1129   }
1130 };
1131
1132 MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(
1133     MachineBasicBlock *Succ, Pass &P,
1134     std::vector<SparseBitVector<>> *LiveInSets) {
1135   if (!canSplitCriticalEdge(Succ))
1136     return nullptr;
1137
1138   MachineFunction *MF = getParent();
1139   MachineBasicBlock *PrevFallthrough = getNextNode();
1140   DebugLoc DL;  // FIXME: this is nowhere
1141
1142   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
1143   NMBB->setCallFrameSize(Succ->getCallFrameSize());
1144
1145   // Is there an indirect jump with jump table?
1146   bool ChangedIndirectJump = false;
1147   int JTI = findJumpTableIndex(*this);
1148   if (JTI >= 0) {
1149     MachineJumpTableInfo &MJTI = *MF->getJumpTableInfo();
1150     MJTI.ReplaceMBBInJumpTable(JTI, Succ, NMBB);
1151     ChangedIndirectJump = true;
1152   }
1153
1154   MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
1155   LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
1156                     << " -- " << printMBBReference(*NMBB) << " -- "
1157                     << printMBBReference(*Succ) << '\n');
1158
1159   LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
1160   SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
1161   if (LIS)
1162     LIS->insertMBBInMaps(NMBB);
1163   else if (Indexes)
1164     Indexes->insertMBBInMaps(NMBB);
1165
1166   // On some targets like Mips, branches may kill virtual registers. Make sure
1167   // that LiveVariables is properly updated after updateTerminator replaces the
1168   // terminators.
1169   LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
1170
1171   // Collect a list of virtual registers killed by the terminators.
1172   SmallVector<Register, 4> KilledRegs;
1173   if (LV)
1174     for (MachineInstr &MI :
1175          llvm::make_range(getFirstInstrTerminator(), instr_end())) {
1176       for (MachineOperand &MO : MI.all_uses()) {
1177         if (MO.getReg() == 0 || !MO.isKill() || MO.isUndef())
1178           continue;
1179         Register Reg = MO.getReg();
1180         if (Reg.isPhysical() || LV->getVarInfo(Reg).removeKill(MI)) {
1181           KilledRegs.push_back(Reg);
1182           LLVM_DEBUG(dbgs() << "Removing terminator kill: " << MI);
1183           MO.setIsKill(false);
1184         }
1185       }
1186     }
1187
1188   SmallVector<Register, 4> UsedRegs;
1189   if (LIS) {
1190     for (MachineInstr &MI :
1191          llvm::make_range(getFirstInstrTerminator(), instr_end())) {
1192       for (const MachineOperand &MO : MI.operands()) {
1193         if (!MO.isReg() || MO.getReg() == 0)
1194           continue;
1195
1196         Register Reg = MO.getReg();
1197         if (!is_contained(UsedRegs, Reg))
1198           UsedRegs.push_back(Reg);
1199       }
1200     }
1201   }
1202
1203   ReplaceUsesOfBlockWith(Succ, NMBB);
1204
1205   // Since we replaced all uses of Succ with NMBB, that should also be treated
1206   // as the fallthrough successor
1207   if (Succ == PrevFallthrough)
1208     PrevFallthrough = NMBB;
1209
1210   if (!ChangedIndirectJump) {
1211     SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1212     updateTerminator(PrevFallthrough);
1213   }
1214
1215   // Insert unconditional "jump Succ" instruction in NMBB if necessary.
1216   NMBB->addSuccessor(Succ);
1217   if (!NMBB->isLayoutSuccessor(Succ)) {
1218     SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1219     SmallVector<MachineOperand, 4> Cond;
1220     const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
1221     TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
1222   }
1223
1224   // Fix PHI nodes in Succ so they refer to NMBB instead of this.
1225   Succ->replacePhiUsesWith(this, NMBB);
1226
1227   // Inherit live-ins from the successor
1228   for (const auto &LI : Succ->liveins())
1229     NMBB->addLiveIn(LI);
1230
1231   // Update LiveVariables.
1232   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
1233   if (LV) {
1234     // Restore kills of virtual registers that were killed by the terminators.
1235     while (!KilledRegs.empty()) {
1236       Register Reg = KilledRegs.pop_back_val();
1237       for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
1238         if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
1239           continue;
1240         if (Reg.isVirtual())
1241           LV->getVarInfo(Reg).Kills.push_back(&*I);
1242         LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1243         break;
1244       }
1245     }
1246     // Update relevant live-through information.
1247     if (LiveInSets != nullptr)
1248       LV->addNewBlock(NMBB, this, Succ, *LiveInSets);
1249     else
1250       LV->addNewBlock(NMBB, this, Succ);
1251   }
1252
1253   if (LIS) {
1254     // After splitting the edge and updating SlotIndexes, live intervals may be
1255     // in one of two situations, depending on whether this block was the last in
1256     // the function. If the original block was the last in the function, all
1257     // live intervals will end prior to the beginning of the new split block. If
1258     // the original block was not at the end of the function, all live intervals
1259     // will extend to the end of the new split block.
1260
1261     bool isLastMBB =
1262       std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1263
1264     SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1265     SlotIndex PrevIndex = StartIndex.getPrevSlot();
1266     SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1267
1268     // Find the registers used from NMBB in PHIs in Succ.
1269     SmallSet<Register, 8> PHISrcRegs;
1270     for (MachineBasicBlock::instr_iterator
1271          I = Succ->instr_begin(), E = Succ->instr_end();
1272          I != E && I->isPHI(); ++I) {
1273       for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1274         if (I->getOperand(ni+1).getMBB() == NMBB) {
1275           MachineOperand &MO = I->getOperand(ni);
1276           Register Reg = MO.getReg();
1277           PHISrcRegs.insert(Reg);
1278           if (MO.isUndef())
1279             continue;
1280
1281           LiveInterval &LI = LIS->getInterval(Reg);
1282           VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1283           assert(VNI &&
1284                  "PHI sources should be live out of their predecessors.");
1285           LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1286           for (auto &SR : LI.subranges())
1287             SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1288         }
1289       }
1290     }
1291
1292     MachineRegisterInfo *MRI = &getParent()->getRegInfo();
1293     for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1294       Register Reg = Register::index2VirtReg(i);
1295       if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1296         continue;
1297
1298       LiveInterval &LI = LIS->getInterval(Reg);
1299       if (!LI.liveAt(PrevIndex))
1300         continue;
1301
1302       bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1303       if (isLiveOut && isLastMBB) {
1304         VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1305         assert(VNI && "LiveInterval should have VNInfo where it is live.");
1306         LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1307         // Update subranges with live values
1308         for (auto &SR : LI.subranges()) {
1309           VNInfo *VNI = SR.getVNInfoAt(PrevIndex);
1310           if (VNI)
1311             SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1312         }
1313       } else if (!isLiveOut && !isLastMBB) {
1314         LI.removeSegment(StartIndex, EndIndex);
1315         for (auto &SR : LI.subranges())
1316           SR.removeSegment(StartIndex, EndIndex);
1317       }
1318     }
1319
1320     // Update all intervals for registers whose uses may have been modified by
1321     // updateTerminator().
1322     LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1323   }
1324
1325   if (MachineDominatorTree *MDT =
1326           P.getAnalysisIfAvailable<MachineDominatorTree>())
1327     MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1328
1329   if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
1330     if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1331       // If one or the other blocks were not in a loop, the new block is not
1332       // either, and thus LI doesn't need to be updated.
1333       if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1334         if (TIL == DestLoop) {
1335           // Both in the same loop, the NMBB joins loop.
1336           DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1337         } else if (TIL->contains(DestLoop)) {
1338           // Edge from an outer loop to an inner loop.  Add to the outer loop.
1339           TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1340         } else if (DestLoop->contains(TIL)) {
1341           // Edge from an inner loop to an outer loop.  Add to the outer loop.
1342           DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1343         } else {
1344           // Edge from two loops with no containment relation.  Because these
1345           // are natural loops, we know that the destination block must be the
1346           // header of its loop (adding a branch into a loop elsewhere would
1347           // create an irreducible loop).
1348           assert(DestLoop->getHeader() == Succ &&
1349                  "Should not create irreducible loops!");
1350           if (MachineLoop *P = DestLoop->getParentLoop())
1351             P->addBasicBlockToLoop(NMBB, MLI->getBase());
1352         }
1353       }
1354     }
1355
1356   return NMBB;
1357 }
1358
1359 bool MachineBasicBlock::canSplitCriticalEdge(
1360     const MachineBasicBlock *Succ) const {
1361   // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1362   // it in this generic function.
1363   if (Succ->isEHPad())
1364     return false;
1365
1366   // Splitting the critical edge to a callbr's indirect block isn't advised.
1367   // Don't do it in this generic function.
1368   if (Succ->isInlineAsmBrIndirectTarget())
1369     return false;
1370
1371   const MachineFunction *MF = getParent();
1372   // Performance might be harmed on HW that implements branching using exec mask
1373   // where both sides of the branches are always executed.
1374   if (MF->getTarget().requiresStructuredCFG())
1375     return false;
1376
1377   // Do we have an Indirect jump with a jumptable that we can rewrite?
1378   int JTI = findJumpTableIndex(*this);
1379   if (JTI >= 0 && !jumpTableHasOtherUses(*MF, *this, JTI))
1380     return true;
1381
1382   // We may need to update this's terminator, but we can't do that if
1383   // analyzeBranch fails.
1384   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1385   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1386   SmallVector<MachineOperand, 4> Cond;
1387   // AnalyzeBanch should modify this, since we did not allow modification.
1388   if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1389                          /*AllowModify*/ false))
1390     return false;
1391
1392   // Avoid bugpoint weirdness: A block may end with a conditional branch but
1393   // jumps to the same MBB is either case. We have duplicate CFG edges in that
1394   // case that we can't handle. Since this never happens in properly optimized
1395   // code, just skip those edges.
1396   if (TBB && TBB == FBB) {
1397     LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1398                       << printMBBReference(*this) << '\n');
1399     return false;
1400   }
1401   return true;
1402 }
1403
1404 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1405 /// neighboring instructions so the bundle won't be broken by removing MI.
1406 static void unbundleSingleMI(MachineInstr *MI) {
1407   // Removing the first instruction in a bundle.
1408   if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1409     MI->unbundleFromSucc();
1410   // Removing the last instruction in a bundle.
1411   if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1412     MI->unbundleFromPred();
1413   // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1414   // are already fine.
1415 }
1416
1417 MachineBasicBlock::instr_iterator
1418 MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1419   unbundleSingleMI(&*I);
1420   return Insts.erase(I);
1421 }
1422
1423 MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1424   unbundleSingleMI(MI);
1425   MI->clearFlag(MachineInstr::BundledPred);
1426   MI->clearFlag(MachineInstr::BundledSucc);
1427   return Insts.remove(MI);
1428 }
1429
1430 MachineBasicBlock::instr_iterator
1431 MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
1432   assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1433          "Cannot insert instruction with bundle flags");
1434   // Set the bundle flags when inserting inside a bundle.
1435   if (I != instr_end() && I->isBundledWithPred()) {
1436     MI->setFlag(MachineInstr::BundledPred);
1437     MI->setFlag(MachineInstr::BundledSucc);
1438   }
1439   return Insts.insert(I, MI);
1440 }
1441
1442 /// This method unlinks 'this' from the containing function, and returns it, but
1443 /// does not delete it.
1444 MachineBasicBlock *MachineBasicBlock::removeFromParent() {
1445   assert(getParent() && "Not embedded in a function!");
1446   getParent()->remove(this);
1447   return this;
1448 }
1449
1450 /// This method unlinks 'this' from the containing function, and deletes it.
1451 void MachineBasicBlock::eraseFromParent() {
1452   assert(getParent() && "Not embedded in a function!");
1453   getParent()->erase(this);
1454 }
1455
1456 /// Given a machine basic block that branched to 'Old', change the code and CFG
1457 /// so that it branches to 'New' instead.
1458 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1459                                                MachineBasicBlock *New) {
1460   assert(Old != New && "Cannot replace self with self!");
1461
1462   MachineBasicBlock::instr_iterator I = instr_end();
1463   while (I != instr_begin()) {
1464     --I;
1465     if (!I->isTerminator()) break;
1466
1467     // Scan the operands of this machine instruction, replacing any uses of Old
1468     // with New.
1469     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1470       if (I->getOperand(i).isMBB() &&
1471           I->getOperand(i).getMBB() == Old)
1472         I->getOperand(i).setMBB(New);
1473   }
1474
1475   // Update the successor information.
1476   replaceSuccessor(Old, New);
1477 }
1478
1479 void MachineBasicBlock::replacePhiUsesWith(MachineBasicBlock *Old,
1480                                            MachineBasicBlock *New) {
1481   for (MachineInstr &MI : phis())
1482     for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
1483       MachineOperand &MO = MI.getOperand(i);
1484       if (MO.getMBB() == Old)
1485         MO.setMBB(New);
1486     }
1487 }
1488
1489 /// Find the next valid DebugLoc starting at MBBI, skipping any debug
1490 /// instructions.  Return UnknownLoc if there is none.
1491 DebugLoc
1492 MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
1493   // Skip debug declarations, we don't want a DebugLoc from them.
1494   MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1495   if (MBBI != instr_end())
1496     return MBBI->getDebugLoc();
1497   return {};
1498 }
1499
1500 DebugLoc MachineBasicBlock::rfindDebugLoc(reverse_instr_iterator MBBI) {
1501   if (MBBI == instr_rend())
1502     return findDebugLoc(instr_begin());
1503   // Skip debug declarations, we don't want a DebugLoc from them.
1504   MBBI = skipDebugInstructionsBackward(MBBI, instr_rbegin());
1505   if (!MBBI->isDebugInstr())
1506     return MBBI->getDebugLoc();
1507   return {};
1508 }
1509
1510 /// Find the previous valid DebugLoc preceding MBBI, skipping any debug
1511 /// instructions.  Return UnknownLoc if there is none.
1512 DebugLoc MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI) {
1513   if (MBBI == instr_begin())
1514     return {};
1515   // Skip debug instructions, we don't want a DebugLoc from them.
1516   MBBI = prev_nodbg(MBBI, instr_begin());
1517   if (!MBBI->isDebugInstr())
1518     return MBBI->getDebugLoc();
1519   return {};
1520 }
1521
1522 DebugLoc MachineBasicBlock::rfindPrevDebugLoc(reverse_instr_iterator MBBI) {
1523   if (MBBI == instr_rend())
1524     return {};
1525   // Skip debug declarations, we don't want a DebugLoc from them.
1526   MBBI = next_nodbg(MBBI, instr_rend());
1527   if (MBBI != instr_rend())
1528     return MBBI->getDebugLoc();
1529   return {};
1530 }
1531
1532 /// Find and return the merged DebugLoc of the branch instructions of the block.
1533 /// Return UnknownLoc if there is none.
1534 DebugLoc
1535 MachineBasicBlock::findBranchDebugLoc() {
1536   DebugLoc DL;
1537   auto TI = getFirstTerminator();
1538   while (TI != end() && !TI->isBranch())
1539     ++TI;
1540
1541   if (TI != end()) {
1542     DL = TI->getDebugLoc();
1543     for (++TI ; TI != end() ; ++TI)
1544       if (TI->isBranch())
1545         DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1546   }
1547   return DL;
1548 }
1549
1550 /// Return probability of the edge from this block to MBB.
1551 BranchProbability
1552 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1553   if (Probs.empty())
1554     return BranchProbability(1, succ_size());
1555
1556   const auto &Prob = *getProbabilityIterator(Succ);
1557   if (Prob.isUnknown()) {
1558     // For unknown probabilities, collect the sum of all known ones, and evenly
1559     // ditribute the complemental of the sum to each unknown probability.
1560     unsigned KnownProbNum = 0;
1561     auto Sum = BranchProbability::getZero();
1562     for (const auto &P : Probs) {
1563       if (!P.isUnknown()) {
1564         Sum += P;
1565         KnownProbNum++;
1566       }
1567     }
1568     return Sum.getCompl() / (Probs.size() - KnownProbNum);
1569   } else
1570     return Prob;
1571 }
1572
1573 /// Set successor probability of a given iterator.
1574 void MachineBasicBlock::setSuccProbability(succ_iterator I,
1575                                            BranchProbability Prob) {
1576   assert(!Prob.isUnknown());
1577   if (Probs.empty())
1578     return;
1579   *getProbabilityIterator(I) = Prob;
1580 }
1581
1582 /// Return probability iterator corresonding to the I successor iterator
1583 MachineBasicBlock::const_probability_iterator
1584 MachineBasicBlock::getProbabilityIterator(
1585     MachineBasicBlock::const_succ_iterator I) const {
1586   assert(Probs.size() == Successors.size() && "Async probability list!");
1587   const size_t index = std::distance(Successors.begin(), I);
1588   assert(index < Probs.size() && "Not a current successor!");
1589   return Probs.begin() + index;
1590 }
1591
1592 /// Return probability iterator corresonding to the I successor iterator.
1593 MachineBasicBlock::probability_iterator
1594 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1595   assert(Probs.size() == Successors.size() && "Async probability list!");
1596   const size_t index = std::distance(Successors.begin(), I);
1597   assert(index < Probs.size() && "Not a current successor!");
1598   return Probs.begin() + index;
1599 }
1600
1601 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1602 /// as of just before "MI".
1603 ///
1604 /// Search is localised to a neighborhood of
1605 /// Neighborhood instructions before (searching for defs or kills) and N
1606 /// instructions after (searching just for defs) MI.
1607 MachineBasicBlock::LivenessQueryResult
1608 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
1609                                            MCRegister Reg, const_iterator Before,
1610                                            unsigned Neighborhood) const {
1611   unsigned N = Neighborhood;
1612
1613   // Try searching forwards from Before, looking for reads or defs.
1614   const_iterator I(Before);
1615   for (; I != end() && N > 0; ++I) {
1616     if (I->isDebugOrPseudoInstr())
1617       continue;
1618
1619     --N;
1620
1621     PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);
1622
1623     // Register is live when we read it here.
1624     if (Info.Read)
1625       return LQR_Live;
1626     // Register is dead if we can fully overwrite or clobber it here.
1627     if (Info.FullyDefined || Info.Clobbered)
1628       return LQR_Dead;
1629   }
1630
1631   // If we reached the end, it is safe to clobber Reg at the end of a block of
1632   // no successor has it live in.
1633   if (I == end()) {
1634     for (MachineBasicBlock *S : successors()) {
1635       for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1636         if (TRI->regsOverlap(LI.PhysReg, Reg))
1637           return LQR_Live;
1638       }
1639     }
1640
1641     return LQR_Dead;
1642   }
1643
1644
1645   N = Neighborhood;
1646
1647   // Start by searching backwards from Before, looking for kills, reads or defs.
1648   I = const_iterator(Before);
1649   // If this is the first insn in the block, don't search backwards.
1650   if (I != begin()) {
1651     do {
1652       --I;
1653
1654       if (I->isDebugOrPseudoInstr())
1655         continue;
1656
1657       --N;
1658
1659       PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);
1660
1661       // Defs happen after uses so they take precedence if both are present.
1662
1663       // Register is dead after a dead def of the full register.
1664       if (Info.DeadDef)
1665         return LQR_Dead;
1666       // Register is (at least partially) live after a def.
1667       if (Info.Defined) {
1668         if (!Info.PartialDeadDef)
1669           return LQR_Live;
1670         // As soon as we saw a partial definition (dead or not),
1671         // we cannot tell if the value is partial live without
1672         // tracking the lanemasks. We are not going to do this,
1673         // so fall back on the remaining of the analysis.
1674         break;
1675       }
1676       // Register is dead after a full kill or clobber and no def.
1677       if (Info.Killed || Info.Clobbered)
1678         return LQR_Dead;
1679       // Register must be live if we read it.
1680       if (Info.Read)
1681         return LQR_Live;
1682
1683     } while (I != begin() && N > 0);
1684   }
1685
1686   // If all the instructions before this in the block are debug instructions,
1687   // skip over them.
1688   while (I != begin() && std::prev(I)->isDebugOrPseudoInstr())
1689     --I;
1690
1691   // Did we get to the start of the block?
1692   if (I == begin()) {
1693     // If so, the register's state is definitely defined by the live-in state.
1694     for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())
1695       if (TRI->regsOverlap(LI.PhysReg, Reg))
1696         return LQR_Live;
1697
1698     return LQR_Dead;
1699   }
1700
1701   // At this point we have no idea of the liveness of the register.
1702   return LQR_Unknown;
1703 }
1704
1705 const uint32_t *
1706 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1707   // EH funclet entry does not preserve any registers.
1708   return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1709 }
1710
1711 const uint32_t *
1712 MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
1713   // If we see a return block with successors, this must be a funclet return,
1714   // which does not preserve any registers. If there are no successors, we don't
1715   // care what kind of return it is, putting a mask after it is a no-op.
1716   return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1717 }
1718
1719 void MachineBasicBlock::clearLiveIns() {
1720   LiveIns.clear();
1721 }
1722
1723 MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
1724   assert(getParent()->getProperties().hasProperty(
1725       MachineFunctionProperties::Property::TracksLiveness) &&
1726       "Liveness information is accurate");
1727   return LiveIns.begin();
1728 }
1729
1730 MachineBasicBlock::liveout_iterator MachineBasicBlock::liveout_begin() const {
1731   const MachineFunction &MF = *getParent();
1732   assert(MF.getProperties().hasProperty(
1733       MachineFunctionProperties::Property::TracksLiveness) &&
1734       "Liveness information is accurate");
1735
1736   const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
1737   MCPhysReg ExceptionPointer = 0, ExceptionSelector = 0;
1738   if (MF.getFunction().hasPersonalityFn()) {
1739     auto PersonalityFn = MF.getFunction().getPersonalityFn();
1740     ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);
1741     ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);
1742   }
1743
1744   return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);
1745 }
1746
1747 bool MachineBasicBlock::sizeWithoutDebugLargerThan(unsigned Limit) const {
1748   unsigned Cntr = 0;
1749   auto R = instructionsWithoutDebug(begin(), end());
1750   for (auto I = R.begin(), E = R.end(); I != E; ++I) {
1751     if (++Cntr > Limit)
1752       return true;
1753   }
1754   return false;
1755 }
1756
1757 const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
1758 const MBBSectionID
1759     MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);