MachineVerifier.cpp revision bb0721680c329625f47c090f48dcafb2fe14101c 
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() && getBundleStart(&MBB->back())->isBarrier() &&
480          !TII->isPredicated(getBundleStart(&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 (!getBundleStart(&MBB->back())->isBarrier()) {
501        report("MBB exits via unconditional branch but doesn't end with a "
502               "barrier instruction!", MBB);
503      } else if (!getBundleStart(&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 (getBundleStart(&MBB->back())->isBarrier()) {
524        report("MBB exits via conditional branch/fall-through but ends with a "
525               "barrier instruction!", MBB);
526      } else if (!getBundleStart(&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 (!getBundleStart(&MBB->back())->isBarrier()) {
544        report("MBB exits via conditional branch/branch but doesn't end with a "
545               "barrier instruction!", MBB);
546      } else if (!getBundleStart(&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  // Ensure non-terminators don't follow terminators.
601  // Ignore predicated terminators formed by if conversion.
602  // FIXME: If conversion shouldn't need to violate this rule.
603  if (MI->isTerminator() && !TII->isPredicated(MI)) {
604    if (!FirstTerminator)
605      FirstTerminator = MI;
606  } else if (FirstTerminator) {
607    report("Non-terminator instruction after the first terminator", MI);
608    *OS << "First terminator was:\t" << *FirstTerminator;
609  }
610}
611
612void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
613  const MCInstrDesc &MCID = MI->getDesc();
614  if (MI->getNumOperands() < MCID.getNumOperands()) {
615    report("Too few operands", MI);
616    *OS << MCID.getNumOperands() << " operands expected, but "
617        << MI->getNumExplicitOperands() << " given.\n";
618  }
619
620  // Check the MachineMemOperands for basic consistency.
621  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
622       E = MI->memoperands_end(); I != E; ++I) {
623    if ((*I)->isLoad() && !MI->mayLoad())
624      report("Missing mayLoad flag", MI);
625    if ((*I)->isStore() && !MI->mayStore())
626      report("Missing mayStore flag", MI);
627  }
628
629  // Debug values must not have a slot index.
630  // Other instructions must have one, unless they are inside a bundle.
631  if (LiveInts) {
632    bool mapped = !LiveInts->isNotInMIMap(MI);
633    if (MI->isDebugValue()) {
634      if (mapped)
635        report("Debug instruction has a slot index", MI);
636    } else if (MI->isInsideBundle()) {
637      if (mapped)
638        report("Instruction inside bundle has a slot index", MI);
639    } else {
640      if (!mapped)
641        report("Missing slot index", MI);
642    }
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);
870      DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
871      if (LiveInts->hasInterval(Reg)) {
872        const LiveInterval &LI = LiveInts->getInterval(Reg);
873        if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
874          assert(VNI && "NULL valno is not allowed");
875          if (VNI->def != DefIdx) {
876            report("Inconsistent valno->def", MO, MONum);
877            *OS << "Valno " << VNI->id << " is not defined at "
878              << DefIdx << " in " << LI << '\n';
879          }
880        } else {
881          report("No live range at def", MO, MONum);
882          *OS << DefIdx << " is not live in " << LI << '\n';
883        }
884      } else {
885        report("Virtual register has no Live interval", MO, MONum);
886      }
887    }
888  }
889}
890
891void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
892}
893
894// This function gets called after visiting all instructions in a bundle. The
895// argument points to the bundle header.
896// Normal stand-alone instructions are also considered 'bundles', and this
897// function is called for all of them.
898void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
899  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
900  set_union(MInfo.regsKilled, regsKilled);
901  set_subtract(regsLive, regsKilled); regsKilled.clear();
902  // Kill any masked registers.
903  while (!regMasks.empty()) {
904    const uint32_t *Mask = regMasks.pop_back_val();
905    for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
906      if (TargetRegisterInfo::isPhysicalRegister(*I) &&
907          MachineOperand::clobbersPhysReg(Mask, *I))
908        regsDead.push_back(*I);
909  }
910  set_subtract(regsLive, regsDead);   regsDead.clear();
911  set_union(regsLive, regsDefined);   regsDefined.clear();
912}
913
914void
915MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
916  MBBInfoMap[MBB].regsLiveOut = regsLive;
917  regsLive.clear();
918
919  if (Indexes) {
920    SlotIndex stop = Indexes->getMBBEndIdx(MBB);
921    if (!(stop > lastIndex)) {
922      report("Block ends before last instruction index", MBB);
923      *OS << "Block ends at " << stop
924          << " last instruction was at " << lastIndex << '\n';
925    }
926    lastIndex = stop;
927  }
928}
929
930// Calculate the largest possible vregsPassed sets. These are the registers that
931// can pass through an MBB live, but may not be live every time. It is assumed
932// that all vregsPassed sets are empty before the call.
933void MachineVerifier::calcRegsPassed() {
934  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
935  // have any vregsPassed.
936  SmallPtrSet<const MachineBasicBlock*, 8> todo;
937  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
938       MFI != MFE; ++MFI) {
939    const MachineBasicBlock &MBB(*MFI);
940    BBInfo &MInfo = MBBInfoMap[&MBB];
941    if (!MInfo.reachable)
942      continue;
943    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
944           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
945      BBInfo &SInfo = MBBInfoMap[*SuI];
946      if (SInfo.addPassed(MInfo.regsLiveOut))
947        todo.insert(*SuI);
948    }
949  }
950
951  // Iteratively push vregsPassed to successors. This will converge to the same
952  // final state regardless of DenseSet iteration order.
953  while (!todo.empty()) {
954    const MachineBasicBlock *MBB = *todo.begin();
955    todo.erase(MBB);
956    BBInfo &MInfo = MBBInfoMap[MBB];
957    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
958           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
959      if (*SuI == MBB)
960        continue;
961      BBInfo &SInfo = MBBInfoMap[*SuI];
962      if (SInfo.addPassed(MInfo.vregsPassed))
963        todo.insert(*SuI);
964    }
965  }
966}
967
968// Calculate the set of virtual registers that must be passed through each basic
969// block in order to satisfy the requirements of successor blocks. This is very
970// similar to calcRegsPassed, only backwards.
971void MachineVerifier::calcRegsRequired() {
972  // First push live-in regs to predecessors' vregsRequired.
973  SmallPtrSet<const MachineBasicBlock*, 8> todo;
974  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
975       MFI != MFE; ++MFI) {
976    const MachineBasicBlock &MBB(*MFI);
977    BBInfo &MInfo = MBBInfoMap[&MBB];
978    for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
979           PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
980      BBInfo &PInfo = MBBInfoMap[*PrI];
981      if (PInfo.addRequired(MInfo.vregsLiveIn))
982        todo.insert(*PrI);
983    }
984  }
985
986  // Iteratively push vregsRequired to predecessors. This will converge to the
987  // same final state regardless of DenseSet iteration order.
988  while (!todo.empty()) {
989    const MachineBasicBlock *MBB = *todo.begin();
990    todo.erase(MBB);
991    BBInfo &MInfo = MBBInfoMap[MBB];
992    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
993           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
994      if (*PrI == MBB)
995        continue;
996      BBInfo &SInfo = MBBInfoMap[*PrI];
997      if (SInfo.addRequired(MInfo.vregsRequired))
998        todo.insert(*PrI);
999    }
1000  }
1001}
1002
1003// Check PHI instructions at the beginning of MBB. It is assumed that
1004// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
1005void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
1006  SmallPtrSet<const MachineBasicBlock*, 8> seen;
1007  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
1008       BBI != BBE && BBI->isPHI(); ++BBI) {
1009    seen.clear();
1010
1011    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
1012      unsigned Reg = BBI->getOperand(i).getReg();
1013      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
1014      if (!Pre->isSuccessor(MBB))
1015        continue;
1016      seen.insert(Pre);
1017      BBInfo &PrInfo = MBBInfoMap[Pre];
1018      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
1019        report("PHI operand is not live-out from predecessor",
1020               &BBI->getOperand(i), i);
1021    }
1022
1023    // Did we see all predecessors?
1024    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1025           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1026      if (!seen.count(*PrI)) {
1027        report("Missing PHI operand", BBI);
1028        *OS << "BB#" << (*PrI)->getNumber()
1029            << " is a predecessor according to the CFG.\n";
1030      }
1031    }
1032  }
1033}
1034
1035void MachineVerifier::visitMachineFunctionAfter() {
1036  calcRegsPassed();
1037
1038  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1039       MFI != MFE; ++MFI) {
1040    BBInfo &MInfo = MBBInfoMap[MFI];
1041
1042    // Skip unreachable MBBs.
1043    if (!MInfo.reachable)
1044      continue;
1045
1046    checkPHIOps(MFI);
1047  }
1048
1049  // Now check liveness info if available
1050  calcRegsRequired();
1051
1052  // Check for killed virtual registers that should be live out.
1053  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1054       MFI != MFE; ++MFI) {
1055    BBInfo &MInfo = MBBInfoMap[MFI];
1056    for (RegSet::iterator
1057         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1058         ++I)
1059      if (MInfo.regsKilled.count(*I)) {
1060	report("Virtual register killed in block, but needed live out.", MFI);
1061	*OS << "Virtual register " << PrintReg(*I)
1062            << " is used after the block.\n";
1063      }
1064  }
1065
1066  if (!MF->empty()) {
1067    BBInfo &MInfo = MBBInfoMap[&MF->front()];
1068    for (RegSet::iterator
1069         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1070         ++I)
1071      report("Virtual register def doesn't dominate all uses.",
1072             MRI->getVRegDef(*I));
1073  }
1074
1075  if (LiveVars)
1076    verifyLiveVariables();
1077  if (LiveInts)
1078    verifyLiveIntervals();
1079}
1080
1081void MachineVerifier::verifyLiveVariables() {
1082  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
1083  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1084    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1085    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1086    for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1087         MFI != MFE; ++MFI) {
1088      BBInfo &MInfo = MBBInfoMap[MFI];
1089
1090      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1091      if (MInfo.vregsRequired.count(Reg)) {
1092        if (!VI.AliveBlocks.test(MFI->getNumber())) {
1093          report("LiveVariables: Block missing from AliveBlocks", MFI);
1094          *OS << "Virtual register " << PrintReg(Reg)
1095              << " must be live through the block.\n";
1096        }
1097      } else {
1098        if (VI.AliveBlocks.test(MFI->getNumber())) {
1099          report("LiveVariables: Block should not be in AliveBlocks", MFI);
1100          *OS << "Virtual register " << PrintReg(Reg)
1101              << " is not needed live through the block.\n";
1102        }
1103      }
1104    }
1105  }
1106}
1107
1108void MachineVerifier::verifyLiveIntervals() {
1109  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
1110  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1111    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1112
1113    // Spilling and splitting may leave unused registers around. Skip them.
1114    if (MRI->reg_nodbg_empty(Reg))
1115      continue;
1116
1117    if (!LiveInts->hasInterval(Reg)) {
1118      report("Missing live interval for virtual register", MF);
1119      *OS << PrintReg(Reg, TRI) << " still has defs or uses\n";
1120      continue;
1121    }
1122
1123    const LiveInterval &LI = LiveInts->getInterval(Reg);
1124    assert(Reg == LI.reg && "Invalid reg to interval mapping");
1125
1126    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
1127         I!=E; ++I) {
1128      VNInfo *VNI = *I;
1129      const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
1130
1131      if (!DefVNI) {
1132        if (!VNI->isUnused()) {
1133          report("Valno not live at def and not marked unused", MF);
1134          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1135        }
1136        continue;
1137      }
1138
1139      if (VNI->isUnused())
1140        continue;
1141
1142      if (DefVNI != VNI) {
1143        report("Live range at def has different valno", MF);
1144        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1145            << " where valno #" << DefVNI->id << " is live in " << LI << '\n';
1146        continue;
1147      }
1148
1149      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1150      if (!MBB) {
1151        report("Invalid definition index", MF);
1152        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1153            << " in " << LI << '\n';
1154        continue;
1155      }
1156
1157      if (VNI->isPHIDef()) {
1158        if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1159          report("PHIDef value is not defined at MBB start", MF);
1160          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1161              << ", not at the beginning of BB#" << MBB->getNumber()
1162              << " in " << LI << '\n';
1163        }
1164      } else {
1165        // Non-PHI def.
1166        const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1167        if (!MI) {
1168          report("No instruction at def index", MF);
1169          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1170              << " in " << LI << '\n';
1171          continue;
1172        }
1173
1174        bool hasDef = false;
1175        bool isEarlyClobber = false;
1176        for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1177          if (!MOI->isReg() || !MOI->isDef())
1178            continue;
1179          if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1180            if (MOI->getReg() != LI.reg)
1181              continue;
1182          } else {
1183            if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1184                !TRI->regsOverlap(LI.reg, MOI->getReg()))
1185              continue;
1186          }
1187          hasDef = true;
1188          if (MOI->isEarlyClobber())
1189            isEarlyClobber = true;
1190        }
1191
1192        if (!hasDef) {
1193          report("Defining instruction does not modify register", MI);
1194          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1195        }
1196
1197        // Early clobber defs begin at USE slots, but other defs must begin at
1198        // DEF slots.
1199        if (isEarlyClobber) {
1200          if (!VNI->def.isEarlyClobber()) {
1201            report("Early clobber def must be at an early-clobber slot", MF);
1202            *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1203                << " in " << LI << '\n';
1204          }
1205        } else if (!VNI->def.isRegister()) {
1206          report("Non-PHI, non-early clobber def must be at a register slot",
1207                 MF);
1208          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1209              << " in " << LI << '\n';
1210        }
1211      }
1212    }
1213
1214    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
1215      const VNInfo *VNI = I->valno;
1216      assert(VNI && "Live range has no valno");
1217
1218      if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
1219        report("Foreign valno in live range", MF);
1220        I->print(*OS);
1221        *OS << " has a valno not in " << LI << '\n';
1222      }
1223
1224      if (VNI->isUnused()) {
1225        report("Live range valno is marked unused", MF);
1226        I->print(*OS);
1227        *OS << " in " << LI << '\n';
1228      }
1229
1230      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
1231      if (!MBB) {
1232        report("Bad start of live segment, no basic block", MF);
1233        I->print(*OS);
1234        *OS << " in " << LI << '\n';
1235        continue;
1236      }
1237      SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1238      if (I->start != MBBStartIdx && I->start != VNI->def) {
1239        report("Live segment must begin at MBB entry or valno def", MBB);
1240        I->print(*OS);
1241        *OS << " in " << LI << '\n' << "Basic block starts at "
1242            << MBBStartIdx << '\n';
1243      }
1244
1245      const MachineBasicBlock *EndMBB =
1246                                LiveInts->getMBBFromIndex(I->end.getPrevSlot());
1247      if (!EndMBB) {
1248        report("Bad end of live segment, no basic block", MF);
1249        I->print(*OS);
1250        *OS << " in " << LI << '\n';
1251        continue;
1252      }
1253
1254      // No more checks for live-out segments.
1255      if (I->end == LiveInts->getMBBEndIdx(EndMBB))
1256        continue;
1257
1258      // The live segment is ending inside EndMBB
1259      const MachineInstr *MI =
1260        LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
1261      if (!MI) {
1262        report("Live segment doesn't end at a valid instruction", EndMBB);
1263        I->print(*OS);
1264        *OS << " in " << LI << '\n' << "Basic block starts at "
1265          << MBBStartIdx << '\n';
1266        continue;
1267      }
1268
1269      // The block slot must refer to a basic block boundary.
1270      if (I->end.isBlock()) {
1271        report("Live segment ends at B slot of an instruction", MI);
1272        I->print(*OS);
1273        *OS << " in " << LI << '\n';
1274      }
1275
1276      if (I->end.isDead()) {
1277        // Segment ends on the dead slot.
1278        // That means there must be a dead def.
1279        if (!SlotIndex::isSameInstr(I->start, I->end)) {
1280          report("Live segment ending at dead slot spans instructions", MI);
1281          I->print(*OS);
1282          *OS << " in " << LI << '\n';
1283        }
1284      }
1285
1286      // A live segment can only end at an early-clobber slot if it is being
1287      // redefined by an early-clobber def.
1288      if (I->end.isEarlyClobber()) {
1289        if (I+1 == E || (I+1)->start != I->end) {
1290          report("Live segment ending at early clobber slot must be "
1291                 "redefined by an EC def in the same instruction", MI);
1292          I->print(*OS);
1293          *OS << " in " << LI << '\n';
1294        }
1295      }
1296
1297      // The following checks only apply to virtual registers. Physreg liveness
1298      // is too weird to check.
1299      if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1300        // A live range can end with either a redefinition, a kill flag on a
1301        // use, or a dead flag on a def.
1302        bool hasRead = false;
1303        bool hasDeadDef = false;
1304        for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1305          if (!MOI->isReg() || MOI->getReg() != LI.reg)
1306            continue;
1307          if (MOI->readsReg())
1308            hasRead = true;
1309          if (MOI->isDef() && MOI->isDead())
1310            hasDeadDef = true;
1311        }
1312
1313        if (I->end.isDead()) {
1314          if (!hasDeadDef) {
1315            report("Instruction doesn't have a dead def operand", MI);
1316            I->print(*OS);
1317            *OS << " in " << LI << '\n';
1318          }
1319        } else {
1320          if (!hasRead) {
1321            report("Instruction ending live range doesn't read the register",
1322                   MI);
1323            I->print(*OS);
1324            *OS << " in " << LI << '\n';
1325          }
1326        }
1327      }
1328
1329      // Now check all the basic blocks in this live segment.
1330      MachineFunction::const_iterator MFI = MBB;
1331      // Is this live range the beginning of a non-PHIDef VN?
1332      if (I->start == VNI->def && !VNI->isPHIDef()) {
1333        // Not live-in to any blocks.
1334        if (MBB == EndMBB)
1335          continue;
1336        // Skip this block.
1337        ++MFI;
1338      }
1339      for (;;) {
1340        assert(LiveInts->isLiveInToMBB(LI, MFI));
1341        // We don't know how to track physregs into a landing pad.
1342        if (TargetRegisterInfo::isPhysicalRegister(LI.reg) &&
1343            MFI->isLandingPad()) {
1344          if (&*MFI == EndMBB)
1345            break;
1346          ++MFI;
1347          continue;
1348        }
1349
1350        // Is VNI a PHI-def in the current block?
1351        bool IsPHI = VNI->isPHIDef() &&
1352                     VNI->def == LiveInts->getMBBStartIdx(MFI);
1353
1354        // Check that VNI is live-out of all predecessors.
1355        for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1356             PE = MFI->pred_end(); PI != PE; ++PI) {
1357          SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
1358          const VNInfo *PVNI = LI.getVNInfoBefore(PEnd);
1359
1360          // All predecessors must have a live-out value.
1361          if (!PVNI) {
1362            report("Register not marked live out of predecessor", *PI);
1363            *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1364                << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
1365                << PEnd << " in " << LI << '\n';
1366            continue;
1367          }
1368
1369          // Only PHI-defs can take different predecessor values.
1370          if (!IsPHI && PVNI != VNI) {
1371            report("Different value live out of predecessor", *PI);
1372            *OS << "Valno #" << PVNI->id << " live out of BB#"
1373                << (*PI)->getNumber() << '@' << PEnd
1374                << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1375                << '@' << LiveInts->getMBBStartIdx(MFI) << " in "
1376                << PrintReg(Reg) << ": " << LI << '\n';
1377          }
1378        }
1379        if (&*MFI == EndMBB)
1380          break;
1381        ++MFI;
1382      }
1383    }
1384
1385    // Check the LI only has one connected component.
1386    if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1387      ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1388      unsigned NumComp = ConEQ.Classify(&LI);
1389      if (NumComp > 1) {
1390        report("Multiple connected components in live interval", MF);
1391        *OS << NumComp << " components in " << LI << '\n';
1392        for (unsigned comp = 0; comp != NumComp; ++comp) {
1393          *OS << comp << ": valnos";
1394          for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1395               E = LI.vni_end(); I!=E; ++I)
1396            if (comp == ConEQ.getEqClass(*I))
1397              *OS << ' ' << (*I)->id;
1398          *OS << '\n';
1399        }
1400      }
1401    }
1402  }
1403}
1404