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