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