LLVM  mainline
MachineBasicBlock.cpp
Go to the documentation of this file.
00001 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Collect the sequence of machine instructions for a basic block.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/CodeGen/MachineBasicBlock.h"
00015 #include "llvm/ADT/SmallPtrSet.h"
00016 #include "llvm/ADT/SmallString.h"
00017 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
00018 #include "llvm/CodeGen/LiveVariables.h"
00019 #include "llvm/CodeGen/MachineDominators.h"
00020 #include "llvm/CodeGen/MachineFunction.h"
00021 #include "llvm/CodeGen/MachineInstrBuilder.h"
00022 #include "llvm/CodeGen/MachineLoopInfo.h"
00023 #include "llvm/CodeGen/MachineRegisterInfo.h"
00024 #include "llvm/CodeGen/SlotIndexes.h"
00025 #include "llvm/IR/BasicBlock.h"
00026 #include "llvm/IR/DataLayout.h"
00027 #include "llvm/IR/ModuleSlotTracker.h"
00028 #include "llvm/MC/MCAsmInfo.h"
00029 #include "llvm/MC/MCContext.h"
00030 #include "llvm/Support/DataTypes.h"
00031 #include "llvm/Support/Debug.h"
00032 #include "llvm/Support/raw_ostream.h"
00033 #include "llvm/Target/TargetInstrInfo.h"
00034 #include "llvm/Target/TargetMachine.h"
00035 #include "llvm/Target/TargetRegisterInfo.h"
00036 #include "llvm/Target/TargetSubtargetInfo.h"
00037 #include <algorithm>
00038 using namespace llvm;
00039 
00040 #define DEBUG_TYPE "codegen"
00041 
00042 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
00043     : BB(B), Number(-1), xParent(&MF) {
00044   Insts.Parent = this;
00045 }
00046 
00047 MachineBasicBlock::~MachineBasicBlock() {
00048 }
00049 
00050 /// Return the MCSymbol for this basic block.
00051 MCSymbol *MachineBasicBlock::getSymbol() const {
00052   if (!CachedMCSymbol) {
00053     const MachineFunction *MF = getParent();
00054     MCContext &Ctx = MF->getContext();
00055     const char *Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
00056     assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
00057     CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
00058                                            Twine(MF->getFunctionNumber()) +
00059                                            "_" + Twine(getNumber()));
00060   }
00061 
00062   return CachedMCSymbol;
00063 }
00064 
00065 
00066 raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
00067   MBB.print(OS);
00068   return OS;
00069 }
00070 
00071 /// When an MBB is added to an MF, we need to update the parent pointer of the
00072 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
00073 /// operand list for registers.
00074 ///
00075 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
00076 /// gets the next available unique MBB number. If it is removed from a
00077 /// MachineFunction, it goes back to being #-1.
00078 void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock *N) {
00079   MachineFunction &MF = *N->getParent();
00080   N->Number = MF.addToMBBNumbering(N);
00081 
00082   // Make sure the instructions have their operands in the reginfo lists.
00083   MachineRegisterInfo &RegInfo = MF.getRegInfo();
00084   for (MachineBasicBlock::instr_iterator
00085          I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
00086     I->AddRegOperandsToUseLists(RegInfo);
00087 }
00088 
00089 void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock *N) {
00090   N->getParent()->removeFromMBBNumbering(N->Number);
00091   N->Number = -1;
00092 }
00093 
00094 /// When we add an instruction to a basic block list, we update its parent
00095 /// pointer and add its operands from reg use/def lists if appropriate.
00096 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
00097   assert(!N->getParent() && "machine instruction already in a basic block");
00098   N->setParent(Parent);
00099 
00100   // Add the instruction's register operands to their corresponding
00101   // use/def lists.
00102   MachineFunction *MF = Parent->getParent();
00103   N->AddRegOperandsToUseLists(MF->getRegInfo());
00104 }
00105 
00106 /// When we remove an instruction from a basic block list, we update its parent
00107 /// pointer and remove its operands from reg use/def lists if appropriate.
00108 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {
00109   assert(N->getParent() && "machine instruction not in a basic block");
00110 
00111   // Remove from the use/def lists.
00112   if (MachineFunction *MF = N->getParent()->getParent())
00113     N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
00114 
00115   N->setParent(nullptr);
00116 }
00117 
00118 /// When moving a range of instructions from one MBB list to another, we need to
00119 /// update the parent pointers and the use/def lists.
00120 void ilist_traits<MachineInstr>::
00121 transferNodesFromList(ilist_traits<MachineInstr> &FromList,
00122                       ilist_iterator<MachineInstr> First,
00123                       ilist_iterator<MachineInstr> Last) {
00124   assert(Parent->getParent() == FromList.Parent->getParent() &&
00125         "MachineInstr parent mismatch!");
00126 
00127   // Splice within the same MBB -> no change.
00128   if (Parent == FromList.Parent) return;
00129 
00130   // If splicing between two blocks within the same function, just update the
00131   // parent pointers.
00132   for (; First != Last; ++First)
00133     First->setParent(Parent);
00134 }
00135 
00136 void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) {
00137   assert(!MI->getParent() && "MI is still in a block!");
00138   Parent->getParent()->DeleteMachineInstr(MI);
00139 }
00140 
00141 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
00142   instr_iterator I = instr_begin(), E = instr_end();
00143   while (I != E && I->isPHI())
00144     ++I;
00145   assert((I == E || !I->isInsideBundle()) &&
00146          "First non-phi MI cannot be inside a bundle!");
00147   return I;
00148 }
00149 
00150 MachineBasicBlock::iterator
00151 MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
00152   iterator E = end();
00153   while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue()))
00154     ++I;
00155   // FIXME: This needs to change if we wish to bundle labels / dbg_values
00156   // inside the bundle.
00157   assert((I == E || !I->isInsideBundle()) &&
00158          "First non-phi / non-label instruction is inside a bundle!");
00159   return I;
00160 }
00161 
00162 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
00163   iterator B = begin(), E = end(), I = E;
00164   while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
00165     ; /*noop */
00166   while (I != E && !I->isTerminator())
00167     ++I;
00168   return I;
00169 }
00170 
00171 MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
00172   instr_iterator B = instr_begin(), E = instr_end(), I = E;
00173   while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
00174     ; /*noop */
00175   while (I != E && !I->isTerminator())
00176     ++I;
00177   return I;
00178 }
00179 
00180 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() {
00181   // Skip over begin-of-block dbg_value instructions.
00182   iterator I = begin(), E = end();
00183   while (I != E && I->isDebugValue())
00184     ++I;
00185   return I;
00186 }
00187 
00188 MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() {
00189   // Skip over end-of-block dbg_value instructions.
00190   instr_iterator B = instr_begin(), I = instr_end();
00191   while (I != B) {
00192     --I;
00193     // Return instruction that starts a bundle.
00194     if (I->isDebugValue() || I->isInsideBundle())
00195       continue;
00196     return I;
00197   }
00198   // The block is all debug values.
00199   return end();
00200 }
00201 
00202 const MachineBasicBlock *MachineBasicBlock::getLandingPadSuccessor() const {
00203   // A block with a landing pad successor only has one other successor.
00204   if (succ_size() > 2)
00205     return nullptr;
00206   for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
00207     if ((*I)->isEHPad())
00208       return *I;
00209   return nullptr;
00210 }
00211 
00212 bool MachineBasicBlock::hasEHPadSuccessor() const {
00213   for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
00214     if ((*I)->isEHPad())
00215       return true;
00216   return false;
00217 }
00218 
00219 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
00220 void MachineBasicBlock::dump() const {
00221   print(dbgs());
00222 }
00223 #endif
00224 
00225 StringRef MachineBasicBlock::getName() const {
00226   if (const BasicBlock *LBB = getBasicBlock())
00227     return LBB->getName();
00228   else
00229     return "(null)";
00230 }
00231 
00232 /// Return a hopefully unique identifier for this block.
00233 std::string MachineBasicBlock::getFullName() const {
00234   std::string Name;
00235   if (getParent())
00236     Name = (getParent()->getName() + ":").str();
00237   if (getBasicBlock())
00238     Name += getBasicBlock()->getName();
00239   else
00240     Name += ("BB" + Twine(getNumber())).str();
00241   return Name;
00242 }
00243 
00244 void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const {
00245   const MachineFunction *MF = getParent();
00246   if (!MF) {
00247     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
00248        << " is null\n";
00249     return;
00250   }
00251   const Function *F = MF->getFunction();
00252   const Module *M = F ? F->getParent() : nullptr;
00253   ModuleSlotTracker MST(M);
00254   print(OS, MST, Indexes);
00255 }
00256 
00257 void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
00258                               SlotIndexes *Indexes) const {
00259   const MachineFunction *MF = getParent();
00260   if (!MF) {
00261     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
00262        << " is null\n";
00263     return;
00264   }
00265 
00266   if (Indexes)
00267     OS << Indexes->getMBBStartIdx(this) << '\t';
00268 
00269   OS << "BB#" << getNumber() << ": ";
00270 
00271   const char *Comma = "";
00272   if (const BasicBlock *LBB = getBasicBlock()) {
00273     OS << Comma << "derived from LLVM BB ";
00274     LBB->printAsOperand(OS, /*PrintType=*/false, MST);
00275     Comma = ", ";
00276   }
00277   if (isEHPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; }
00278   if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; }
00279   if (Alignment)
00280     OS << Comma << "Align " << Alignment << " (" << (1u << Alignment)
00281        << " bytes)";
00282 
00283   OS << '\n';
00284 
00285   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
00286   if (!livein_empty()) {
00287     if (Indexes) OS << '\t';
00288     OS << "    Live Ins:";
00289     for (const auto &LI : make_range(livein_begin(), livein_end())) {
00290       OS << ' ' << PrintReg(LI.PhysReg, TRI);
00291       if (LI.LaneMask != ~0u)
00292         OS << ':' << PrintLaneMask(LI.LaneMask);
00293     }
00294     OS << '\n';
00295   }
00296   // Print the preds of this block according to the CFG.
00297   if (!pred_empty()) {
00298     if (Indexes) OS << '\t';
00299     OS << "    Predecessors according to CFG:";
00300     for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
00301       OS << " BB#" << (*PI)->getNumber();
00302     OS << '\n';
00303   }
00304 
00305   for (const_instr_iterator I = instr_begin(); I != instr_end(); ++I) {
00306     if (Indexes) {
00307       if (Indexes->hasIndex(&*I))
00308         OS << Indexes->getInstructionIndex(&*I);
00309       OS << '\t';
00310     }
00311     OS << '\t';
00312     if (I->isInsideBundle())
00313       OS << "  * ";
00314     I->print(OS, MST);
00315   }
00316 
00317   // Print the successors of this block according to the CFG.
00318   if (!succ_empty()) {
00319     if (Indexes) OS << '\t';
00320     OS << "    Successors according to CFG:";
00321     for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) {
00322       OS << " BB#" << (*SI)->getNumber();
00323       if (!Probs.empty())
00324         OS << '(' << *getProbabilityIterator(SI) << ')';
00325     }
00326     OS << '\n';
00327   }
00328 }
00329 
00330 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
00331                                        bool /*PrintType*/) const {
00332   OS << "BB#" << getNumber();
00333 }
00334 
00335 void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
00336   LiveInVector::iterator I = std::find_if(
00337       LiveIns.begin(), LiveIns.end(),
00338       [Reg] (const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
00339   if (I == LiveIns.end())
00340     return;
00341 
00342   I->LaneMask &= ~LaneMask;
00343   if (I->LaneMask == 0)
00344     LiveIns.erase(I);
00345 }
00346 
00347 bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
00348   livein_iterator I = std::find_if(
00349       LiveIns.begin(), LiveIns.end(),
00350       [Reg] (const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
00351   return I != livein_end() && (I->LaneMask & LaneMask) != 0;
00352 }
00353 
00354 void MachineBasicBlock::sortUniqueLiveIns() {
00355   std::sort(LiveIns.begin(), LiveIns.end(),
00356             [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
00357               return LI0.PhysReg < LI1.PhysReg;
00358             });
00359   // Liveins are sorted by physreg now we can merge their lanemasks.
00360   LiveInVector::const_iterator I = LiveIns.begin();
00361   LiveInVector::const_iterator J;
00362   LiveInVector::iterator Out = LiveIns.begin();
00363   for (; I != LiveIns.end(); ++Out, I = J) {
00364     unsigned PhysReg = I->PhysReg;
00365     LaneBitmask LaneMask = I->LaneMask;
00366     for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
00367       LaneMask |= J->LaneMask;
00368     Out->PhysReg = PhysReg;
00369     Out->LaneMask = LaneMask;
00370   }
00371   LiveIns.erase(Out, LiveIns.end());
00372 }
00373 
00374 unsigned
00375 MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) {
00376   assert(getParent() && "MBB must be inserted in function");
00377   assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
00378   assert(RC && "Register class is required");
00379   assert((isEHPad() || this == &getParent()->front()) &&
00380          "Only the entry block and landing pads can have physreg live ins");
00381 
00382   bool LiveIn = isLiveIn(PhysReg);
00383   iterator I = SkipPHIsAndLabels(begin()), E = end();
00384   MachineRegisterInfo &MRI = getParent()->getRegInfo();
00385   const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
00386 
00387   // Look for an existing copy.
00388   if (LiveIn)
00389     for (;I != E && I->isCopy(); ++I)
00390       if (I->getOperand(1).getReg() == PhysReg) {
00391         unsigned VirtReg = I->getOperand(0).getReg();
00392         if (!MRI.constrainRegClass(VirtReg, RC))
00393           llvm_unreachable("Incompatible live-in register class.");
00394         return VirtReg;
00395       }
00396 
00397   // No luck, create a virtual register.
00398   unsigned VirtReg = MRI.createVirtualRegister(RC);
00399   BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
00400     .addReg(PhysReg, RegState::Kill);
00401   if (!LiveIn)
00402     addLiveIn(PhysReg);
00403   return VirtReg;
00404 }
00405 
00406 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
00407   getParent()->splice(NewAfter->getIterator(), getIterator());
00408 }
00409 
00410 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
00411   getParent()->splice(++NewBefore->getIterator(), getIterator());
00412 }
00413 
00414 void MachineBasicBlock::updateTerminator() {
00415   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
00416   // A block with no successors has no concerns with fall-through edges.
00417   if (this->succ_empty()) return;
00418 
00419   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
00420   SmallVector<MachineOperand, 4> Cond;
00421   DebugLoc DL;  // FIXME: this is nowhere
00422   bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond);
00423   (void) B;
00424   assert(!B && "UpdateTerminators requires analyzable predecessors!");
00425   if (Cond.empty()) {
00426     if (TBB) {
00427       // The block has an unconditional branch. If its successor is now
00428       // its layout successor, delete the branch.
00429       if (isLayoutSuccessor(TBB))
00430         TII->RemoveBranch(*this);
00431     } else {
00432       // The block has an unconditional fallthrough. If its successor is not
00433       // its layout successor, insert a branch. First we have to locate the
00434       // only non-landing-pad successor, as that is the fallthrough block.
00435       for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
00436         if ((*SI)->isEHPad())
00437           continue;
00438         assert(!TBB && "Found more than one non-landing-pad successor!");
00439         TBB = *SI;
00440       }
00441 
00442       // If there is no non-landing-pad successor, the block has no
00443       // fall-through edges to be concerned with.
00444       if (!TBB)
00445         return;
00446 
00447       // Finally update the unconditional successor to be reached via a branch
00448       // if it would not be reached by fallthrough.
00449       if (!isLayoutSuccessor(TBB))
00450         TII->InsertBranch(*this, TBB, nullptr, Cond, DL);
00451     }
00452   } else {
00453     if (FBB) {
00454       // The block has a non-fallthrough conditional branch. If one of its
00455       // successors is its layout successor, rewrite it to a fallthrough
00456       // conditional branch.
00457       if (isLayoutSuccessor(TBB)) {
00458         if (TII->ReverseBranchCondition(Cond))
00459           return;
00460         TII->RemoveBranch(*this);
00461         TII->InsertBranch(*this, FBB, nullptr, Cond, DL);
00462       } else if (isLayoutSuccessor(FBB)) {
00463         TII->RemoveBranch(*this);
00464         TII->InsertBranch(*this, TBB, nullptr, Cond, DL);
00465       }
00466     } else {
00467       // Walk through the successors and find the successor which is not
00468       // a landing pad and is not the conditional branch destination (in TBB)
00469       // as the fallthrough successor.
00470       MachineBasicBlock *FallthroughBB = nullptr;
00471       for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
00472         if ((*SI)->isEHPad() || *SI == TBB)
00473           continue;
00474         assert(!FallthroughBB && "Found more than one fallthrough successor.");
00475         FallthroughBB = *SI;
00476       }
00477       if (!FallthroughBB && canFallThrough()) {
00478         // We fallthrough to the same basic block as the conditional jump
00479         // targets. Remove the conditional jump, leaving unconditional
00480         // fallthrough.
00481         // FIXME: This does not seem like a reasonable pattern to support, but
00482         // it has been seen in the wild coming out of degenerate ARM test cases.
00483         TII->RemoveBranch(*this);
00484 
00485         // Finally update the unconditional successor to be reached via a branch
00486         // if it would not be reached by fallthrough.
00487         if (!isLayoutSuccessor(TBB))
00488           TII->InsertBranch(*this, TBB, nullptr, Cond, DL);
00489         return;
00490       }
00491 
00492       // The block has a fallthrough conditional branch.
00493       if (isLayoutSuccessor(TBB)) {
00494         if (TII->ReverseBranchCondition(Cond)) {
00495           // We can't reverse the condition, add an unconditional branch.
00496           Cond.clear();
00497           TII->InsertBranch(*this, FallthroughBB, nullptr, Cond, DL);
00498           return;
00499         }
00500         TII->RemoveBranch(*this);
00501         TII->InsertBranch(*this, FallthroughBB, nullptr, Cond, DL);
00502       } else if (!isLayoutSuccessor(FallthroughBB)) {
00503         TII->RemoveBranch(*this);
00504         TII->InsertBranch(*this, TBB, FallthroughBB, Cond, DL);
00505       }
00506     }
00507   }
00508 }
00509 
00510 void MachineBasicBlock::validateSuccProbs() const {
00511 #ifndef NDEBUG
00512   int64_t Sum = 0;
00513   for (auto Prob : Probs)
00514     Sum += Prob.getNumerator();
00515   // Due to precision issue, we assume that the sum of probabilities is one if
00516   // the difference between the sum of their numerators and the denominator is
00517   // no greater than the number of successors.
00518   assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
00519              Probs.size() &&
00520          "The sum of successors's probabilities exceeds one.");
00521 #endif // NDEBUG
00522 }
00523 
00524 void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
00525                                      BranchProbability Prob) {
00526   // Probability list is either empty (if successor list isn't empty, this means
00527   // disabled optimization) or has the same size as successor list.
00528   if (!(Probs.empty() && !Successors.empty()))
00529     Probs.push_back(Prob);
00530   Successors.push_back(Succ);
00531   Succ->addPredecessor(this);
00532 }
00533 
00534 void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
00535   // We need to make sure probability list is either empty or has the same size
00536   // of successor list. When this function is called, we can safely delete all
00537   // probability in the list.
00538   Probs.clear();
00539   Successors.push_back(Succ);
00540   Succ->addPredecessor(this);
00541 }
00542 
00543 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
00544                                         bool NormalizeSuccProbs) {
00545   succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ);
00546   removeSuccessor(I, NormalizeSuccProbs);
00547 }
00548 
00549 MachineBasicBlock::succ_iterator
00550 MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
00551   assert(I != Successors.end() && "Not a current successor!");
00552 
00553   // If probability list is empty it means we don't use it (disabled
00554   // optimization).
00555   if (!Probs.empty()) {
00556     probability_iterator WI = getProbabilityIterator(I);
00557     Probs.erase(WI);
00558     if (NormalizeSuccProbs)
00559       normalizeSuccProbs();
00560   }
00561 
00562   (*I)->removePredecessor(this);
00563   return Successors.erase(I);
00564 }
00565 
00566 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
00567                                          MachineBasicBlock *New) {
00568   if (Old == New)
00569     return;
00570 
00571   succ_iterator E = succ_end();
00572   succ_iterator NewI = E;
00573   succ_iterator OldI = E;
00574   for (succ_iterator I = succ_begin(); I != E; ++I) {
00575     if (*I == Old) {
00576       OldI = I;
00577       if (NewI != E)
00578         break;
00579     }
00580     if (*I == New) {
00581       NewI = I;
00582       if (OldI != E)
00583         break;
00584     }
00585   }
00586   assert(OldI != E && "Old is not a successor of this block");
00587 
00588   // If New isn't already a successor, let it take Old's place.
00589   if (NewI == E) {
00590     Old->removePredecessor(this);
00591     New->addPredecessor(this);
00592     *OldI = New;
00593     return;
00594   }
00595 
00596   // New is already a successor.
00597   // Update its probability instead of adding a duplicate edge.
00598   if (!Probs.empty()) {
00599     auto ProbIter = getProbabilityIterator(NewI);
00600     if (!ProbIter->isUnknown())
00601       *ProbIter += *getProbabilityIterator(OldI);
00602   }
00603   removeSuccessor(OldI);
00604 }
00605 
00606 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
00607   Predecessors.push_back(Pred);
00608 }
00609 
00610 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
00611   pred_iterator I = std::find(Predecessors.begin(), Predecessors.end(), Pred);
00612   assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
00613   Predecessors.erase(I);
00614 }
00615 
00616 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
00617   if (this == FromMBB)
00618     return;
00619 
00620   while (!FromMBB->succ_empty()) {
00621     MachineBasicBlock *Succ = *FromMBB->succ_begin();
00622 
00623     // If probability list is empty it means we don't use it (disabled optimization).
00624     if (!FromMBB->Probs.empty()) {
00625       auto Prob = *FromMBB->Probs.begin();
00626       addSuccessor(Succ, Prob);
00627     } else
00628       addSuccessorWithoutProb(Succ);
00629 
00630     FromMBB->removeSuccessor(Succ);
00631   }
00632 }
00633 
00634 void
00635 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
00636   if (this == FromMBB)
00637     return;
00638 
00639   while (!FromMBB->succ_empty()) {
00640     MachineBasicBlock *Succ = *FromMBB->succ_begin();
00641     if (!FromMBB->Probs.empty()) {
00642       auto Prob = *FromMBB->Probs.begin();
00643       addSuccessor(Succ, Prob);
00644     } else
00645       addSuccessorWithoutProb(Succ);
00646     FromMBB->removeSuccessor(Succ);
00647 
00648     // Fix up any PHI nodes in the successor.
00649     for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(),
00650            ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
00651       for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
00652         MachineOperand &MO = MI->getOperand(i);
00653         if (MO.getMBB() == FromMBB)
00654           MO.setMBB(this);
00655       }
00656   }
00657   normalizeSuccProbs();
00658 }
00659 
00660 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
00661   return std::find(pred_begin(), pred_end(), MBB) != pred_end();
00662 }
00663 
00664 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
00665   return std::find(succ_begin(), succ_end(), MBB) != succ_end();
00666 }
00667 
00668 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
00669   MachineFunction::const_iterator I(this);
00670   return std::next(I) == MachineFunction::const_iterator(MBB);
00671 }
00672 
00673 bool MachineBasicBlock::canFallThrough() {
00674   MachineFunction::iterator Fallthrough = getIterator();
00675   ++Fallthrough;
00676   // If FallthroughBlock is off the end of the function, it can't fall through.
00677   if (Fallthrough == getParent()->end())
00678     return false;
00679 
00680   // If FallthroughBlock isn't a successor, no fallthrough is possible.
00681   if (!isSuccessor(&*Fallthrough))
00682     return false;
00683 
00684   // Analyze the branches, if any, at the end of the block.
00685   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
00686   SmallVector<MachineOperand, 4> Cond;
00687   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
00688   if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) {
00689     // If we couldn't analyze the branch, examine the last instruction.
00690     // If the block doesn't end in a known control barrier, assume fallthrough
00691     // is possible. The isPredicated check is needed because this code can be
00692     // called during IfConversion, where an instruction which is normally a
00693     // Barrier is predicated and thus no longer an actual control barrier.
00694     return empty() || !back().isBarrier() || TII->isPredicated(&back());
00695   }
00696 
00697   // If there is no branch, control always falls through.
00698   if (!TBB) return true;
00699 
00700   // If there is some explicit branch to the fallthrough block, it can obviously
00701   // reach, even though the branch should get folded to fall through implicitly.
00702   if (MachineFunction::iterator(TBB) == Fallthrough ||
00703       MachineFunction::iterator(FBB) == Fallthrough)
00704     return true;
00705 
00706   // If it's an unconditional branch to some block not the fall through, it
00707   // doesn't fall through.
00708   if (Cond.empty()) return false;
00709 
00710   // Otherwise, if it is conditional and has no explicit false block, it falls
00711   // through.
00712   return FBB == nullptr;
00713 }
00714 
00715 MachineBasicBlock *
00716 MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) {
00717   // Splitting the critical edge to a landing pad block is non-trivial. Don't do
00718   // it in this generic function.
00719   if (Succ->isEHPad())
00720     return nullptr;
00721 
00722   MachineFunction *MF = getParent();
00723   DebugLoc DL;  // FIXME: this is nowhere
00724 
00725   // Performance might be harmed on HW that implements branching using exec mask
00726   // where both sides of the branches are always executed.
00727   if (MF->getTarget().requiresStructuredCFG())
00728     return nullptr;
00729 
00730   // We may need to update this's terminator, but we can't do that if
00731   // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
00732   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
00733   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
00734   SmallVector<MachineOperand, 4> Cond;
00735   if (TII->AnalyzeBranch(*this, TBB, FBB, Cond))
00736     return nullptr;
00737 
00738   // Avoid bugpoint weirdness: A block may end with a conditional branch but
00739   // jumps to the same MBB is either case. We have duplicate CFG edges in that
00740   // case that we can't handle. Since this never happens in properly optimized
00741   // code, just skip those edges.
00742   if (TBB && TBB == FBB) {
00743     DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
00744                  << getNumber() << '\n');
00745     return nullptr;
00746   }
00747 
00748   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
00749   MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
00750   DEBUG(dbgs() << "Splitting critical edge:"
00751         " BB#" << getNumber()
00752         << " -- BB#" << NMBB->getNumber()
00753         << " -- BB#" << Succ->getNumber() << '\n');
00754 
00755   LiveIntervals *LIS = P->getAnalysisIfAvailable<LiveIntervals>();
00756   SlotIndexes *Indexes = P->getAnalysisIfAvailable<SlotIndexes>();
00757   if (LIS)
00758     LIS->insertMBBInMaps(NMBB);
00759   else if (Indexes)
00760     Indexes->insertMBBInMaps(NMBB);
00761 
00762   // On some targets like Mips, branches may kill virtual registers. Make sure
00763   // that LiveVariables is properly updated after updateTerminator replaces the
00764   // terminators.
00765   LiveVariables *LV = P->getAnalysisIfAvailable<LiveVariables>();
00766 
00767   // Collect a list of virtual registers killed by the terminators.
00768   SmallVector<unsigned, 4> KilledRegs;
00769   if (LV)
00770     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
00771          I != E; ++I) {
00772       MachineInstr *MI = &*I;
00773       for (MachineInstr::mop_iterator OI = MI->operands_begin(),
00774            OE = MI->operands_end(); OI != OE; ++OI) {
00775         if (!OI->isReg() || OI->getReg() == 0 ||
00776             !OI->isUse() || !OI->isKill() || OI->isUndef())
00777           continue;
00778         unsigned Reg = OI->getReg();
00779         if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
00780             LV->getVarInfo(Reg).removeKill(MI)) {
00781           KilledRegs.push_back(Reg);
00782           DEBUG(dbgs() << "Removing terminator kill: " << *MI);
00783           OI->setIsKill(false);
00784         }
00785       }
00786     }
00787 
00788   SmallVector<unsigned, 4> UsedRegs;
00789   if (LIS) {
00790     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
00791          I != E; ++I) {
00792       MachineInstr *MI = &*I;
00793 
00794       for (MachineInstr::mop_iterator OI = MI->operands_begin(),
00795            OE = MI->operands_end(); OI != OE; ++OI) {
00796         if (!OI->isReg() || OI->getReg() == 0)
00797           continue;
00798 
00799         unsigned Reg = OI->getReg();
00800         if (std::find(UsedRegs.begin(), UsedRegs.end(), Reg) == UsedRegs.end())
00801           UsedRegs.push_back(Reg);
00802       }
00803     }
00804   }
00805 
00806   ReplaceUsesOfBlockWith(Succ, NMBB);
00807 
00808   // If updateTerminator() removes instructions, we need to remove them from
00809   // SlotIndexes.
00810   SmallVector<MachineInstr*, 4> Terminators;
00811   if (Indexes) {
00812     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
00813          I != E; ++I)
00814       Terminators.push_back(&*I);
00815   }
00816 
00817   updateTerminator();
00818 
00819   if (Indexes) {
00820     SmallVector<MachineInstr*, 4> NewTerminators;
00821     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
00822          I != E; ++I)
00823       NewTerminators.push_back(&*I);
00824 
00825     for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
00826         E = Terminators.end(); I != E; ++I) {
00827       if (std::find(NewTerminators.begin(), NewTerminators.end(), *I) ==
00828           NewTerminators.end())
00829        Indexes->removeMachineInstrFromMaps(*I);
00830     }
00831   }
00832 
00833   // Insert unconditional "jump Succ" instruction in NMBB if necessary.
00834   NMBB->addSuccessor(Succ);
00835   if (!NMBB->isLayoutSuccessor(Succ)) {
00836     Cond.clear();
00837     TII->InsertBranch(*NMBB, Succ, nullptr, Cond, DL);
00838 
00839     if (Indexes) {
00840       for (instr_iterator I = NMBB->instr_begin(), E = NMBB->instr_end();
00841            I != E; ++I) {
00842         // Some instructions may have been moved to NMBB by updateTerminator(),
00843         // so we first remove any instruction that already has an index.
00844         if (Indexes->hasIndex(&*I))
00845           Indexes->removeMachineInstrFromMaps(&*I);
00846         Indexes->insertMachineInstrInMaps(&*I);
00847       }
00848     }
00849   }
00850 
00851   // Fix PHI nodes in Succ so they refer to NMBB instead of this
00852   for (MachineBasicBlock::instr_iterator
00853          i = Succ->instr_begin(),e = Succ->instr_end();
00854        i != e && i->isPHI(); ++i)
00855     for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
00856       if (i->getOperand(ni+1).getMBB() == this)
00857         i->getOperand(ni+1).setMBB(NMBB);
00858 
00859   // Inherit live-ins from the successor
00860   for (const auto &LI : Succ->liveins())
00861     NMBB->addLiveIn(LI);
00862 
00863   // Update LiveVariables.
00864   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
00865   if (LV) {
00866     // Restore kills of virtual registers that were killed by the terminators.
00867     while (!KilledRegs.empty()) {
00868       unsigned Reg = KilledRegs.pop_back_val();
00869       for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
00870         if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
00871           continue;
00872         if (TargetRegisterInfo::isVirtualRegister(Reg))
00873           LV->getVarInfo(Reg).Kills.push_back(&*I);
00874         DEBUG(dbgs() << "Restored terminator kill: " << *I);
00875         break;
00876       }
00877     }
00878     // Update relevant live-through information.
00879     LV->addNewBlock(NMBB, this, Succ);
00880   }
00881 
00882   if (LIS) {
00883     // After splitting the edge and updating SlotIndexes, live intervals may be
00884     // in one of two situations, depending on whether this block was the last in
00885     // the function. If the original block was the last in the function, all
00886     // live intervals will end prior to the beginning of the new split block. If
00887     // the original block was not at the end of the function, all live intervals
00888     // will extend to the end of the new split block.
00889 
00890     bool isLastMBB =
00891       std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
00892 
00893     SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
00894     SlotIndex PrevIndex = StartIndex.getPrevSlot();
00895     SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
00896 
00897     // Find the registers used from NMBB in PHIs in Succ.
00898     SmallSet<unsigned, 8> PHISrcRegs;
00899     for (MachineBasicBlock::instr_iterator
00900          I = Succ->instr_begin(), E = Succ->instr_end();
00901          I != E && I->isPHI(); ++I) {
00902       for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
00903         if (I->getOperand(ni+1).getMBB() == NMBB) {
00904           MachineOperand &MO = I->getOperand(ni);
00905           unsigned Reg = MO.getReg();
00906           PHISrcRegs.insert(Reg);
00907           if (MO.isUndef())
00908             continue;
00909 
00910           LiveInterval &LI = LIS->getInterval(Reg);
00911           VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
00912           assert(VNI &&
00913                  "PHI sources should be live out of their predecessors.");
00914           LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
00915         }
00916       }
00917     }
00918 
00919     MachineRegisterInfo *MRI = &getParent()->getRegInfo();
00920     for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
00921       unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
00922       if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
00923         continue;
00924 
00925       LiveInterval &LI = LIS->getInterval(Reg);
00926       if (!LI.liveAt(PrevIndex))
00927         continue;
00928 
00929       bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
00930       if (isLiveOut && isLastMBB) {
00931         VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
00932         assert(VNI && "LiveInterval should have VNInfo where it is live.");
00933         LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
00934       } else if (!isLiveOut && !isLastMBB) {
00935         LI.removeSegment(StartIndex, EndIndex);
00936       }
00937     }
00938 
00939     // Update all intervals for registers whose uses may have been modified by
00940     // updateTerminator().
00941     LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
00942   }
00943 
00944   if (MachineDominatorTree *MDT =
00945       P->getAnalysisIfAvailable<MachineDominatorTree>())
00946     MDT->recordSplitCriticalEdge(this, Succ, NMBB);
00947 
00948   if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable<MachineLoopInfo>())
00949     if (MachineLoop *TIL = MLI->getLoopFor(this)) {
00950       // If one or the other blocks were not in a loop, the new block is not
00951       // either, and thus LI doesn't need to be updated.
00952       if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
00953         if (TIL == DestLoop) {
00954           // Both in the same loop, the NMBB joins loop.
00955           DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
00956         } else if (TIL->contains(DestLoop)) {
00957           // Edge from an outer loop to an inner loop.  Add to the outer loop.
00958           TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
00959         } else if (DestLoop->contains(TIL)) {
00960           // Edge from an inner loop to an outer loop.  Add to the outer loop.
00961           DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
00962         } else {
00963           // Edge from two loops with no containment relation.  Because these
00964           // are natural loops, we know that the destination block must be the
00965           // header of its loop (adding a branch into a loop elsewhere would
00966           // create an irreducible loop).
00967           assert(DestLoop->getHeader() == Succ &&
00968                  "Should not create irreducible loops!");
00969           if (MachineLoop *P = DestLoop->getParentLoop())
00970             P->addBasicBlockToLoop(NMBB, MLI->getBase());
00971         }
00972       }
00973     }
00974 
00975   return NMBB;
00976 }
00977 
00978 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
00979 /// neighboring instructions so the bundle won't be broken by removing MI.
00980 static void unbundleSingleMI(MachineInstr *MI) {
00981   // Removing the first instruction in a bundle.
00982   if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
00983     MI->unbundleFromSucc();
00984   // Removing the last instruction in a bundle.
00985   if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
00986     MI->unbundleFromPred();
00987   // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
00988   // are already fine.
00989 }
00990 
00991 MachineBasicBlock::instr_iterator
00992 MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
00993   unbundleSingleMI(&*I);
00994   return Insts.erase(I);
00995 }
00996 
00997 MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
00998   unbundleSingleMI(MI);
00999   MI->clearFlag(MachineInstr::BundledPred);
01000   MI->clearFlag(MachineInstr::BundledSucc);
01001   return Insts.remove(MI);
01002 }
01003 
01004 MachineBasicBlock::instr_iterator
01005 MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
01006   assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
01007          "Cannot insert instruction with bundle flags");
01008   // Set the bundle flags when inserting inside a bundle.
01009   if (I != instr_end() && I->isBundledWithPred()) {
01010     MI->setFlag(MachineInstr::BundledPred);
01011     MI->setFlag(MachineInstr::BundledSucc);
01012   }
01013   return Insts.insert(I, MI);
01014 }
01015 
01016 /// This method unlinks 'this' from the containing function, and returns it, but
01017 /// does not delete it.
01018 MachineBasicBlock *MachineBasicBlock::removeFromParent() {
01019   assert(getParent() && "Not embedded in a function!");
01020   getParent()->remove(this);
01021   return this;
01022 }
01023 
01024 /// This method unlinks 'this' from the containing function, and deletes it.
01025 void MachineBasicBlock::eraseFromParent() {
01026   assert(getParent() && "Not embedded in a function!");
01027   getParent()->erase(this);
01028 }
01029 
01030 /// Given a machine basic block that branched to 'Old', change the code and CFG
01031 /// so that it branches to 'New' instead.
01032 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
01033                                                MachineBasicBlock *New) {
01034   assert(Old != New && "Cannot replace self with self!");
01035 
01036   MachineBasicBlock::instr_iterator I = instr_end();
01037   while (I != instr_begin()) {
01038     --I;
01039     if (!I->isTerminator()) break;
01040 
01041     // Scan the operands of this machine instruction, replacing any uses of Old
01042     // with New.
01043     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
01044       if (I->getOperand(i).isMBB() &&
01045           I->getOperand(i).getMBB() == Old)
01046         I->getOperand(i).setMBB(New);
01047   }
01048 
01049   // Update the successor information.
01050   replaceSuccessor(Old, New);
01051 }
01052 
01053 /// Various pieces of code can cause excess edges in the CFG to be inserted.  If
01054 /// we have proven that MBB can only branch to DestA and DestB, remove any other
01055 /// MBB successors from the CFG.  DestA and DestB can be null.
01056 ///
01057 /// Besides DestA and DestB, retain other edges leading to LandingPads
01058 /// (currently there can be only one; we don't check or require that here).
01059 /// Note it is possible that DestA and/or DestB are LandingPads.
01060 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
01061                                              MachineBasicBlock *DestB,
01062                                              bool IsCond) {
01063   // The values of DestA and DestB frequently come from a call to the
01064   // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
01065   // values from there.
01066   //
01067   // 1. If both DestA and DestB are null, then the block ends with no branches
01068   //    (it falls through to its successor).
01069   // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
01070   //    with only an unconditional branch.
01071   // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
01072   //    with a conditional branch that falls through to a successor (DestB).
01073   // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
01074   //    conditional branch followed by an unconditional branch. DestA is the
01075   //    'true' destination and DestB is the 'false' destination.
01076 
01077   bool Changed = false;
01078 
01079   MachineFunction::iterator FallThru = std::next(getIterator());
01080 
01081   if (!DestA && !DestB) {
01082     // Block falls through to successor.
01083     DestA = &*FallThru;
01084     DestB = &*FallThru;
01085   } else if (DestA && !DestB) {
01086     if (IsCond)
01087       // Block ends in conditional jump that falls through to successor.
01088       DestB = &*FallThru;
01089   } else {
01090     assert(DestA && DestB && IsCond &&
01091            "CFG in a bad state. Cannot correct CFG edges");
01092   }
01093 
01094   // Remove superfluous edges. I.e., those which aren't destinations of this
01095   // basic block, duplicate edges, or landing pads.
01096   SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
01097   MachineBasicBlock::succ_iterator SI = succ_begin();
01098   while (SI != succ_end()) {
01099     const MachineBasicBlock *MBB = *SI;
01100     if (!SeenMBBs.insert(MBB).second ||
01101         (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
01102       // This is a superfluous edge, remove it.
01103       SI = removeSuccessor(SI);
01104       Changed = true;
01105     } else {
01106       ++SI;
01107     }
01108   }
01109 
01110   if (Changed)
01111     normalizeSuccProbs();
01112   return Changed;
01113 }
01114 
01115 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
01116 /// instructions.  Return UnknownLoc if there is none.
01117 DebugLoc
01118 MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
01119   DebugLoc DL;
01120   instr_iterator E = instr_end();
01121   if (MBBI == E)
01122     return DL;
01123 
01124   // Skip debug declarations, we don't want a DebugLoc from them.
01125   while (MBBI != E && MBBI->isDebugValue())
01126     MBBI++;
01127   if (MBBI != E)
01128     DL = MBBI->getDebugLoc();
01129   return DL;
01130 }
01131 
01132 /// Return probability of the edge from this block to MBB.
01133 BranchProbability
01134 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
01135   if (Probs.empty())
01136     return BranchProbability(1, succ_size());
01137 
01138   const auto &Prob = *getProbabilityIterator(Succ);
01139   if (Prob.isUnknown()) {
01140     // For unknown probabilities, collect the sum of all known ones, and evenly
01141     // ditribute the complemental of the sum to each unknown probability.
01142     unsigned KnownProbNum = 0;
01143     auto Sum = BranchProbability::getZero();
01144     for (auto &P : Probs) {
01145       if (!P.isUnknown()) {
01146         Sum += P;
01147         KnownProbNum++;
01148       }
01149     }
01150     return Sum.getCompl() / (Probs.size() - KnownProbNum);
01151   } else
01152     return Prob;
01153 }
01154 
01155 /// Set successor probability of a given iterator.
01156 void MachineBasicBlock::setSuccProbability(succ_iterator I,
01157                                            BranchProbability Prob) {
01158   assert(!Prob.isUnknown());
01159   if (Probs.empty())
01160     return;
01161   *getProbabilityIterator(I) = Prob;
01162 }
01163 
01164 /// Return probability iterator corresonding to the I successor iterator
01165 MachineBasicBlock::const_probability_iterator
01166 MachineBasicBlock::getProbabilityIterator(
01167     MachineBasicBlock::const_succ_iterator I) const {
01168   assert(Probs.size() == Successors.size() && "Async probability list!");
01169   const size_t index = std::distance(Successors.begin(), I);
01170   assert(index < Probs.size() && "Not a current successor!");
01171   return Probs.begin() + index;
01172 }
01173 
01174 /// Return probability iterator corresonding to the I successor iterator.
01175 MachineBasicBlock::probability_iterator
01176 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
01177   assert(Probs.size() == Successors.size() && "Async probability list!");
01178   const size_t index = std::distance(Successors.begin(), I);
01179   assert(index < Probs.size() && "Not a current successor!");
01180   return Probs.begin() + index;
01181 }
01182 
01183 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
01184 /// as of just before "MI".
01185 ///
01186 /// Search is localised to a neighborhood of
01187 /// Neighborhood instructions before (searching for defs or kills) and N
01188 /// instructions after (searching just for defs) MI.
01189 MachineBasicBlock::LivenessQueryResult
01190 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
01191                                            unsigned Reg, const_iterator Before,
01192                                            unsigned Neighborhood) const {
01193   unsigned N = Neighborhood;
01194 
01195   // Start by searching backwards from Before, looking for kills, reads or defs.
01196   const_iterator I(Before);
01197   // If this is the first insn in the block, don't search backwards.
01198   if (I != begin()) {
01199     do {
01200       --I;
01201 
01202       MachineOperandIteratorBase::PhysRegInfo Info =
01203         ConstMIOperands(I).analyzePhysReg(Reg, TRI);
01204 
01205       // Defs happen after uses so they take precedence if both are present.
01206 
01207       // Register is dead after a dead def of the full register.
01208       if (Info.DeadDef)
01209         return LQR_Dead;
01210       // Register is (at least partially) live after a def.
01211       if (Info.Defined)
01212         return LQR_Live;
01213       // Register is dead after a full kill or clobber and no def.
01214       if (Info.Killed || Info.Clobbered)
01215         return LQR_Dead;
01216       // Register must be live if we read it.
01217       if (Info.Read)
01218         return LQR_Live;
01219     } while (I != begin() && --N > 0);
01220   }
01221 
01222   // Did we get to the start of the block?
01223   if (I == begin()) {
01224     // If so, the register's state is definitely defined by the live-in state.
01225     for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
01226          ++RAI)
01227       if (isLiveIn(*RAI))
01228         return LQR_Live;
01229 
01230     return LQR_Dead;
01231   }
01232 
01233   N = Neighborhood;
01234 
01235   // Try searching forwards from Before, looking for reads or defs.
01236   I = const_iterator(Before);
01237   // If this is the last insn in the block, don't search forwards.
01238   if (I != end()) {
01239     for (++I; I != end() && N > 0; ++I, --N) {
01240       MachineOperandIteratorBase::PhysRegInfo Info =
01241         ConstMIOperands(I).analyzePhysReg(Reg, TRI);
01242 
01243       // Register is live when we read it here.
01244       if (Info.Read)
01245         return LQR_Live;
01246       // Register is dead if we can fully overwrite or clobber it here.
01247       if (Info.FullyDefined || Info.Clobbered)
01248         return LQR_Dead;
01249     }
01250   }
01251 
01252   // At this point we have no idea of the liveness of the register.
01253   return LQR_Unknown;
01254 }
01255 
01256 const uint32_t *
01257 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
01258   // EH funclet entry does not preserve any registers.
01259   return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
01260 }
01261 
01262 const uint32_t *
01263 MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
01264   // If we see a return block with successors, this must be a funclet return,
01265   // which does not preserve any registers. If there are no successors, we don't
01266   // care what kind of return it is, putting a mask after it is a no-op.
01267   return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
01268 }