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