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