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 bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
 354   livein_iterator I = find_if(
 355       LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
 356   return I != livein_end() && (I->LaneMask & LaneMask).any();
 357 }
 358
 359 void MachineBasicBlock::sortUniqueLiveIns() {
 360   std::sort(LiveIns.begin(), LiveIns.end(),
 361             [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
 362               return LI0.PhysReg < LI1.PhysReg;
 363             });
 364   // Liveins are sorted by physreg now we can merge their lanemasks.
 365   LiveInVector::const_iterator I = LiveIns.begin();
 366   LiveInVector::const_iterator J;
 367   LiveInVector::iterator Out = LiveIns.begin();
 368   for (; I != LiveIns.end(); ++Out, I = J) {
 369     unsigned PhysReg = I->PhysReg;
 370     LaneBitmask LaneMask = I->LaneMask;
 371     for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
 372       LaneMask |= J->LaneMask;
 373     Out->PhysReg = PhysReg;
 374     Out->LaneMask = LaneMask;
 375   }
 376   LiveIns.erase(Out, LiveIns.end());
 377 }
 378
 379 unsigned
 380 MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) {
 381   assert(getParent() && "MBB must be inserted in function");
 382   assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
 383   assert(RC && "Register class is required");
 384   assert((isEHPad() || this == &getParent()->front()) &&
 385          "Only the entry block and landing pads can have physreg live ins");
 386
 387   bool LiveIn = isLiveIn(PhysReg);
 388   iterator I = SkipPHIsAndLabels(begin()), E = end();
 389   MachineRegisterInfo &MRI = getParent()->getRegInfo();
 390   const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
 391
 392   // Look for an existing copy.
 393   if (LiveIn)
 394     for (;I != E && I->isCopy(); ++I)
 395       if (I->getOperand(1).getReg() == PhysReg) {
 396         unsigned VirtReg = I->getOperand(0).getReg();
 397         if (!MRI.constrainRegClass(VirtReg, RC))
 398           llvm_unreachable("Incompatible live-in register class.");
 399         return VirtReg;
 400       }
 401
 402   // No luck, create a virtual register.
 403   unsigned VirtReg = MRI.createVirtualRegister(RC);
 404   BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
 405     .addReg(PhysReg, RegState::Kill);
 406   if (!LiveIn)
 407     addLiveIn(PhysReg);
 408   return VirtReg;
 409 }
 410
 411 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
 412   getParent()->splice(NewAfter->getIterator(), getIterator());
 413 }
 414
 415 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
 416   getParent()->splice(++NewBefore->getIterator(), getIterator());
 417 }
 418
 419 void MachineBasicBlock::updateTerminator() {
 420   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 421   // A block with no successors has no concerns with fall-through edges.
 422   if (this->succ_empty())
 423     return;
 424
 425   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 426   SmallVector<MachineOperand, 4> Cond;
 427   DebugLoc DL = findBranchDebugLoc();
 428   bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
 429   (void) B;
 430   assert(!B && "UpdateTerminators requires analyzable predecessors!");
 431   if (Cond.empty()) {
 432     if (TBB) {
 433       // The block has an unconditional branch. If its successor is now its
 434       // layout successor, delete the branch.
 435       if (isLayoutSuccessor(TBB))
 436         TII->removeBranch(*this);
 437     } else {
 438       // The block has an unconditional fallthrough. If its successor is not its
 439       // layout successor, insert a branch. First we have to locate the only
 440       // non-landing-pad successor, as that is the fallthrough block.
 441       for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
 442         if ((*SI)->isEHPad())
 443           continue;
 444         assert(!TBB && "Found more than one non-landing-pad successor!");
 445         TBB = *SI;
 446       }
 447
 448       // If there is no non-landing-pad successor, the block has no fall-through
 449       // edges to be concerned with.
 450       if (!TBB)
 451         return;
 452
 453       // Finally update the unconditional successor to be reached via a branch
 454       // if it would not be reached by fallthrough.
 455       if (!isLayoutSuccessor(TBB))
 456         TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 457     }
 458     return;
 459   }
 460
 461   if (FBB) {
 462     // The block has a non-fallthrough conditional branch. If one of its
 463     // successors is its layout successor, rewrite it to a fallthrough
 464     // conditional branch.
 465     if (isLayoutSuccessor(TBB)) {
 466       if (TII->reverseBranchCondition(Cond))
 467         return;
 468       TII->removeBranch(*this);
 469       TII->insertBranch(*this, FBB, nullptr, Cond, DL);
 470     } else if (isLayoutSuccessor(FBB)) {
 471       TII->removeBranch(*this);
 472       TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 473     }
 474     return;
 475   }
 476
 477   // Walk through the successors and find the successor which is not a landing
 478   // pad and is not the conditional branch destination (in TBB) as the
 479   // fallthrough successor.
 480   MachineBasicBlock *FallthroughBB = nullptr;
 481   for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
 482     if ((*SI)->isEHPad() || *SI == TBB)
 483       continue;
 484     assert(!FallthroughBB && "Found more than one fallthrough successor.");
 485     FallthroughBB = *SI;
 486   }
 487
 488   if (!FallthroughBB) {
 489     if (canFallThrough()) {
 490       // We fallthrough to the same basic block as the conditional jump targets.
 491       // Remove the conditional jump, leaving unconditional fallthrough.
 492       // FIXME: This does not seem like a reasonable pattern to support, but it
 493       // has been seen in the wild coming out of degenerate ARM test cases.
 494       TII->removeBranch(*this);
 495
 496       // Finally update the unconditional successor to be reached via a branch if
 497       // it would not be reached by fallthrough.
 498       if (!isLayoutSuccessor(TBB))
 499         TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 500       return;
 501     }
 502
 503     // We enter here iff exactly one successor is TBB which cannot fallthrough
 504     // and the rest successors if any are EHPads.  In this case, we need to
 505     // change the conditional branch into unconditional branch.
 506     TII->removeBranch(*this);
 507     Cond.clear();
 508     TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 509     return;
 510   }
 511
 512   // The block has a fallthrough conditional branch.
 513   if (isLayoutSuccessor(TBB)) {
 514     if (TII->reverseBranchCondition(Cond)) {
 515       // We can't reverse the condition, add an unconditional branch.
 516       Cond.clear();
 517       TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
 518       return;
 519     }
 520     TII->removeBranch(*this);
 521     TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
 522   } else if (!isLayoutSuccessor(FallthroughBB)) {
 523     TII->removeBranch(*this);
 524     TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
 525   }
 526 }
 527
 528 void MachineBasicBlock::validateSuccProbs() const {
 529 #ifndef NDEBUG
 530   int64_t Sum = 0;
 531   for (auto Prob : Probs)
 532     Sum += Prob.getNumerator();
 533   // Due to precision issue, we assume that the sum of probabilities is one if
 534   // the difference between the sum of their numerators and the denominator is
 535   // no greater than the number of successors.
 536   assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
 537              Probs.size() &&
 538          "The sum of successors's probabilities exceeds one.");
 539 #endif // NDEBUG
 540 }
 541
 542 void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
 543                                      BranchProbability Prob) {
 544   // Probability list is either empty (if successor list isn't empty, this means
 545   // disabled optimization) or has the same size as successor list.
 546   if (!(Probs.empty() && !Successors.empty()))
 547     Probs.push_back(Prob);
 548   Successors.push_back(Succ);
 549   Succ->addPredecessor(this);
 550 }
 551
 552 void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
 553   // We need to make sure probability list is either empty or has the same size
 554   // of successor list. When this function is called, we can safely delete all
 555   // probability in the list.
 556   Probs.clear();
 557   Successors.push_back(Succ);
 558   Succ->addPredecessor(this);
 559 }
 560
 561 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
 562                                         bool NormalizeSuccProbs) {
 563   succ_iterator I = find(Successors, Succ);
 564   removeSuccessor(I, NormalizeSuccProbs);
 565 }
 566
 567 MachineBasicBlock::succ_iterator
 568 MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
 569   assert(I != Successors.end() && "Not a current successor!");
 570
 571   // If probability list is empty it means we don't use it (disabled
 572   // optimization).
 573   if (!Probs.empty()) {
 574     probability_iterator WI = getProbabilityIterator(I);
 575     Probs.erase(WI);
 576     if (NormalizeSuccProbs)
 577       normalizeSuccProbs();
 578   }
 579
 580   (*I)->removePredecessor(this);
 581   return Successors.erase(I);
 582 }
 583
 584 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
 585                                          MachineBasicBlock *New) {
 586   if (Old == New)
 587     return;
 588
 589   succ_iterator E = succ_end();
 590   succ_iterator NewI = E;
 591   succ_iterator OldI = E;
 592   for (succ_iterator I = succ_begin(); I != E; ++I) {
 593     if (*I == Old) {
 594       OldI = I;
 595       if (NewI != E)
 596         break;
 597     }
 598     if (*I == New) {
 599       NewI = I;
 600       if (OldI != E)
 601         break;
 602     }
 603   }
 604   assert(OldI != E && "Old is not a successor of this block");
 605
 606   // If New isn't already a successor, let it take Old's place.
 607   if (NewI == E) {
 608     Old->removePredecessor(this);
 609     New->addPredecessor(this);
 610     *OldI = New;
 611     return;
 612   }
 613
 614   // New is already a successor.
 615   // Update its probability instead of adding a duplicate edge.
 616   if (!Probs.empty()) {
 617     auto ProbIter = getProbabilityIterator(NewI);
 618     if (!ProbIter->isUnknown())
 619       *ProbIter += *getProbabilityIterator(OldI);
 620   }
 621   removeSuccessor(OldI);
 622 }
 623
 624 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
 625   Predecessors.push_back(Pred);
 626 }
 627
 628 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
 629   pred_iterator I = find(Predecessors, Pred);
 630   assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
 631   Predecessors.erase(I);
 632 }
 633
 634 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
 635   if (this == FromMBB)
 636     return;
 637
 638   while (!FromMBB->succ_empty()) {
 639     MachineBasicBlock *Succ = *FromMBB->succ_begin();
 640
 641     // If probability list is empty it means we don't use it (disabled optimization).
 642     if (!FromMBB->Probs.empty()) {
 643       auto Prob = *FromMBB->Probs.begin();
 644       addSuccessor(Succ, Prob);
 645     } else
 646       addSuccessorWithoutProb(Succ);
 647
 648     FromMBB->removeSuccessor(Succ);
 649   }
 650 }
 651
 652 void
 653 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
 654   if (this == FromMBB)
 655     return;
 656
 657   while (!FromMBB->succ_empty()) {
 658     MachineBasicBlock *Succ = *FromMBB->succ_begin();
 659     if (!FromMBB->Probs.empty()) {
 660       auto Prob = *FromMBB->Probs.begin();
 661       addSuccessor(Succ, Prob);
 662     } else
 663       addSuccessorWithoutProb(Succ);
 664     FromMBB->removeSuccessor(Succ);
 665
 666     // Fix up any PHI nodes in the successor.
 667     for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(),
 668            ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
 669       for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
 670         MachineOperand &MO = MI->getOperand(i);
 671         if (MO.getMBB() == FromMBB)
 672           MO.setMBB(this);
 673       }
 674   }
 675   normalizeSuccProbs();
 676 }
 677
 678 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
 679   return is_contained(predecessors(), MBB);
 680 }
 681
 682 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
 683   return is_contained(successors(), MBB);
 684 }
 685
 686 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
 687   MachineFunction::const_iterator I(this);
 688   return std::next(I) == MachineFunction::const_iterator(MBB);
 689 }
 690
 691 MachineBasicBlock *MachineBasicBlock::getFallThrough() {
 692   MachineFunction::iterator Fallthrough = getIterator();
 693   ++Fallthrough;
 694   // If FallthroughBlock is off the end of the function, it can't fall through.
 695   if (Fallthrough == getParent()->end())
 696     return nullptr;
 697
 698   // If FallthroughBlock isn't a successor, no fallthrough is possible.
 699   if (!isSuccessor(&*Fallthrough))
 700     return nullptr;
 701
 702   // Analyze the branches, if any, at the end of the block.
 703   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 704   SmallVector<MachineOperand, 4> Cond;
 705   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 706   if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
 707     // If we couldn't analyze the branch, examine the last instruction.
 708     // If the block doesn't end in a known control barrier, assume fallthrough
 709     // is possible. The isPredicated check is needed because this code can be
 710     // called during IfConversion, where an instruction which is normally a
 711     // Barrier is predicated and thus no longer an actual control barrier.
 712     return (empty() || !back().isBarrier() || TII->isPredicated(back()))
 713                ? &*Fallthrough
 714                : nullptr;
 715   }
 716
 717   // If there is no branch, control always falls through.
 718   if (!TBB) return &*Fallthrough;
 719
 720   // If there is some explicit branch to the fallthrough block, it can obviously
 721   // reach, even though the branch should get folded to fall through implicitly.
 722   if (MachineFunction::iterator(TBB) == Fallthrough ||
 723       MachineFunction::iterator(FBB) == Fallthrough)
 724     return &*Fallthrough;
 725
 726   // If it's an unconditional branch to some block not the fall through, it
 727   // doesn't fall through.
 728   if (Cond.empty()) return nullptr;
 729
 730   // Otherwise, if it is conditional and has no explicit false block, it falls
 731   // through.
 732   return (FBB == nullptr) ? &*Fallthrough : nullptr;
 733 }
 734
 735 bool MachineBasicBlock::canFallThrough() {
 736   return getFallThrough() != nullptr;
 737 }
 738
 739 MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ,
 740                                                         Pass &P) {
 741   if (!canSplitCriticalEdge(Succ))
 742     return nullptr;
 743
 744   MachineFunction *MF = getParent();
 745   DebugLoc DL;  // FIXME: this is nowhere
 746
 747   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
 748   MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
 749   DEBUG(dbgs() << "Splitting critical edge:"
 750         " BB#" << getNumber()
 751         << " -- BB#" << NMBB->getNumber()
 752         << " -- BB#" << Succ->getNumber() << '\n');
 753
 754   LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
 755   SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
 756   if (LIS)
 757     LIS->insertMBBInMaps(NMBB);
 758   else if (Indexes)
 759     Indexes->insertMBBInMaps(NMBB);
 760
 761   // On some targets like Mips, branches may kill virtual registers. Make sure
 762   // that LiveVariables is properly updated after updateTerminator replaces the
 763   // terminators.
 764   LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
 765
 766   // Collect a list of virtual registers killed by the terminators.
 767   SmallVector<unsigned, 4> KilledRegs;
 768   if (LV)
 769     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 770          I != E; ++I) {
 771       MachineInstr *MI = &*I;
 772       for (MachineInstr::mop_iterator OI = MI->operands_begin(),
 773            OE = MI->operands_end(); OI != OE; ++OI) {
 774         if (!OI->isReg() || OI->getReg() == 0 ||
 775             !OI->isUse() || !OI->isKill() || OI->isUndef())
 776           continue;
 777         unsigned Reg = OI->getReg();
 778         if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
 779             LV->getVarInfo(Reg).removeKill(*MI)) {
 780           KilledRegs.push_back(Reg);
 781           DEBUG(dbgs() << "Removing terminator kill: " << *MI);
 782           OI->setIsKill(false);
 783         }
 784       }
 785     }
 786
 787   SmallVector<unsigned, 4> UsedRegs;
 788   if (LIS) {
 789     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 790          I != E; ++I) {
 791       MachineInstr *MI = &*I;
 792
 793       for (MachineInstr::mop_iterator OI = MI->operands_begin(),
 794            OE = MI->operands_end(); OI != OE; ++OI) {
 795         if (!OI->isReg() || OI->getReg() == 0)
 796           continue;
 797
 798         unsigned Reg = OI->getReg();
 799         if (!is_contained(UsedRegs, Reg))
 800           UsedRegs.push_back(Reg);
 801       }
 802     }
 803   }
 804
 805   ReplaceUsesOfBlockWith(Succ, NMBB);
 806
 807   // If updateTerminator() removes instructions, we need to remove them from
 808   // SlotIndexes.
 809   SmallVector<MachineInstr*, 4> Terminators;
 810   if (Indexes) {
 811     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 812          I != E; ++I)
 813       Terminators.push_back(&*I);
 814   }
 815
 816   updateTerminator();
 817
 818   if (Indexes) {
 819     SmallVector<MachineInstr*, 4> NewTerminators;
 820     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 821          I != E; ++I)
 822       NewTerminators.push_back(&*I);
 823
 824     for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
 825         E = Terminators.end(); I != E; ++I) {
 826       if (!is_contained(NewTerminators, *I))
 827         Indexes->removeMachineInstrFromMaps(**I);
 828     }
 829   }
 830
 831   // Insert unconditional "jump Succ" instruction in NMBB if necessary.
 832   NMBB->addSuccessor(Succ);
 833   if (!NMBB->isLayoutSuccessor(Succ)) {
 834     SmallVector<MachineOperand, 4> Cond;
 835     const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 836     TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
 837
 838     if (Indexes) {
 839       for (MachineInstr &MI : NMBB->instrs()) {
 840         // Some instructions may have been moved to NMBB by updateTerminator(),
 841         // so we first remove any instruction that already has an index.
 842         if (Indexes->hasIndex(MI))
 843           Indexes->removeMachineInstrFromMaps(MI);
 844         Indexes->insertMachineInstrInMaps(MI);
 845       }
 846     }
 847   }
 848
 849   // Fix PHI nodes in Succ so they refer to NMBB instead of this
 850   for (MachineBasicBlock::instr_iterator
 851          i = Succ->instr_begin(),e = Succ->instr_end();
 852        i != e && i->isPHI(); ++i)
 853     for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
 854       if (i->getOperand(ni+1).getMBB() == this)
 855         i->getOperand(ni+1).setMBB(NMBB);
 856
 857   // Inherit live-ins from the successor
 858   for (const auto &LI : Succ->liveins())
 859     NMBB->addLiveIn(LI);
 860
 861   // Update LiveVariables.
 862   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
 863   if (LV) {
 864     // Restore kills of virtual registers that were killed by the terminators.
 865     while (!KilledRegs.empty()) {
 866       unsigned Reg = KilledRegs.pop_back_val();
 867       for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
 868         if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
 869           continue;
 870         if (TargetRegisterInfo::isVirtualRegister(Reg))
 871           LV->getVarInfo(Reg).Kills.push_back(&*I);
 872         DEBUG(dbgs() << "Restored terminator kill: " << *I);
 873         break;
 874       }
 875     }
 876     // Update relevant live-through information.
 877     LV->addNewBlock(NMBB, this, Succ);
 878   }
 879
 880   if (LIS) {
 881     // After splitting the edge and updating SlotIndexes, live intervals may be
 882     // in one of two situations, depending on whether this block was the last in
 883     // the function. If the original block was the last in the function, all
 884     // live intervals will end prior to the beginning of the new split block. If
 885     // the original block was not at the end of the function, all live intervals
 886     // will extend to the end of the new split block.
 887
 888     bool isLastMBB =
 889       std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
 890
 891     SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
 892     SlotIndex PrevIndex = StartIndex.getPrevSlot();
 893     SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
 894
 895     // Find the registers used from NMBB in PHIs in Succ.
 896     SmallSet<unsigned, 8> PHISrcRegs;
 897     for (MachineBasicBlock::instr_iterator
 898          I = Succ->instr_begin(), E = Succ->instr_end();
 899          I != E && I->isPHI(); ++I) {
 900       for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
 901         if (I->getOperand(ni+1).getMBB() == NMBB) {
 902           MachineOperand &MO = I->getOperand(ni);
 903           unsigned Reg = MO.getReg();
 904           PHISrcRegs.insert(Reg);
 905           if (MO.isUndef())
 906             continue;
 907
 908           LiveInterval &LI = LIS->getInterval(Reg);
 909           VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
 910           assert(VNI &&
 911                  "PHI sources should be live out of their predecessors.");
 912           LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
 913         }
 914       }
 915     }
 916
 917     MachineRegisterInfo *MRI = &getParent()->getRegInfo();
 918     for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 919       unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 920       if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
 921         continue;
 922
 923       LiveInterval &LI = LIS->getInterval(Reg);
 924       if (!LI.liveAt(PrevIndex))
 925         continue;
 926
 927       bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
 928       if (isLiveOut && isLastMBB) {
 929         VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
 930         assert(VNI && "LiveInterval should have VNInfo where it is live.");
 931         LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
 932       } else if (!isLiveOut && !isLastMBB) {
 933         LI.removeSegment(StartIndex, EndIndex);
 934       }
 935     }
 936
 937     // Update all intervals for registers whose uses may have been modified by
 938     // updateTerminator().
 939     LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
 940   }
 941
 942   if (MachineDominatorTree *MDT =
 943           P.getAnalysisIfAvailable<MachineDominatorTree>())
 944     MDT->recordSplitCriticalEdge(this, Succ, NMBB);
 945
 946   if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
 947     if (MachineLoop *TIL = MLI->getLoopFor(this)) {
 948       // If one or the other blocks were not in a loop, the new block is not
 949       // either, and thus LI doesn't need to be updated.
 950       if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
 951         if (TIL == DestLoop) {
 952           // Both in the same loop, the NMBB joins loop.
 953           DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
 954         } else if (TIL->contains(DestLoop)) {
 955           // Edge from an outer loop to an inner loop.  Add to the outer loop.
 956           TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
 957         } else if (DestLoop->contains(TIL)) {
 958           // Edge from an inner loop to an outer loop.  Add to the outer loop.
 959           DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
 960         } else {
 961           // Edge from two loops with no containment relation.  Because these
 962           // are natural loops, we know that the destination block must be the
 963           // header of its loop (adding a branch into a loop elsewhere would
 964           // create an irreducible loop).
 965           assert(DestLoop->getHeader() == Succ &&
 966                  "Should not create irreducible loops!");
 967           if (MachineLoop *P = DestLoop->getParentLoop())
 968             P->addBasicBlockToLoop(NMBB, MLI->getBase());
 969         }
 970       }
 971     }
 972
 973   return NMBB;
 974 }
 975
 976 bool MachineBasicBlock::canSplitCriticalEdge(
 977     const MachineBasicBlock *Succ) const {
 978   // Splitting the critical edge to a landing pad block is non-trivial. Don't do
 979   // it in this generic function.
 980   if (Succ->isEHPad())
 981     return false;
 982
 983   const MachineFunction *MF = getParent();
 984
 985   // Performance might be harmed on HW that implements branching using exec mask
 986   // where both sides of the branches are always executed.
 987   if (MF->getTarget().requiresStructuredCFG())
 988     return false;
 989
 990   // We may need to update this's terminator, but we can't do that if
 991   // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
 992   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
 993   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 994   SmallVector<MachineOperand, 4> Cond;
 995   // AnalyzeBanch should modify this, since we did not allow modification.
 996   if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
 997                          /*AllowModify*/ false))
 998     return false;
 999
1000   // Avoid bugpoint weirdness: A block may end with a conditional branch but
1001   // jumps to the same MBB is either case. We have duplicate CFG edges in that
1002   // case that we can't handle. Since this never happens in properly optimized
1003   // code, just skip those edges.
1004   if (TBB && TBB == FBB) {
1005     DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
1006                  << getNumber() << '\n');
1007     return false;
1008   }
1009   return true;
1010 }
1011
1012 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1013 /// neighboring instructions so the bundle won't be broken by removing MI.
1014 static void unbundleSingleMI(MachineInstr *MI) {
1015   // Removing the first instruction in a bundle.
1016   if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1017     MI->unbundleFromSucc();
1018   // Removing the last instruction in a bundle.
1019   if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1020     MI->unbundleFromPred();
1021   // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1022   // are already fine.
1023 }
1024
1025 MachineBasicBlock::instr_iterator
1026 MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1027   unbundleSingleMI(&*I);
1028   return Insts.erase(I);
1029 }
1030
1031 MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1032   unbundleSingleMI(MI);
1033   MI->clearFlag(MachineInstr::BundledPred);
1034   MI->clearFlag(MachineInstr::BundledSucc);
1035   return Insts.remove(MI);
1036 }
1037
1038 MachineBasicBlock::instr_iterator
1039 MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
1040   assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1041          "Cannot insert instruction with bundle flags");
1042   // Set the bundle flags when inserting inside a bundle.
1043   if (I != instr_end() && I->isBundledWithPred()) {
1044     MI->setFlag(MachineInstr::BundledPred);
1045     MI->setFlag(MachineInstr::BundledSucc);
1046   }
1047   return Insts.insert(I, MI);
1048 }
1049
1050 /// This method unlinks 'this' from the containing function, and returns it, but
1051 /// does not delete it.
1052 MachineBasicBlock *MachineBasicBlock::removeFromParent() {
1053   assert(getParent() && "Not embedded in a function!");
1054   getParent()->remove(this);
1055   return this;
1056 }
1057
1058 /// This method unlinks 'this' from the containing function, and deletes it.
1059 void MachineBasicBlock::eraseFromParent() {
1060   assert(getParent() && "Not embedded in a function!");
1061   getParent()->erase(this);
1062 }
1063
1064 /// Given a machine basic block that branched to 'Old', change the code and CFG
1065 /// so that it branches to 'New' instead.
1066 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1067                                                MachineBasicBlock *New) {
1068   assert(Old != New && "Cannot replace self with self!");
1069
1070   MachineBasicBlock::instr_iterator I = instr_end();
1071   while (I != instr_begin()) {
1072     --I;
1073     if (!I->isTerminator()) break;
1074
1075     // Scan the operands of this machine instruction, replacing any uses of Old
1076     // with New.
1077     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1078       if (I->getOperand(i).isMBB() &&
1079           I->getOperand(i).getMBB() == Old)
1080         I->getOperand(i).setMBB(New);
1081   }
1082
1083   // Update the successor information.
1084   replaceSuccessor(Old, New);
1085 }
1086
1087 /// Various pieces of code can cause excess edges in the CFG to be inserted.  If
1088 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1089 /// MBB successors from the CFG.  DestA and DestB can be null.
1090 ///
1091 /// Besides DestA and DestB, retain other edges leading to LandingPads
1092 /// (currently there can be only one; we don't check or require that here).
1093 /// Note it is possible that DestA and/or DestB are LandingPads.
1094 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
1095                                              MachineBasicBlock *DestB,
1096                                              bool IsCond) {
1097   // The values of DestA and DestB frequently come from a call to the
1098   // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1099   // values from there.
1100   //
1101   // 1. If both DestA and DestB are null, then the block ends with no branches
1102   //    (it falls through to its successor).
1103   // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1104   //    with only an unconditional branch.
1105   // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1106   //    with a conditional branch that falls through to a successor (DestB).
1107   // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1108   //    conditional branch followed by an unconditional branch. DestA is the
1109   //    'true' destination and DestB is the 'false' destination.
1110
1111   bool Changed = false;
1112
1113   MachineBasicBlock *FallThru = getNextNode();
1114
1115   if (!DestA && !DestB) {
1116     // Block falls through to successor.
1117     DestA = FallThru;
1118     DestB = FallThru;
1119   } else if (DestA && !DestB) {
1120     if (IsCond)
1121       // Block ends in conditional jump that falls through to successor.
1122       DestB = FallThru;
1123   } else {
1124     assert(DestA && DestB && IsCond &&
1125            "CFG in a bad state. Cannot correct CFG edges");
1126   }
1127
1128   // Remove superfluous edges. I.e., those which aren't destinations of this
1129   // basic block, duplicate edges, or landing pads.
1130   SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
1131   MachineBasicBlock::succ_iterator SI = succ_begin();
1132   while (SI != succ_end()) {
1133     const MachineBasicBlock *MBB = *SI;
1134     if (!SeenMBBs.insert(MBB).second ||
1135         (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1136       // This is a superfluous edge, remove it.
1137       SI = removeSuccessor(SI);
1138       Changed = true;
1139     } else {
1140       ++SI;
1141     }
1142   }
1143
1144   if (Changed)
1145     normalizeSuccProbs();
1146   return Changed;
1147 }
1148
1149 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1150 /// instructions.  Return UnknownLoc if there is none.
1151 DebugLoc
1152 MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
1153   // Skip debug declarations, we don't want a DebugLoc from them.
1154   MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1155   if (MBBI != instr_end())
1156     return MBBI->getDebugLoc();
1157   return {};
1158 }
1159
1160 /// Find and return the merged DebugLoc of the branch instructions of the block.
1161 /// Return UnknownLoc if there is none.
1162 DebugLoc
1163 MachineBasicBlock::findBranchDebugLoc() {
1164   DebugLoc DL;
1165   auto TI = getFirstTerminator();
1166   while (TI != end() && !TI->isBranch())
1167     ++TI;
1168
1169   if (TI != end()) {
1170     DL = TI->getDebugLoc();
1171     for (++TI ; TI != end() ; ++TI)
1172       if (TI->isBranch())
1173         DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1174   }
1175   return DL;
1176 }
1177
1178 /// Return probability of the edge from this block to MBB.
1179 BranchProbability
1180 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1181   if (Probs.empty())
1182     return BranchProbability(1, succ_size());
1183
1184   const auto &Prob = *getProbabilityIterator(Succ);
1185   if (Prob.isUnknown()) {
1186     // For unknown probabilities, collect the sum of all known ones, and evenly
1187     // ditribute the complemental of the sum to each unknown probability.
1188     unsigned KnownProbNum = 0;
1189     auto Sum = BranchProbability::getZero();
1190     for (auto &P : Probs) {
1191       if (!P.isUnknown()) {
1192         Sum += P;
1193         KnownProbNum++;
1194       }
1195     }
1196     return Sum.getCompl() / (Probs.size() - KnownProbNum);
1197   } else
1198     return Prob;
1199 }
1200
1201 /// Set successor probability of a given iterator.
1202 void MachineBasicBlock::setSuccProbability(succ_iterator I,
1203                                            BranchProbability Prob) {
1204   assert(!Prob.isUnknown());
1205   if (Probs.empty())
1206     return;
1207   *getProbabilityIterator(I) = Prob;
1208 }
1209
1210 /// Return probability iterator corresonding to the I successor iterator
1211 MachineBasicBlock::const_probability_iterator
1212 MachineBasicBlock::getProbabilityIterator(
1213     MachineBasicBlock::const_succ_iterator I) const {
1214   assert(Probs.size() == Successors.size() && "Async probability list!");
1215   const size_t index = std::distance(Successors.begin(), I);
1216   assert(index < Probs.size() && "Not a current successor!");
1217   return Probs.begin() + index;
1218 }
1219
1220 /// Return probability iterator corresonding to the I successor iterator.
1221 MachineBasicBlock::probability_iterator
1222 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1223   assert(Probs.size() == Successors.size() && "Async probability list!");
1224   const size_t index = std::distance(Successors.begin(), I);
1225   assert(index < Probs.size() && "Not a current successor!");
1226   return Probs.begin() + index;
1227 }
1228
1229 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1230 /// as of just before "MI".
1231 ///
1232 /// Search is localised to a neighborhood of
1233 /// Neighborhood instructions before (searching for defs or kills) and N
1234 /// instructions after (searching just for defs) MI.
1235 MachineBasicBlock::LivenessQueryResult
1236 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
1237                                            unsigned Reg, const_iterator Before,
1238                                            unsigned Neighborhood) const {
1239   unsigned N = Neighborhood;
1240
1241   // Start by searching backwards from Before, looking for kills, reads or defs.
1242   const_iterator I(Before);
1243   // If this is the first insn in the block, don't search backwards.
1244   if (I != begin()) {
1245     do {
1246       --I;
1247
1248       MachineOperandIteratorBase::PhysRegInfo Info =
1249           ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1250
1251       // Defs happen after uses so they take precedence if both are present.
1252
1253       // Register is dead after a dead def of the full register.
1254       if (Info.DeadDef)
1255         return LQR_Dead;
1256       // Register is (at least partially) live after a def.
1257       if (Info.Defined) {
1258         if (!Info.PartialDeadDef)
1259           return LQR_Live;
1260         // As soon as we saw a partial definition (dead or not),
1261         // we cannot tell if the value is partial live without
1262         // tracking the lanemasks. We are not going to do this,
1263         // so fall back on the remaining of the analysis.
1264         break;
1265       }
1266       // Register is dead after a full kill or clobber and no def.
1267       if (Info.Killed || Info.Clobbered)
1268         return LQR_Dead;
1269       // Register must be live if we read it.
1270       if (Info.Read)
1271         return LQR_Live;
1272     } while (I != begin() && --N > 0);
1273   }
1274
1275   // Did we get to the start of the block?
1276   if (I == begin()) {
1277     // If so, the register's state is definitely defined by the live-in state.
1278     for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1279          ++RAI)
1280       if (isLiveIn(*RAI))
1281         return LQR_Live;
1282
1283     return LQR_Dead;
1284   }
1285
1286   N = Neighborhood;
1287
1288   // Try searching forwards from Before, looking for reads or defs.
1289   I = const_iterator(Before);
1290   // If this is the last insn in the block, don't search forwards.
1291   if (I != end()) {
1292     for (++I; I != end() && N > 0; ++I, --N) {
1293       MachineOperandIteratorBase::PhysRegInfo Info =
1294           ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1295
1296       // Register is live when we read it here.
1297       if (Info.Read)
1298         return LQR_Live;
1299       // Register is dead if we can fully overwrite or clobber it here.
1300       if (Info.FullyDefined || Info.Clobbered)
1301         return LQR_Dead;
1302     }
1303   }
1304
1305   // At this point we have no idea of the liveness of the register.
1306   return LQR_Unknown;
1307 }
1308
1309 const uint32_t *
1310 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1311   // EH funclet entry does not preserve any registers.
1312   return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1313 }
1314
1315 const uint32_t *
1316 MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
1317   // If we see a return block with successors, this must be a funclet return,
1318   // which does not preserve any registers. If there are no successors, we don't
1319   // care what kind of return it is, putting a mask after it is a no-op.
1320   return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1321 }
1322
1323 void MachineBasicBlock::clearLiveIns() {
1324   LiveIns.clear();
1325 }
1326
1327 MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
1328   assert(getParent()->getProperties().hasProperty(
1329       MachineFunctionProperties::Property::TracksLiveness) &&
1330       "Liveness information is accurate");
1331   return LiveIns.begin();
1332 }