MachineVerifier.cpp revision 6fcb6e454b08c5e5aaed125860b01bc08dc6cc49 
1//===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===//
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// Pass to verify generated machine code. The following is checked:
11//
12// Operand counts: All explicit operands must be present.
13//
14// Register classes: All physical and virtual register operands must be
15// compatible with the register class required by the instruction descriptor.
16//
17// Register live intervals: Registers must be defined only once, and must be
18// defined before use.
19//
20// The machine code verifier is enabled from LLVMTargetMachine.cpp with the
21// command-line option -verify-machineinstrs, or by defining the environment
22// variable LLVM_VERIFY_MACHINEINSTRS to the name of a file that will receive
23// the verifier errors.
24//===----------------------------------------------------------------------===//
25
26#include "llvm/Instructions.h"
27#include "llvm/Function.h"
28#include "llvm/CodeGen/LiveIntervalAnalysis.h"
29#include "llvm/CodeGen/LiveVariables.h"
30#include "llvm/CodeGen/LiveStackAnalysis.h"
31#include "llvm/CodeGen/MachineFunctionPass.h"
32#include "llvm/CodeGen/MachineFrameInfo.h"
33#include "llvm/CodeGen/MachineMemOperand.h"
34#include "llvm/CodeGen/MachineRegisterInfo.h"
35#include "llvm/CodeGen/Passes.h"
36#include "llvm/MC/MCAsmInfo.h"
37#include "llvm/Target/TargetMachine.h"
38#include "llvm/Target/TargetRegisterInfo.h"
39#include "llvm/Target/TargetInstrInfo.h"
40#include "llvm/ADT/DenseSet.h"
41#include "llvm/ADT/SetOperations.h"
42#include "llvm/ADT/SmallVector.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/raw_ostream.h"
46using namespace llvm;
47
48namespace {
49  struct MachineVerifier {
50
51    MachineVerifier(Pass *pass, const char *b) :
52      PASS(pass),
53      Banner(b),
54      OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
55      {}
56
57    bool runOnMachineFunction(MachineFunction &MF);
58
59    Pass *const PASS;
60    const char *Banner;
61    const char *const OutFileName;
62    raw_ostream *OS;
63    const MachineFunction *MF;
64    const TargetMachine *TM;
65    const TargetRegisterInfo *TRI;
66    const MachineRegisterInfo *MRI;
67
68    unsigned foundErrors;
69
70    typedef SmallVector<unsigned, 16> RegVector;
71    typedef DenseSet<unsigned> RegSet;
72    typedef DenseMap<unsigned, const MachineInstr*> RegMap;
73
74    BitVector regsReserved;
75    RegSet regsLive;
76    RegVector regsDefined, regsDead, regsKilled;
77    RegSet regsLiveInButUnused;
78
79    SlotIndex lastIndex;
80
81    // Add Reg and any sub-registers to RV
82    void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
83      RV.push_back(Reg);
84      if (TargetRegisterInfo::isPhysicalRegister(Reg))
85        for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
86          RV.push_back(*R);
87    }
88
89    struct BBInfo {
90      // Is this MBB reachable from the MF entry point?
91      bool reachable;
92
93      // Vregs that must be live in because they are used without being
94      // defined. Map value is the user.
95      RegMap vregsLiveIn;
96
97      // Regs killed in MBB. They may be defined again, and will then be in both
98      // regsKilled and regsLiveOut.
99      RegSet regsKilled;
100
101      // Regs defined in MBB and live out. Note that vregs passing through may
102      // be live out without being mentioned here.
103      RegSet regsLiveOut;
104
105      // Vregs that pass through MBB untouched. This set is disjoint from
106      // regsKilled and regsLiveOut.
107      RegSet vregsPassed;
108
109      // Vregs that must pass through MBB because they are needed by a successor
110      // block. This set is disjoint from regsLiveOut.
111      RegSet vregsRequired;
112
113      BBInfo() : reachable(false) {}
114
115      // Add register to vregsPassed if it belongs there. Return true if
116      // anything changed.
117      bool addPassed(unsigned Reg) {
118        if (!TargetRegisterInfo::isVirtualRegister(Reg))
119          return false;
120        if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
121          return false;
122        return vregsPassed.insert(Reg).second;
123      }
124
125      // Same for a full set.
126      bool addPassed(const RegSet &RS) {
127        bool changed = false;
128        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
129          if (addPassed(*I))
130            changed = true;
131        return changed;
132      }
133
134      // Add register to vregsRequired if it belongs there. Return true if
135      // anything changed.
136      bool addRequired(unsigned Reg) {
137        if (!TargetRegisterInfo::isVirtualRegister(Reg))
138          return false;
139        if (regsLiveOut.count(Reg))
140          return false;
141        return vregsRequired.insert(Reg).second;
142      }
143
144      // Same for a full set.
145      bool addRequired(const RegSet &RS) {
146        bool changed = false;
147        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
148          if (addRequired(*I))
149            changed = true;
150        return changed;
151      }
152
153      // Same for a full map.
154      bool addRequired(const RegMap &RM) {
155        bool changed = false;
156        for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
157          if (addRequired(I->first))
158            changed = true;
159        return changed;
160      }
161
162      // Live-out registers are either in regsLiveOut or vregsPassed.
163      bool isLiveOut(unsigned Reg) const {
164        return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
165      }
166    };
167
168    // Extra register info per MBB.
169    DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
170
171    bool isReserved(unsigned Reg) {
172      return Reg < regsReserved.size() && regsReserved.test(Reg);
173    }
174
175    // Analysis information if available
176    LiveVariables *LiveVars;
177    LiveIntervals *LiveInts;
178    LiveStacks *LiveStks;
179    SlotIndexes *Indexes;
180
181    void visitMachineFunctionBefore();
182    void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
183    void visitMachineInstrBefore(const MachineInstr *MI);
184    void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
185    void visitMachineInstrAfter(const MachineInstr *MI);
186    void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
187    void visitMachineFunctionAfter();
188
189    void report(const char *msg, const MachineFunction *MF);
190    void report(const char *msg, const MachineBasicBlock *MBB);
191    void report(const char *msg, const MachineInstr *MI);
192    void report(const char *msg, const MachineOperand *MO, unsigned MONum);
193
194    void markReachable(const MachineBasicBlock *MBB);
195    void calcRegsPassed();
196    void checkPHIOps(const MachineBasicBlock *MBB);
197
198    void calcRegsRequired();
199    void verifyLiveVariables();
200    void verifyLiveIntervals();
201  };
202
203  struct MachineVerifierPass : public MachineFunctionPass {
204    static char ID; // Pass ID, replacement for typeid
205    const char *const Banner;
206
207    MachineVerifierPass(const char *b = 0)
208      : MachineFunctionPass(ID), Banner(b) {
209        initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
210      }
211
212    void getAnalysisUsage(AnalysisUsage &AU) const {
213      AU.setPreservesAll();
214      MachineFunctionPass::getAnalysisUsage(AU);
215    }
216
217    bool runOnMachineFunction(MachineFunction &MF) {
218      MF.verify(this, Banner);
219      return false;
220    }
221  };
222
223}
224
225char MachineVerifierPass::ID = 0;
226INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
227                "Verify generated machine code", false, false)
228
229FunctionPass *llvm::createMachineVerifierPass(const char *Banner) {
230  return new MachineVerifierPass(Banner);
231}
232
233void MachineFunction::verify(Pass *p, const char *Banner) const {
234  MachineVerifier(p, Banner)
235    .runOnMachineFunction(const_cast<MachineFunction&>(*this));
236}
237
238bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
239  raw_ostream *OutFile = 0;
240  if (OutFileName) {
241    std::string ErrorInfo;
242    OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
243                                 raw_fd_ostream::F_Append);
244    if (!ErrorInfo.empty()) {
245      errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
246      exit(1);
247    }
248
249    OS = OutFile;
250  } else {
251    OS = &errs();
252  }
253
254  foundErrors = 0;
255
256  this->MF = &MF;
257  TM = &MF.getTarget();
258  TRI = TM->getRegisterInfo();
259  MRI = &MF.getRegInfo();
260
261  LiveVars = NULL;
262  LiveInts = NULL;
263  LiveStks = NULL;
264  Indexes = NULL;
265  if (PASS) {
266    LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
267    // We don't want to verify LiveVariables if LiveIntervals is available.
268    if (!LiveInts)
269      LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
270    LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
271    Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
272  }
273
274  visitMachineFunctionBefore();
275  for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
276       MFI!=MFE; ++MFI) {
277    visitMachineBasicBlockBefore(MFI);
278    for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
279           MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
280      if (MBBI->getParent() != MFI) {
281        report("Bad instruction parent pointer", MFI);
282        *OS << "Instruction: " << *MBBI;
283        continue;
284      }
285      visitMachineInstrBefore(MBBI);
286      for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
287        visitMachineOperand(&MBBI->getOperand(I), I);
288      visitMachineInstrAfter(MBBI);
289    }
290    visitMachineBasicBlockAfter(MFI);
291  }
292  visitMachineFunctionAfter();
293
294  if (OutFile)
295    delete OutFile;
296  else if (foundErrors)
297    report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
298
299  // Clean up.
300  regsLive.clear();
301  regsDefined.clear();
302  regsDead.clear();
303  regsKilled.clear();
304  regsLiveInButUnused.clear();
305  MBBInfoMap.clear();
306
307  return false;                 // no changes
308}
309
310void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
311  assert(MF);
312  *OS << '\n';
313  if (!foundErrors++) {
314    if (Banner)
315      *OS << "# " << Banner << '\n';
316    MF->print(*OS, Indexes);
317  }
318  *OS << "*** Bad machine code: " << msg << " ***\n"
319      << "- function:    " << MF->getFunction()->getNameStr() << "\n";
320}
321
322void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
323  assert(MBB);
324  report(msg, MBB->getParent());
325  *OS << "- basic block: " << MBB->getName()
326      << " " << (void*)MBB
327      << " (BB#" << MBB->getNumber() << ")";
328  if (Indexes)
329    *OS << " [" << Indexes->getMBBStartIdx(MBB)
330        << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
331  *OS << '\n';
332}
333
334void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
335  assert(MI);
336  report(msg, MI->getParent());
337  *OS << "- instruction: ";
338  if (Indexes && Indexes->hasIndex(MI))
339    *OS << Indexes->getInstructionIndex(MI) << '\t';
340  MI->print(*OS, TM);
341}
342
343void MachineVerifier::report(const char *msg,
344                             const MachineOperand *MO, unsigned MONum) {
345  assert(MO);
346  report(msg, MO->getParent());
347  *OS << "- operand " << MONum << ":   ";
348  MO->print(*OS, TM);
349  *OS << "\n";
350}
351
352void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
353  BBInfo &MInfo = MBBInfoMap[MBB];
354  if (!MInfo.reachable) {
355    MInfo.reachable = true;
356    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
357           SuE = MBB->succ_end(); SuI != SuE; ++SuI)
358      markReachable(*SuI);
359  }
360}
361
362void MachineVerifier::visitMachineFunctionBefore() {
363  lastIndex = SlotIndex();
364  regsReserved = TRI->getReservedRegs(*MF);
365
366  // A sub-register of a reserved register is also reserved
367  for (int Reg = regsReserved.find_first(); Reg>=0;
368       Reg = regsReserved.find_next(Reg)) {
369    for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
370      // FIXME: This should probably be:
371      // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
372      regsReserved.set(*Sub);
373    }
374  }
375  markReachable(&MF->front());
376}
377
378// Does iterator point to a and b as the first two elements?
379static bool matchPair(MachineBasicBlock::const_succ_iterator i,
380                      const MachineBasicBlock *a, const MachineBasicBlock *b) {
381  if (*i == a)
382    return *++i == b;
383  if (*i == b)
384    return *++i == a;
385  return false;
386}
387
388void
389MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
390  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
391
392  // Count the number of landing pad successors.
393  SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
394  for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
395       E = MBB->succ_end(); I != E; ++I) {
396    if ((*I)->isLandingPad())
397      LandingPadSuccs.insert(*I);
398  }
399
400  const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
401  const BasicBlock *BB = MBB->getBasicBlock();
402  if (LandingPadSuccs.size() > 1 &&
403      !(AsmInfo &&
404        AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
405        BB && isa<SwitchInst>(BB->getTerminator())))
406    report("MBB has more than one landing pad successor", MBB);
407
408  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
409  MachineBasicBlock *TBB = 0, *FBB = 0;
410  SmallVector<MachineOperand, 4> Cond;
411  if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
412                          TBB, FBB, Cond)) {
413    // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
414    // check whether its answers match up with reality.
415    if (!TBB && !FBB) {
416      // Block falls through to its successor.
417      MachineFunction::const_iterator MBBI = MBB;
418      ++MBBI;
419      if (MBBI == MF->end()) {
420        // It's possible that the block legitimately ends with a noreturn
421        // call or an unreachable, in which case it won't actually fall
422        // out the bottom of the function.
423      } else if (MBB->succ_size() == LandingPadSuccs.size()) {
424        // It's possible that the block legitimately ends with a noreturn
425        // call or an unreachable, in which case it won't actuall fall
426        // out of the block.
427      } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
428        report("MBB exits via unconditional fall-through but doesn't have "
429               "exactly one CFG successor!", MBB);
430      } else if (!MBB->isSuccessor(MBBI)) {
431        report("MBB exits via unconditional fall-through but its successor "
432               "differs from its CFG successor!", MBB);
433      }
434      if (!MBB->empty() && MBB->back().getDesc().isBarrier() &&
435          !TII->isPredicated(&MBB->back())) {
436        report("MBB exits via unconditional fall-through but ends with a "
437               "barrier instruction!", MBB);
438      }
439      if (!Cond.empty()) {
440        report("MBB exits via unconditional fall-through but has a condition!",
441               MBB);
442      }
443    } else if (TBB && !FBB && Cond.empty()) {
444      // Block unconditionally branches somewhere.
445      if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
446        report("MBB exits via unconditional branch but doesn't have "
447               "exactly one CFG successor!", MBB);
448      } else if (!MBB->isSuccessor(TBB)) {
449        report("MBB exits via unconditional branch but the CFG "
450               "successor doesn't match the actual successor!", MBB);
451      }
452      if (MBB->empty()) {
453        report("MBB exits via unconditional branch but doesn't contain "
454               "any instructions!", MBB);
455      } else if (!MBB->back().getDesc().isBarrier()) {
456        report("MBB exits via unconditional branch but doesn't end with a "
457               "barrier instruction!", MBB);
458      } else if (!MBB->back().getDesc().isTerminator()) {
459        report("MBB exits via unconditional branch but the branch isn't a "
460               "terminator instruction!", MBB);
461      }
462    } else if (TBB && !FBB && !Cond.empty()) {
463      // Block conditionally branches somewhere, otherwise falls through.
464      MachineFunction::const_iterator MBBI = MBB;
465      ++MBBI;
466      if (MBBI == MF->end()) {
467        report("MBB conditionally falls through out of function!", MBB);
468      } if (MBB->succ_size() != 2) {
469        report("MBB exits via conditional branch/fall-through but doesn't have "
470               "exactly two CFG successors!", MBB);
471      } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
472        report("MBB exits via conditional branch/fall-through but the CFG "
473               "successors don't match the actual successors!", MBB);
474      }
475      if (MBB->empty()) {
476        report("MBB exits via conditional branch/fall-through but doesn't "
477               "contain any instructions!", MBB);
478      } else if (MBB->back().getDesc().isBarrier()) {
479        report("MBB exits via conditional branch/fall-through but ends with a "
480               "barrier instruction!", MBB);
481      } else if (!MBB->back().getDesc().isTerminator()) {
482        report("MBB exits via conditional branch/fall-through but the branch "
483               "isn't a terminator instruction!", MBB);
484      }
485    } else if (TBB && FBB) {
486      // Block conditionally branches somewhere, otherwise branches
487      // somewhere else.
488      if (MBB->succ_size() != 2) {
489        report("MBB exits via conditional branch/branch but doesn't have "
490               "exactly two CFG successors!", MBB);
491      } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
492        report("MBB exits via conditional branch/branch but the CFG "
493               "successors don't match the actual successors!", MBB);
494      }
495      if (MBB->empty()) {
496        report("MBB exits via conditional branch/branch but doesn't "
497               "contain any instructions!", MBB);
498      } else if (!MBB->back().getDesc().isBarrier()) {
499        report("MBB exits via conditional branch/branch but doesn't end with a "
500               "barrier instruction!", MBB);
501      } else if (!MBB->back().getDesc().isTerminator()) {
502        report("MBB exits via conditional branch/branch but the branch "
503               "isn't a terminator instruction!", MBB);
504      }
505      if (Cond.empty()) {
506        report("MBB exits via conditinal branch/branch but there's no "
507               "condition!", MBB);
508      }
509    } else {
510      report("AnalyzeBranch returned invalid data!", MBB);
511    }
512  }
513
514  regsLive.clear();
515  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
516         E = MBB->livein_end(); I != E; ++I) {
517    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
518      report("MBB live-in list contains non-physical register", MBB);
519      continue;
520    }
521    regsLive.insert(*I);
522    for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
523      regsLive.insert(*R);
524  }
525  regsLiveInButUnused = regsLive;
526
527  const MachineFrameInfo *MFI = MF->getFrameInfo();
528  assert(MFI && "Function has no frame info");
529  BitVector PR = MFI->getPristineRegs(MBB);
530  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
531    regsLive.insert(I);
532    for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
533      regsLive.insert(*R);
534  }
535
536  regsKilled.clear();
537  regsDefined.clear();
538
539  if (Indexes)
540    lastIndex = Indexes->getMBBStartIdx(MBB);
541}
542
543void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
544  const TargetInstrDesc &TI = MI->getDesc();
545  if (MI->getNumOperands() < TI.getNumOperands()) {
546    report("Too few operands", MI);
547    *OS << TI.getNumOperands() << " operands expected, but "
548        << MI->getNumExplicitOperands() << " given.\n";
549  }
550
551  // Check the MachineMemOperands for basic consistency.
552  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
553       E = MI->memoperands_end(); I != E; ++I) {
554    if ((*I)->isLoad() && !TI.mayLoad())
555      report("Missing mayLoad flag", MI);
556    if ((*I)->isStore() && !TI.mayStore())
557      report("Missing mayStore flag", MI);
558  }
559
560  // Debug values must not have a slot index.
561  // Other instructions must have one.
562  if (LiveInts) {
563    bool mapped = !LiveInts->isNotInMIMap(MI);
564    if (MI->isDebugValue()) {
565      if (mapped)
566        report("Debug instruction has a slot index", MI);
567    } else {
568      if (!mapped)
569        report("Missing slot index", MI);
570    }
571  }
572
573}
574
575void
576MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
577  const MachineInstr *MI = MO->getParent();
578  const TargetInstrDesc &TI = MI->getDesc();
579  const TargetOperandInfo &TOI = TI.OpInfo[MONum];
580
581  // The first TI.NumDefs operands must be explicit register defines
582  if (MONum < TI.getNumDefs()) {
583    if (!MO->isReg())
584      report("Explicit definition must be a register", MO, MONum);
585    else if (!MO->isDef())
586      report("Explicit definition marked as use", MO, MONum);
587    else if (MO->isImplicit())
588      report("Explicit definition marked as implicit", MO, MONum);
589  } else if (MONum < TI.getNumOperands()) {
590    // Don't check if it's the last operand in a variadic instruction. See,
591    // e.g., LDM_RET in the arm back end.
592    if (MO->isReg() && !(TI.isVariadic() && MONum == TI.getNumOperands()-1)) {
593      if (MO->isDef() && !TOI.isOptionalDef())
594          report("Explicit operand marked as def", MO, MONum);
595      if (MO->isImplicit())
596        report("Explicit operand marked as implicit", MO, MONum);
597    }
598  } else {
599    // ARM adds %reg0 operands to indicate predicates. We'll allow that.
600    if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic() && MO->getReg())
601      report("Extra explicit operand on non-variadic instruction", MO, MONum);
602  }
603
604  switch (MO->getType()) {
605  case MachineOperand::MO_Register: {
606    const unsigned Reg = MO->getReg();
607    if (!Reg)
608      return;
609
610    // Check Live Variables.
611    if (MI->isDebugValue()) {
612      // Liveness checks are not valid for debug values.
613    } else if (MO->isUse() && !MO->isUndef()) {
614      regsLiveInButUnused.erase(Reg);
615
616      bool isKill = false;
617      unsigned defIdx;
618      if (MI->isRegTiedToDefOperand(MONum, &defIdx)) {
619        // A two-addr use counts as a kill if use and def are the same.
620        unsigned DefReg = MI->getOperand(defIdx).getReg();
621        if (Reg == DefReg)
622          isKill = true;
623        else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
624          report("Two-address instruction operands must be identical",
625                 MO, MONum);
626        }
627      } else
628        isKill = MO->isKill();
629
630      if (isKill)
631        addRegWithSubRegs(regsKilled, Reg);
632
633      // Check that LiveVars knows this kill.
634      if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
635          MO->isKill()) {
636        LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
637        if (std::find(VI.Kills.begin(),
638                      VI.Kills.end(), MI) == VI.Kills.end())
639          report("Kill missing from LiveVariables", MO, MONum);
640      }
641
642      // Check LiveInts liveness and kill.
643      if (TargetRegisterInfo::isVirtualRegister(Reg) &&
644          LiveInts && !LiveInts->isNotInMIMap(MI)) {
645        SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getUseIndex();
646        if (LiveInts->hasInterval(Reg)) {
647          const LiveInterval &LI = LiveInts->getInterval(Reg);
648          if (!LI.liveAt(UseIdx)) {
649            report("No live range at use", MO, MONum);
650            *OS << UseIdx << " is not live in " << LI << '\n';
651          }
652          // Check for extra kill flags.
653          // Note that we allow missing kill flags for now.
654          if (MO->isKill() && !LI.killedAt(UseIdx.getDefIndex())) {
655            report("Live range continues after kill flag", MO, MONum);
656            *OS << "Live range: " << LI << '\n';
657          }
658        } else {
659          report("Virtual register has no Live interval", MO, MONum);
660        }
661      }
662
663      // Use of a dead register.
664      if (!regsLive.count(Reg)) {
665        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
666          // Reserved registers may be used even when 'dead'.
667          if (!isReserved(Reg))
668            report("Using an undefined physical register", MO, MONum);
669        } else {
670          BBInfo &MInfo = MBBInfoMap[MI->getParent()];
671          // We don't know which virtual registers are live in, so only complain
672          // if vreg was killed in this MBB. Otherwise keep track of vregs that
673          // must be live in. PHI instructions are handled separately.
674          if (MInfo.regsKilled.count(Reg))
675            report("Using a killed virtual register", MO, MONum);
676          else if (!MI->isPHI())
677            MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
678        }
679      }
680    } else if (MO->isDef()) {
681      // Register defined.
682      // TODO: verify that earlyclobber ops are not used.
683      if (MO->isDead())
684        addRegWithSubRegs(regsDead, Reg);
685      else
686        addRegWithSubRegs(regsDefined, Reg);
687
688      // Check LiveInts for a live range, but only for virtual registers.
689      if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
690          !LiveInts->isNotInMIMap(MI)) {
691        SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getDefIndex();
692        if (LiveInts->hasInterval(Reg)) {
693          const LiveInterval &LI = LiveInts->getInterval(Reg);
694          if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
695            assert(VNI && "NULL valno is not allowed");
696            if (VNI->def != DefIdx && !MO->isEarlyClobber()) {
697              report("Inconsistent valno->def", MO, MONum);
698              *OS << "Valno " << VNI->id << " is not defined at "
699                  << DefIdx << " in " << LI << '\n';
700            }
701          } else {
702            report("No live range at def", MO, MONum);
703            *OS << DefIdx << " is not live in " << LI << '\n';
704          }
705        } else {
706          report("Virtual register has no Live interval", MO, MONum);
707        }
708      }
709    }
710
711    // Check register classes.
712    if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
713      unsigned SubIdx = MO->getSubReg();
714
715      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
716        unsigned sr = Reg;
717        if (SubIdx) {
718          unsigned s = TRI->getSubReg(Reg, SubIdx);
719          if (!s) {
720            report("Invalid subregister index for physical register",
721                   MO, MONum);
722            return;
723          }
724          sr = s;
725        }
726        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
727          if (!DRC->contains(sr)) {
728            report("Illegal physical register for instruction", MO, MONum);
729            *OS << TRI->getName(sr) << " is not a "
730                << DRC->getName() << " register.\n";
731          }
732        }
733      } else {
734        // Virtual register.
735        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
736        if (SubIdx) {
737          const TargetRegisterClass *SRC = RC->getSubRegisterRegClass(SubIdx);
738          if (!SRC) {
739            report("Invalid subregister index for virtual register", MO, MONum);
740            *OS << "Register class " << RC->getName()
741                << " does not support subreg index " << SubIdx << "\n";
742            return;
743          }
744          RC = SRC;
745        }
746        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
747          if (RC != DRC && !RC->hasSuperClass(DRC)) {
748            report("Illegal virtual register for instruction", MO, MONum);
749            *OS << "Expected a " << DRC->getName() << " register, but got a "
750                << RC->getName() << " register\n";
751          }
752        }
753      }
754    }
755    break;
756  }
757
758  case MachineOperand::MO_MachineBasicBlock:
759    if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
760      report("PHI operand is not in the CFG", MO, MONum);
761    break;
762
763  case MachineOperand::MO_FrameIndex:
764    if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
765        LiveInts && !LiveInts->isNotInMIMap(MI)) {
766      LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
767      SlotIndex Idx = LiveInts->getInstructionIndex(MI);
768      if (TI.mayLoad() && !LI.liveAt(Idx.getUseIndex())) {
769        report("Instruction loads from dead spill slot", MO, MONum);
770        *OS << "Live stack: " << LI << '\n';
771      }
772      if (TI.mayStore() && !LI.liveAt(Idx.getDefIndex())) {
773        report("Instruction stores to dead spill slot", MO, MONum);
774        *OS << "Live stack: " << LI << '\n';
775      }
776    }
777    break;
778
779  default:
780    break;
781  }
782}
783
784void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
785  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
786  set_union(MInfo.regsKilled, regsKilled);
787  set_subtract(regsLive, regsKilled); regsKilled.clear();
788  set_subtract(regsLive, regsDead);   regsDead.clear();
789  set_union(regsLive, regsDefined);   regsDefined.clear();
790
791  if (Indexes && Indexes->hasIndex(MI)) {
792    SlotIndex idx = Indexes->getInstructionIndex(MI);
793    if (!(idx > lastIndex)) {
794      report("Instruction index out of order", MI);
795      *OS << "Last instruction was at " << lastIndex << '\n';
796    }
797    lastIndex = idx;
798  }
799}
800
801void
802MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
803  MBBInfoMap[MBB].regsLiveOut = regsLive;
804  regsLive.clear();
805
806  if (Indexes) {
807    SlotIndex stop = Indexes->getMBBEndIdx(MBB);
808    if (!(stop > lastIndex)) {
809      report("Block ends before last instruction index", MBB);
810      *OS << "Block ends at " << stop
811          << " last instruction was at " << lastIndex << '\n';
812    }
813    lastIndex = stop;
814  }
815}
816
817// Calculate the largest possible vregsPassed sets. These are the registers that
818// can pass through an MBB live, but may not be live every time. It is assumed
819// that all vregsPassed sets are empty before the call.
820void MachineVerifier::calcRegsPassed() {
821  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
822  // have any vregsPassed.
823  DenseSet<const MachineBasicBlock*> todo;
824  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
825       MFI != MFE; ++MFI) {
826    const MachineBasicBlock &MBB(*MFI);
827    BBInfo &MInfo = MBBInfoMap[&MBB];
828    if (!MInfo.reachable)
829      continue;
830    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
831           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
832      BBInfo &SInfo = MBBInfoMap[*SuI];
833      if (SInfo.addPassed(MInfo.regsLiveOut))
834        todo.insert(*SuI);
835    }
836  }
837
838  // Iteratively push vregsPassed to successors. This will converge to the same
839  // final state regardless of DenseSet iteration order.
840  while (!todo.empty()) {
841    const MachineBasicBlock *MBB = *todo.begin();
842    todo.erase(MBB);
843    BBInfo &MInfo = MBBInfoMap[MBB];
844    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
845           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
846      if (*SuI == MBB)
847        continue;
848      BBInfo &SInfo = MBBInfoMap[*SuI];
849      if (SInfo.addPassed(MInfo.vregsPassed))
850        todo.insert(*SuI);
851    }
852  }
853}
854
855// Calculate the set of virtual registers that must be passed through each basic
856// block in order to satisfy the requirements of successor blocks. This is very
857// similar to calcRegsPassed, only backwards.
858void MachineVerifier::calcRegsRequired() {
859  // First push live-in regs to predecessors' vregsRequired.
860  DenseSet<const MachineBasicBlock*> todo;
861  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
862       MFI != MFE; ++MFI) {
863    const MachineBasicBlock &MBB(*MFI);
864    BBInfo &MInfo = MBBInfoMap[&MBB];
865    for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
866           PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
867      BBInfo &PInfo = MBBInfoMap[*PrI];
868      if (PInfo.addRequired(MInfo.vregsLiveIn))
869        todo.insert(*PrI);
870    }
871  }
872
873  // Iteratively push vregsRequired to predecessors. This will converge to the
874  // same final state regardless of DenseSet iteration order.
875  while (!todo.empty()) {
876    const MachineBasicBlock *MBB = *todo.begin();
877    todo.erase(MBB);
878    BBInfo &MInfo = MBBInfoMap[MBB];
879    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
880           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
881      if (*PrI == MBB)
882        continue;
883      BBInfo &SInfo = MBBInfoMap[*PrI];
884      if (SInfo.addRequired(MInfo.vregsRequired))
885        todo.insert(*PrI);
886    }
887  }
888}
889
890// Check PHI instructions at the beginning of MBB. It is assumed that
891// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
892void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
893  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
894       BBI != BBE && BBI->isPHI(); ++BBI) {
895    DenseSet<const MachineBasicBlock*> seen;
896
897    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
898      unsigned Reg = BBI->getOperand(i).getReg();
899      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
900      if (!Pre->isSuccessor(MBB))
901        continue;
902      seen.insert(Pre);
903      BBInfo &PrInfo = MBBInfoMap[Pre];
904      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
905        report("PHI operand is not live-out from predecessor",
906               &BBI->getOperand(i), i);
907    }
908
909    // Did we see all predecessors?
910    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
911           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
912      if (!seen.count(*PrI)) {
913        report("Missing PHI operand", BBI);
914        *OS << "BB#" << (*PrI)->getNumber()
915            << " is a predecessor according to the CFG.\n";
916      }
917    }
918  }
919}
920
921void MachineVerifier::visitMachineFunctionAfter() {
922  calcRegsPassed();
923
924  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
925       MFI != MFE; ++MFI) {
926    BBInfo &MInfo = MBBInfoMap[MFI];
927
928    // Skip unreachable MBBs.
929    if (!MInfo.reachable)
930      continue;
931
932    checkPHIOps(MFI);
933  }
934
935  // Now check liveness info if available
936  if (LiveVars || LiveInts)
937    calcRegsRequired();
938  if (LiveVars)
939    verifyLiveVariables();
940  if (LiveInts)
941    verifyLiveIntervals();
942}
943
944void MachineVerifier::verifyLiveVariables() {
945  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
946  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
947    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
948    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
949    for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
950         MFI != MFE; ++MFI) {
951      BBInfo &MInfo = MBBInfoMap[MFI];
952
953      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
954      if (MInfo.vregsRequired.count(Reg)) {
955        if (!VI.AliveBlocks.test(MFI->getNumber())) {
956          report("LiveVariables: Block missing from AliveBlocks", MFI);
957          *OS << "Virtual register " << PrintReg(Reg)
958              << " must be live through the block.\n";
959        }
960      } else {
961        if (VI.AliveBlocks.test(MFI->getNumber())) {
962          report("LiveVariables: Block should not be in AliveBlocks", MFI);
963          *OS << "Virtual register " << PrintReg(Reg)
964              << " is not needed live through the block.\n";
965        }
966      }
967    }
968  }
969}
970
971void MachineVerifier::verifyLiveIntervals() {
972  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
973  for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
974       LVE = LiveInts->end(); LVI != LVE; ++LVI) {
975    const LiveInterval &LI = *LVI->second;
976
977    // Spilling and splitting may leave unused registers around. Skip them.
978    if (MRI->use_empty(LI.reg))
979      continue;
980
981    // Physical registers have much weirdness going on, mostly from coalescing.
982    // We should probably fix it, but for now just ignore them.
983    if (TargetRegisterInfo::isPhysicalRegister(LI.reg))
984      continue;
985
986    assert(LVI->first == LI.reg && "Invalid reg to interval mapping");
987
988    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
989         I!=E; ++I) {
990      VNInfo *VNI = *I;
991      const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
992
993      if (!DefVNI) {
994        if (!VNI->isUnused()) {
995          report("Valno not live at def and not marked unused", MF);
996          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
997        }
998        continue;
999      }
1000
1001      if (VNI->isUnused())
1002        continue;
1003
1004      if (DefVNI != VNI) {
1005        report("Live range at def has different valno", MF);
1006        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1007            << " where valno #" << DefVNI->id << " is live in " << LI << '\n';
1008        continue;
1009      }
1010
1011      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1012      if (!MBB) {
1013        report("Invalid definition index", MF);
1014        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1015            << " in " << LI << '\n';
1016        continue;
1017      }
1018
1019      if (VNI->isPHIDef()) {
1020        if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1021          report("PHIDef value is not defined at MBB start", MF);
1022          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1023              << ", not at the beginning of BB#" << MBB->getNumber()
1024              << " in " << LI << '\n';
1025        }
1026      } else {
1027        // Non-PHI def.
1028        const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1029        if (!MI) {
1030          report("No instruction at def index", MF);
1031          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1032              << " in " << LI << '\n';
1033        } else if (!MI->modifiesRegister(LI.reg, TRI)) {
1034          report("Defining instruction does not modify register", MI);
1035          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1036        }
1037
1038        bool isEarlyClobber = false;
1039        if (MI) {
1040          for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
1041               MOE = MI->operands_end(); MOI != MOE; ++MOI) {
1042            if (MOI->isReg() && MOI->getReg() == LI.reg && MOI->isDef() &&
1043                MOI->isEarlyClobber()) {
1044              isEarlyClobber = true;
1045              break;
1046            }
1047          }
1048        }
1049
1050        // Early clobber defs begin at USE slots, but other defs must begin at
1051        // DEF slots.
1052        if (isEarlyClobber) {
1053          if (!VNI->def.isUse()) {
1054            report("Early clobber def must be at a USE slot", MF);
1055            *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1056                << " in " << LI << '\n';
1057          }
1058        } else if (!VNI->def.isDef()) {
1059          report("Non-PHI, non-early clobber def must be at a DEF slot", MF);
1060          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1061              << " in " << LI << '\n';
1062        }
1063      }
1064    }
1065
1066    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
1067      const VNInfo *VNI = I->valno;
1068      assert(VNI && "Live range has no valno");
1069
1070      if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
1071        report("Foreign valno in live range", MF);
1072        I->print(*OS);
1073        *OS << " has a valno not in " << LI << '\n';
1074      }
1075
1076      if (VNI->isUnused()) {
1077        report("Live range valno is marked unused", MF);
1078        I->print(*OS);
1079        *OS << " in " << LI << '\n';
1080      }
1081
1082      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
1083      if (!MBB) {
1084        report("Bad start of live segment, no basic block", MF);
1085        I->print(*OS);
1086        *OS << " in " << LI << '\n';
1087        continue;
1088      }
1089      SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1090      if (I->start != MBBStartIdx && I->start != VNI->def) {
1091        report("Live segment must begin at MBB entry or valno def", MBB);
1092        I->print(*OS);
1093        *OS << " in " << LI << '\n' << "Basic block starts at "
1094            << MBBStartIdx << '\n';
1095      }
1096
1097      const MachineBasicBlock *EndMBB =
1098                                LiveInts->getMBBFromIndex(I->end.getPrevSlot());
1099      if (!EndMBB) {
1100        report("Bad end of live segment, no basic block", MF);
1101        I->print(*OS);
1102        *OS << " in " << LI << '\n';
1103        continue;
1104      }
1105      if (I->end != LiveInts->getMBBEndIdx(EndMBB)) {
1106        // The live segment is ending inside EndMBB
1107        const MachineInstr *MI =
1108                        LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
1109        if (!MI) {
1110          report("Live segment doesn't end at a valid instruction", EndMBB);
1111        I->print(*OS);
1112        *OS << " in " << LI << '\n' << "Basic block starts at "
1113            << MBBStartIdx << '\n';
1114        } else if (TargetRegisterInfo::isVirtualRegister(LI.reg) &&
1115                   !MI->readsVirtualRegister(LI.reg)) {
1116          // A live range can end with either a redefinition, a kill flag on a
1117          // use, or a dead flag on a def.
1118          // FIXME: Should we check for each of these?
1119          bool hasDeadDef = false;
1120          for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
1121               MOE = MI->operands_end(); MOI != MOE; ++MOI) {
1122            if (MOI->isReg() && MOI->getReg() == LI.reg && MOI->isDef() && MOI->isDead()) {
1123              hasDeadDef = true;
1124              break;
1125            }
1126          }
1127
1128          if (!hasDeadDef) {
1129            report("Instruction killing live segment neither defines nor reads "
1130                   "register", MI);
1131            I->print(*OS);
1132            *OS << " in " << LI << '\n';
1133          }
1134        }
1135      }
1136
1137      // Now check all the basic blocks in this live segment.
1138      MachineFunction::const_iterator MFI = MBB;
1139      // Is this live range the beginning of a non-PHIDef VN?
1140      if (I->start == VNI->def && !VNI->isPHIDef()) {
1141        // Not live-in to any blocks.
1142        if (MBB == EndMBB)
1143          continue;
1144        // Skip this block.
1145        ++MFI;
1146      }
1147      for (;;) {
1148        assert(LiveInts->isLiveInToMBB(LI, MFI));
1149        // We don't know how to track physregs into a landing pad.
1150        if (TargetRegisterInfo::isPhysicalRegister(LI.reg) &&
1151            MFI->isLandingPad()) {
1152          if (&*MFI == EndMBB)
1153            break;
1154          ++MFI;
1155          continue;
1156        }
1157        // Check that VNI is live-out of all predecessors.
1158        for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1159             PE = MFI->pred_end(); PI != PE; ++PI) {
1160          SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI).getPrevSlot();
1161          const VNInfo *PVNI = LI.getVNInfoAt(PEnd);
1162
1163          if (VNI->isPHIDef() && VNI->def == LiveInts->getMBBStartIdx(MFI)) {
1164            if (PVNI && !PVNI->hasPHIKill()) {
1165              report("Value live out of predecessor doesn't have PHIKill", MF);
1166              *OS << "Valno #" << PVNI->id << " live out of BB#"
1167                  << (*PI)->getNumber() << '@' << PEnd
1168                  << " doesn't have PHIKill, but Valno #" << VNI->id
1169                  << " is PHIDef and defined at the beginning of BB#"
1170                  << MFI->getNumber() << '@' << LiveInts->getMBBStartIdx(MFI)
1171                  << " in " << LI << '\n';
1172            }
1173            continue;
1174          }
1175
1176          if (!PVNI) {
1177            report("Register not marked live out of predecessor", *PI);
1178            *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1179                << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live at "
1180                << PEnd << " in " << LI << '\n';
1181            continue;
1182          }
1183
1184          if (PVNI != VNI) {
1185            report("Different value live out of predecessor", *PI);
1186            *OS << "Valno #" << PVNI->id << " live out of BB#"
1187                << (*PI)->getNumber() << '@' << PEnd
1188                << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1189                << '@' << LiveInts->getMBBStartIdx(MFI) << " in " << LI << '\n';
1190          }
1191        }
1192        if (&*MFI == EndMBB)
1193          break;
1194        ++MFI;
1195      }
1196    }
1197
1198    // Check the LI only has one connected component.
1199    if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1200      ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1201      unsigned NumComp = ConEQ.Classify(&LI);
1202      if (NumComp > 1) {
1203        report("Multiple connected components in live interval", MF);
1204        *OS << NumComp << " components in " << LI << '\n';
1205        for (unsigned comp = 0; comp != NumComp; ++comp) {
1206          *OS << comp << ": valnos";
1207          for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1208               E = LI.vni_end(); I!=E; ++I)
1209            if (comp == ConEQ.getEqClass(*I))
1210              *OS << ' ' << (*I)->id;
1211          *OS << '\n';
1212        }
1213      }
1214    }
1215  }
1216}
1217
1218