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