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