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