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