contrib/llvm/lib/CodeGen/MachineBasicBlock.cpp

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