lib/CodeGen/MachineBasicBlock.cpp

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