LLVM API Documentation

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