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