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