MachineVerifier.cpp revision 3bf7cf9f0e5a34ade5e44c47f39e3f46c8ae2c76 
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/Function.h"
27#include "llvm/CodeGen/LiveIntervalAnalysis.h"
28#include "llvm/CodeGen/LiveVariables.h"
29#include "llvm/CodeGen/MachineFunctionPass.h"
30#include "llvm/CodeGen/MachineFrameInfo.h"
31#include "llvm/CodeGen/MachineMemOperand.h"
32#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/CodeGen/Passes.h"
34#include "llvm/Target/TargetMachine.h"
35#include "llvm/Target/TargetRegisterInfo.h"
36#include "llvm/Target/TargetInstrInfo.h"
37#include "llvm/ADT/DenseSet.h"
38#include "llvm/ADT/SetOperations.h"
39#include "llvm/ADT/SmallVector.h"
40#include "llvm/Support/Debug.h"
41#include "llvm/Support/ErrorHandling.h"
42#include "llvm/Support/raw_ostream.h"
43using namespace llvm;
44
45namespace {
46  struct MachineVerifier {
47
48    MachineVerifier(Pass *pass) :
49      PASS(pass),
50      OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
51      {}
52
53    bool runOnMachineFunction(MachineFunction &MF);
54
55    Pass *const PASS;
56    const char *const OutFileName;
57    raw_ostream *OS;
58    const MachineFunction *MF;
59    const TargetMachine *TM;
60    const TargetRegisterInfo *TRI;
61    const MachineRegisterInfo *MRI;
62
63    unsigned foundErrors;
64
65    typedef SmallVector<unsigned, 16> RegVector;
66    typedef DenseSet<unsigned> RegSet;
67    typedef DenseMap<unsigned, const MachineInstr*> RegMap;
68
69    BitVector regsReserved;
70    RegSet regsLive;
71    RegVector regsDefined, regsDead, regsKilled;
72    RegSet regsLiveInButUnused;
73
74    // Add Reg and any sub-registers to RV
75    void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
76      RV.push_back(Reg);
77      if (TargetRegisterInfo::isPhysicalRegister(Reg))
78        for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
79          RV.push_back(*R);
80    }
81
82    struct BBInfo {
83      // Is this MBB reachable from the MF entry point?
84      bool reachable;
85
86      // Vregs that must be live in because they are used without being
87      // defined. Map value is the user.
88      RegMap vregsLiveIn;
89
90      // Regs killed in MBB. They may be defined again, and will then be in both
91      // regsKilled and regsLiveOut.
92      RegSet regsKilled;
93
94      // Regs defined in MBB and live out. Note that vregs passing through may
95      // be live out without being mentioned here.
96      RegSet regsLiveOut;
97
98      // Vregs that pass through MBB untouched. This set is disjoint from
99      // regsKilled and regsLiveOut.
100      RegSet vregsPassed;
101
102      // Vregs that must pass through MBB because they are needed by a successor
103      // block. This set is disjoint from regsLiveOut.
104      RegSet vregsRequired;
105
106      BBInfo() : reachable(false) {}
107
108      // Add register to vregsPassed if it belongs there. Return true if
109      // anything changed.
110      bool addPassed(unsigned Reg) {
111        if (!TargetRegisterInfo::isVirtualRegister(Reg))
112          return false;
113        if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
114          return false;
115        return vregsPassed.insert(Reg).second;
116      }
117
118      // Same for a full set.
119      bool addPassed(const RegSet &RS) {
120        bool changed = false;
121        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
122          if (addPassed(*I))
123            changed = true;
124        return changed;
125      }
126
127      // Add register to vregsRequired if it belongs there. Return true if
128      // anything changed.
129      bool addRequired(unsigned Reg) {
130        if (!TargetRegisterInfo::isVirtualRegister(Reg))
131          return false;
132        if (regsLiveOut.count(Reg))
133          return false;
134        return vregsRequired.insert(Reg).second;
135      }
136
137      // Same for a full set.
138      bool addRequired(const RegSet &RS) {
139        bool changed = false;
140        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
141          if (addRequired(*I))
142            changed = true;
143        return changed;
144      }
145
146      // Same for a full map.
147      bool addRequired(const RegMap &RM) {
148        bool changed = false;
149        for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
150          if (addRequired(I->first))
151            changed = true;
152        return changed;
153      }
154
155      // Live-out registers are either in regsLiveOut or vregsPassed.
156      bool isLiveOut(unsigned Reg) const {
157        return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
158      }
159    };
160
161    // Extra register info per MBB.
162    DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
163
164    bool isReserved(unsigned Reg) {
165      return Reg < regsReserved.size() && regsReserved.test(Reg);
166    }
167
168    // Analysis information if available
169    LiveVariables *LiveVars;
170    const LiveIntervals *LiveInts;
171
172    void visitMachineFunctionBefore();
173    void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
174    void visitMachineInstrBefore(const MachineInstr *MI);
175    void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
176    void visitMachineInstrAfter(const MachineInstr *MI);
177    void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
178    void visitMachineFunctionAfter();
179
180    void report(const char *msg, const MachineFunction *MF);
181    void report(const char *msg, const MachineBasicBlock *MBB);
182    void report(const char *msg, const MachineInstr *MI);
183    void report(const char *msg, const MachineOperand *MO, unsigned MONum);
184
185    void markReachable(const MachineBasicBlock *MBB);
186    void calcRegsPassed();
187    void checkPHIOps(const MachineBasicBlock *MBB);
188
189    void calcRegsRequired();
190    void verifyLiveVariables();
191    void verifyLiveIntervals();
192  };
193
194  struct MachineVerifierPass : public MachineFunctionPass {
195    static char ID; // Pass ID, replacement for typeid
196
197    MachineVerifierPass()
198      : MachineFunctionPass(ID) {
199        initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
200      }
201
202    void getAnalysisUsage(AnalysisUsage &AU) const {
203      AU.setPreservesAll();
204      MachineFunctionPass::getAnalysisUsage(AU);
205    }
206
207    bool runOnMachineFunction(MachineFunction &MF) {
208      MF.verify(this);
209      return false;
210    }
211  };
212
213}
214
215char MachineVerifierPass::ID = 0;
216INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
217                "Verify generated machine code", false, false)
218
219FunctionPass *llvm::createMachineVerifierPass() {
220  return new MachineVerifierPass();
221}
222
223void MachineFunction::verify(Pass *p) const {
224  MachineVerifier(p).runOnMachineFunction(const_cast<MachineFunction&>(*this));
225}
226
227bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
228  raw_ostream *OutFile = 0;
229  if (OutFileName) {
230    std::string ErrorInfo;
231    OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
232                                 raw_fd_ostream::F_Append);
233    if (!ErrorInfo.empty()) {
234      errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
235      exit(1);
236    }
237
238    OS = OutFile;
239  } else {
240    OS = &errs();
241  }
242
243  foundErrors = 0;
244
245  this->MF = &MF;
246  TM = &MF.getTarget();
247  TRI = TM->getRegisterInfo();
248  MRI = &MF.getRegInfo();
249
250  LiveVars = NULL;
251  LiveInts = NULL;
252  if (PASS) {
253    LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
254    // We don't want to verify LiveVariables if LiveIntervals is available.
255    if (!LiveInts)
256      LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
257  }
258
259  visitMachineFunctionBefore();
260  for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
261       MFI!=MFE; ++MFI) {
262    visitMachineBasicBlockBefore(MFI);
263    for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
264           MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
265      visitMachineInstrBefore(MBBI);
266      for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
267        visitMachineOperand(&MBBI->getOperand(I), I);
268      visitMachineInstrAfter(MBBI);
269    }
270    visitMachineBasicBlockAfter(MFI);
271  }
272  visitMachineFunctionAfter();
273
274  if (OutFile)
275    delete OutFile;
276  else if (foundErrors)
277    report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
278
279  // Clean up.
280  regsLive.clear();
281  regsDefined.clear();
282  regsDead.clear();
283  regsKilled.clear();
284  regsLiveInButUnused.clear();
285  MBBInfoMap.clear();
286
287  return false;                 // no changes
288}
289
290void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
291  assert(MF);
292  *OS << '\n';
293  if (!foundErrors++)
294    MF->print(*OS);
295  *OS << "*** Bad machine code: " << msg << " ***\n"
296      << "- function:    " << MF->getFunction()->getNameStr() << "\n";
297}
298
299void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
300  assert(MBB);
301  report(msg, MBB->getParent());
302  *OS << "- basic block: " << MBB->getName()
303      << " " << (void*)MBB
304      << " (BB#" << MBB->getNumber() << ")\n";
305}
306
307void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
308  assert(MI);
309  report(msg, MI->getParent());
310  *OS << "- instruction: ";
311  MI->print(*OS, TM);
312}
313
314void MachineVerifier::report(const char *msg,
315                             const MachineOperand *MO, unsigned MONum) {
316  assert(MO);
317  report(msg, MO->getParent());
318  *OS << "- operand " << MONum << ":   ";
319  MO->print(*OS, TM);
320  *OS << "\n";
321}
322
323void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
324  BBInfo &MInfo = MBBInfoMap[MBB];
325  if (!MInfo.reachable) {
326    MInfo.reachable = true;
327    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
328           SuE = MBB->succ_end(); SuI != SuE; ++SuI)
329      markReachable(*SuI);
330  }
331}
332
333void MachineVerifier::visitMachineFunctionBefore() {
334  regsReserved = TRI->getReservedRegs(*MF);
335
336  // A sub-register of a reserved register is also reserved
337  for (int Reg = regsReserved.find_first(); Reg>=0;
338       Reg = regsReserved.find_next(Reg)) {
339    for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
340      // FIXME: This should probably be:
341      // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
342      regsReserved.set(*Sub);
343    }
344  }
345  markReachable(&MF->front());
346}
347
348// Does iterator point to a and b as the first two elements?
349static bool matchPair(MachineBasicBlock::const_succ_iterator i,
350                      const MachineBasicBlock *a, const MachineBasicBlock *b) {
351  if (*i == a)
352    return *++i == b;
353  if (*i == b)
354    return *++i == a;
355  return false;
356}
357
358void
359MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
360  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
361
362  // Count the number of landing pad successors.
363  unsigned LandingPadSuccs = 0;
364  for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
365       E = MBB->succ_end(); I != E; ++I)
366    LandingPadSuccs += (*I)->isLandingPad();
367  if (LandingPadSuccs > 1)
368    report("MBB has more than one landing pad successor", MBB);
369
370  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
371  MachineBasicBlock *TBB = 0, *FBB = 0;
372  SmallVector<MachineOperand, 4> Cond;
373  if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
374                          TBB, FBB, Cond)) {
375    // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
376    // check whether its answers match up with reality.
377    if (!TBB && !FBB) {
378      // Block falls through to its successor.
379      MachineFunction::const_iterator MBBI = MBB;
380      ++MBBI;
381      if (MBBI == MF->end()) {
382        // It's possible that the block legitimately ends with a noreturn
383        // call or an unreachable, in which case it won't actually fall
384        // out the bottom of the function.
385      } else if (MBB->succ_size() == LandingPadSuccs) {
386        // It's possible that the block legitimately ends with a noreturn
387        // call or an unreachable, in which case it won't actuall fall
388        // out of the block.
389      } else if (MBB->succ_size() != 1+LandingPadSuccs) {
390        report("MBB exits via unconditional fall-through but doesn't have "
391               "exactly one CFG successor!", MBB);
392      } else if (!MBB->isSuccessor(MBBI)) {
393        report("MBB exits via unconditional fall-through but its successor "
394               "differs from its CFG successor!", MBB);
395      }
396      if (!MBB->empty() && MBB->back().getDesc().isBarrier() &&
397          !TII->isPredicated(&MBB->back())) {
398        report("MBB exits via unconditional fall-through but ends with a "
399               "barrier instruction!", MBB);
400      }
401      if (!Cond.empty()) {
402        report("MBB exits via unconditional fall-through but has a condition!",
403               MBB);
404      }
405    } else if (TBB && !FBB && Cond.empty()) {
406      // Block unconditionally branches somewhere.
407      if (MBB->succ_size() != 1+LandingPadSuccs) {
408        report("MBB exits via unconditional branch but doesn't have "
409               "exactly one CFG successor!", MBB);
410      } else if (!MBB->isSuccessor(TBB)) {
411        report("MBB exits via unconditional branch but the CFG "
412               "successor doesn't match the actual successor!", MBB);
413      }
414      if (MBB->empty()) {
415        report("MBB exits via unconditional branch but doesn't contain "
416               "any instructions!", MBB);
417      } else if (!MBB->back().getDesc().isBarrier()) {
418        report("MBB exits via unconditional branch but doesn't end with a "
419               "barrier instruction!", MBB);
420      } else if (!MBB->back().getDesc().isTerminator()) {
421        report("MBB exits via unconditional branch but the branch isn't a "
422               "terminator instruction!", MBB);
423      }
424    } else if (TBB && !FBB && !Cond.empty()) {
425      // Block conditionally branches somewhere, otherwise falls through.
426      MachineFunction::const_iterator MBBI = MBB;
427      ++MBBI;
428      if (MBBI == MF->end()) {
429        report("MBB conditionally falls through out of function!", MBB);
430      } if (MBB->succ_size() != 2) {
431        report("MBB exits via conditional branch/fall-through but doesn't have "
432               "exactly two CFG successors!", MBB);
433      } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
434        report("MBB exits via conditional branch/fall-through but the CFG "
435               "successors don't match the actual successors!", MBB);
436      }
437      if (MBB->empty()) {
438        report("MBB exits via conditional branch/fall-through but doesn't "
439               "contain any instructions!", MBB);
440      } else if (MBB->back().getDesc().isBarrier()) {
441        report("MBB exits via conditional branch/fall-through but ends with a "
442               "barrier instruction!", MBB);
443      } else if (!MBB->back().getDesc().isTerminator()) {
444        report("MBB exits via conditional branch/fall-through but the branch "
445               "isn't a terminator instruction!", MBB);
446      }
447    } else if (TBB && FBB) {
448      // Block conditionally branches somewhere, otherwise branches
449      // somewhere else.
450      if (MBB->succ_size() != 2) {
451        report("MBB exits via conditional branch/branch but doesn't have "
452               "exactly two CFG successors!", MBB);
453      } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
454        report("MBB exits via conditional branch/branch but the CFG "
455               "successors don't match the actual successors!", MBB);
456      }
457      if (MBB->empty()) {
458        report("MBB exits via conditional branch/branch but doesn't "
459               "contain any instructions!", MBB);
460      } else if (!MBB->back().getDesc().isBarrier()) {
461        report("MBB exits via conditional branch/branch but doesn't end with a "
462               "barrier instruction!", MBB);
463      } else if (!MBB->back().getDesc().isTerminator()) {
464        report("MBB exits via conditional branch/branch but the branch "
465               "isn't a terminator instruction!", MBB);
466      }
467      if (Cond.empty()) {
468        report("MBB exits via conditinal branch/branch but there's no "
469               "condition!", MBB);
470      }
471    } else {
472      report("AnalyzeBranch returned invalid data!", MBB);
473    }
474  }
475
476  regsLive.clear();
477  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
478         E = MBB->livein_end(); I != E; ++I) {
479    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
480      report("MBB live-in list contains non-physical register", MBB);
481      continue;
482    }
483    regsLive.insert(*I);
484    for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
485      regsLive.insert(*R);
486  }
487  regsLiveInButUnused = regsLive;
488
489  const MachineFrameInfo *MFI = MF->getFrameInfo();
490  assert(MFI && "Function has no frame info");
491  BitVector PR = MFI->getPristineRegs(MBB);
492  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
493    regsLive.insert(I);
494    for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
495      regsLive.insert(*R);
496  }
497
498  regsKilled.clear();
499  regsDefined.clear();
500}
501
502void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
503  const TargetInstrDesc &TI = MI->getDesc();
504  if (MI->getNumOperands() < TI.getNumOperands()) {
505    report("Too few operands", MI);
506    *OS << TI.getNumOperands() << " operands expected, but "
507        << MI->getNumExplicitOperands() << " given.\n";
508  }
509
510  // Check the MachineMemOperands for basic consistency.
511  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
512       E = MI->memoperands_end(); I != E; ++I) {
513    if ((*I)->isLoad() && !TI.mayLoad())
514      report("Missing mayLoad flag", MI);
515    if ((*I)->isStore() && !TI.mayStore())
516      report("Missing mayStore flag", MI);
517  }
518
519  // Debug values must not have a slot index.
520  // Other instructions must have one.
521  if (LiveInts) {
522    bool mapped = !LiveInts->isNotInMIMap(MI);
523    if (MI->isDebugValue()) {
524      if (mapped)
525        report("Debug instruction has a slot index", MI);
526    } else {
527      if (!mapped)
528        report("Missing slot index", MI);
529    }
530  }
531
532}
533
534void
535MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
536  const MachineInstr *MI = MO->getParent();
537  const TargetInstrDesc &TI = MI->getDesc();
538
539  // The first TI.NumDefs operands must be explicit register defines
540  if (MONum < TI.getNumDefs()) {
541    if (!MO->isReg())
542      report("Explicit definition must be a register", MO, MONum);
543    else if (!MO->isDef())
544      report("Explicit definition marked as use", MO, MONum);
545    else if (MO->isImplicit())
546      report("Explicit definition marked as implicit", MO, MONum);
547  } else if (MONum < TI.getNumOperands()) {
548    if (MO->isReg()) {
549      if (MO->isDef())
550        report("Explicit operand marked as def", MO, MONum);
551      if (MO->isImplicit())
552        report("Explicit operand marked as implicit", MO, MONum);
553    }
554  } else {
555    // ARM adds %reg0 operands to indicate predicates. We'll allow that.
556    if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic() && MO->getReg())
557      report("Extra explicit operand on non-variadic instruction", MO, MONum);
558  }
559
560  switch (MO->getType()) {
561  case MachineOperand::MO_Register: {
562    const unsigned Reg = MO->getReg();
563    if (!Reg)
564      return;
565
566    // Check Live Variables.
567    if (MO->isUndef()) {
568      // An <undef> doesn't refer to any register, so just skip it.
569    } else if (MO->isUse()) {
570      regsLiveInButUnused.erase(Reg);
571
572      bool isKill = false;
573      unsigned defIdx;
574      if (MI->isRegTiedToDefOperand(MONum, &defIdx)) {
575        // A two-addr use counts as a kill if use and def are the same.
576        unsigned DefReg = MI->getOperand(defIdx).getReg();
577        if (Reg == DefReg) {
578          isKill = true;
579          // ANd in that case an explicit kill flag is not allowed.
580          if (MO->isKill())
581            report("Illegal kill flag on two-address instruction operand",
582                   MO, MONum);
583        } else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
584          report("Two-address instruction operands must be identical",
585                 MO, MONum);
586        }
587      } else
588        isKill = MO->isKill();
589
590      if (isKill)
591        addRegWithSubRegs(regsKilled, Reg);
592
593      // Check that LiveVars knows this kill.
594      if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
595          MO->isKill()) {
596        LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
597        if (std::find(VI.Kills.begin(),
598                      VI.Kills.end(), MI) == VI.Kills.end())
599          report("Kill missing from LiveVariables", MO, MONum);
600      }
601
602      // Check LiveInts liveness and kill.
603      if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
604        SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getUseIndex();
605        if (LiveInts->hasInterval(Reg)) {
606          const LiveInterval &LI = LiveInts->getInterval(Reg);
607          if (!LI.liveAt(UseIdx)) {
608            report("No live range at use", MO, MONum);
609            *OS << UseIdx << " is not live in " << LI << '\n';
610          }
611          // TODO: Verify isKill == LI.killedAt.
612        } else if (TargetRegisterInfo::isVirtualRegister(Reg)) {
613          report("Virtual register has no Live interval", MO, MONum);
614        }
615      }
616
617      // Use of a dead register.
618      if (!regsLive.count(Reg)) {
619        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
620          // Reserved registers may be used even when 'dead'.
621          if (!isReserved(Reg))
622            report("Using an undefined physical register", MO, MONum);
623        } else {
624          BBInfo &MInfo = MBBInfoMap[MI->getParent()];
625          // We don't know which virtual registers are live in, so only complain
626          // if vreg was killed in this MBB. Otherwise keep track of vregs that
627          // must be live in. PHI instructions are handled separately.
628          if (MInfo.regsKilled.count(Reg))
629            report("Using a killed virtual register", MO, MONum);
630          else if (!MI->isPHI())
631            MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
632        }
633      }
634    } else {
635      assert(MO->isDef());
636      // Register defined.
637      // TODO: verify that earlyclobber ops are not used.
638      if (MO->isDead())
639        addRegWithSubRegs(regsDead, Reg);
640      else
641        addRegWithSubRegs(regsDefined, Reg);
642
643      // Check LiveInts for a live range, but only for virtual registers.
644      if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
645          !LiveInts->isNotInMIMap(MI)) {
646        SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getDefIndex();
647        if (LiveInts->hasInterval(Reg)) {
648          const LiveInterval &LI = LiveInts->getInterval(Reg);
649          if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
650            assert(VNI && "NULL valno is not allowed");
651            if (VNI->def != DefIdx) {
652              report("Inconsistent valno->def", MO, MONum);
653              *OS << "Valno " << VNI->id << " is not defined at "
654                  << DefIdx << " in " << LI << '\n';
655            }
656          } else {
657            report("No live range at def", MO, MONum);
658            *OS << DefIdx << " is not live in " << LI << '\n';
659          }
660        } else {
661          report("Virtual register has no Live interval", MO, MONum);
662        }
663      }
664    }
665
666    // Check register classes.
667    if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
668      const TargetOperandInfo &TOI = TI.OpInfo[MONum];
669      unsigned SubIdx = MO->getSubReg();
670
671      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
672        unsigned sr = Reg;
673        if (SubIdx) {
674          unsigned s = TRI->getSubReg(Reg, SubIdx);
675          if (!s) {
676            report("Invalid subregister index for physical register",
677                   MO, MONum);
678            return;
679          }
680          sr = s;
681        }
682        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
683          if (!DRC->contains(sr)) {
684            report("Illegal physical register for instruction", MO, MONum);
685            *OS << TRI->getName(sr) << " is not a "
686                << DRC->getName() << " register.\n";
687          }
688        }
689      } else {
690        // Virtual register.
691        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
692        if (SubIdx) {
693          const TargetRegisterClass *SRC = RC->getSubRegisterRegClass(SubIdx);
694          if (!SRC) {
695            report("Invalid subregister index for virtual register", MO, MONum);
696            *OS << "Register class " << RC->getName()
697                << " does not support subreg index " << SubIdx << "\n";
698            return;
699          }
700          RC = SRC;
701        }
702        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
703          if (RC != DRC && !RC->hasSuperClass(DRC)) {
704            report("Illegal virtual register for instruction", MO, MONum);
705            *OS << "Expected a " << DRC->getName() << " register, but got a "
706                << RC->getName() << " register\n";
707          }
708        }
709      }
710    }
711    break;
712  }
713
714  case MachineOperand::MO_MachineBasicBlock:
715    if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
716      report("PHI operand is not in the CFG", MO, MONum);
717    break;
718
719  default:
720    break;
721  }
722}
723
724void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
725  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
726  set_union(MInfo.regsKilled, regsKilled);
727  set_subtract(regsLive, regsKilled); regsKilled.clear();
728  set_subtract(regsLive, regsDead);   regsDead.clear();
729  set_union(regsLive, regsDefined);   regsDefined.clear();
730}
731
732void
733MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
734  MBBInfoMap[MBB].regsLiveOut = regsLive;
735  regsLive.clear();
736}
737
738// Calculate the largest possible vregsPassed sets. These are the registers that
739// can pass through an MBB live, but may not be live every time. It is assumed
740// that all vregsPassed sets are empty before the call.
741void MachineVerifier::calcRegsPassed() {
742  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
743  // have any vregsPassed.
744  DenseSet<const MachineBasicBlock*> todo;
745  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
746       MFI != MFE; ++MFI) {
747    const MachineBasicBlock &MBB(*MFI);
748    BBInfo &MInfo = MBBInfoMap[&MBB];
749    if (!MInfo.reachable)
750      continue;
751    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
752           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
753      BBInfo &SInfo = MBBInfoMap[*SuI];
754      if (SInfo.addPassed(MInfo.regsLiveOut))
755        todo.insert(*SuI);
756    }
757  }
758
759  // Iteratively push vregsPassed to successors. This will converge to the same
760  // final state regardless of DenseSet iteration order.
761  while (!todo.empty()) {
762    const MachineBasicBlock *MBB = *todo.begin();
763    todo.erase(MBB);
764    BBInfo &MInfo = MBBInfoMap[MBB];
765    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
766           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
767      if (*SuI == MBB)
768        continue;
769      BBInfo &SInfo = MBBInfoMap[*SuI];
770      if (SInfo.addPassed(MInfo.vregsPassed))
771        todo.insert(*SuI);
772    }
773  }
774}
775
776// Calculate the set of virtual registers that must be passed through each basic
777// block in order to satisfy the requirements of successor blocks. This is very
778// similar to calcRegsPassed, only backwards.
779void MachineVerifier::calcRegsRequired() {
780  // First push live-in regs to predecessors' vregsRequired.
781  DenseSet<const MachineBasicBlock*> todo;
782  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
783       MFI != MFE; ++MFI) {
784    const MachineBasicBlock &MBB(*MFI);
785    BBInfo &MInfo = MBBInfoMap[&MBB];
786    for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
787           PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
788      BBInfo &PInfo = MBBInfoMap[*PrI];
789      if (PInfo.addRequired(MInfo.vregsLiveIn))
790        todo.insert(*PrI);
791    }
792  }
793
794  // Iteratively push vregsRequired to predecessors. This will converge to the
795  // same final state regardless of DenseSet iteration order.
796  while (!todo.empty()) {
797    const MachineBasicBlock *MBB = *todo.begin();
798    todo.erase(MBB);
799    BBInfo &MInfo = MBBInfoMap[MBB];
800    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
801           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
802      if (*PrI == MBB)
803        continue;
804      BBInfo &SInfo = MBBInfoMap[*PrI];
805      if (SInfo.addRequired(MInfo.vregsRequired))
806        todo.insert(*PrI);
807    }
808  }
809}
810
811// Check PHI instructions at the beginning of MBB. It is assumed that
812// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
813void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
814  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
815       BBI != BBE && BBI->isPHI(); ++BBI) {
816    DenseSet<const MachineBasicBlock*> seen;
817
818    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
819      unsigned Reg = BBI->getOperand(i).getReg();
820      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
821      if (!Pre->isSuccessor(MBB))
822        continue;
823      seen.insert(Pre);
824      BBInfo &PrInfo = MBBInfoMap[Pre];
825      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
826        report("PHI operand is not live-out from predecessor",
827               &BBI->getOperand(i), i);
828    }
829
830    // Did we see all predecessors?
831    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
832           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
833      if (!seen.count(*PrI)) {
834        report("Missing PHI operand", BBI);
835        *OS << "BB#" << (*PrI)->getNumber()
836            << " is a predecessor according to the CFG.\n";
837      }
838    }
839  }
840}
841
842void MachineVerifier::visitMachineFunctionAfter() {
843  calcRegsPassed();
844
845  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
846       MFI != MFE; ++MFI) {
847    BBInfo &MInfo = MBBInfoMap[MFI];
848
849    // Skip unreachable MBBs.
850    if (!MInfo.reachable)
851      continue;
852
853    checkPHIOps(MFI);
854  }
855
856  // Now check liveness info if available
857  if (LiveVars || LiveInts)
858    calcRegsRequired();
859  if (LiveVars)
860    verifyLiveVariables();
861  if (LiveInts)
862    verifyLiveIntervals();
863}
864
865void MachineVerifier::verifyLiveVariables() {
866  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
867  for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
868         RegE = MRI->getLastVirtReg()-1; Reg != RegE; ++Reg) {
869    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
870    for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
871         MFI != MFE; ++MFI) {
872      BBInfo &MInfo = MBBInfoMap[MFI];
873
874      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
875      if (MInfo.vregsRequired.count(Reg)) {
876        if (!VI.AliveBlocks.test(MFI->getNumber())) {
877          report("LiveVariables: Block missing from AliveBlocks", MFI);
878          *OS << "Virtual register %reg" << Reg
879              << " must be live through the block.\n";
880        }
881      } else {
882        if (VI.AliveBlocks.test(MFI->getNumber())) {
883          report("LiveVariables: Block should not be in AliveBlocks", MFI);
884          *OS << "Virtual register %reg" << Reg
885              << " is not needed live through the block.\n";
886        }
887      }
888    }
889  }
890}
891
892void MachineVerifier::verifyLiveIntervals() {
893  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
894  for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
895       LVE = LiveInts->end(); LVI != LVE; ++LVI) {
896    const LiveInterval &LI = *LVI->second;
897
898    // Spilling and splitting may leave unused registers around. Skip them.
899    if (MRI->use_empty(LI.reg))
900      continue;
901
902    assert(LVI->first == LI.reg && "Invalid reg to interval mapping");
903
904    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
905         I!=E; ++I) {
906      VNInfo *VNI = *I;
907      const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
908
909      if (!DefVNI) {
910        if (!VNI->isUnused()) {
911          report("Valno not live at def and not marked unused", MF);
912          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
913        }
914        continue;
915      }
916
917      if (VNI->isUnused())
918        continue;
919
920      if (DefVNI != VNI) {
921        report("Live range at def has different valno", MF);
922        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
923            << " where valno #" << DefVNI->id << " is live.\n";
924        continue;
925      }
926
927      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
928      if (!MBB) {
929        report("Invalid definition index", MF);
930        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
931        continue;
932      }
933
934      if (VNI->isPHIDef()) {
935        if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
936          report("PHIDef value is not defined at MBB start", MF);
937          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
938              << ", not at the beginning of BB#" << MBB->getNumber() << '\n';
939        }
940      } else {
941        // Non-PHI def.
942        if (!VNI->def.isDef()) {
943          report("Non-PHI def must be at a DEF slot", MF);
944          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
945        }
946        const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
947        if (!MI) {
948          report("No instruction at def index", MF);
949          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
950        } else if (!MI->modifiesRegister(LI.reg, TRI)) {
951          report("Defining instruction does not modify register", MI);
952          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
953        }
954      }
955    }
956
957    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
958      const VNInfo *VNI = I->valno;
959      assert(VNI && "Live range has no valno");
960
961      if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
962        report("Foreign valno in live range", MF);
963        I->print(*OS);
964        *OS << " has a valno not in " << LI << '\n';
965      }
966
967      if (VNI->isUnused()) {
968        report("Live range valno is marked unused", MF);
969        I->print(*OS);
970        *OS << " in " << LI << '\n';
971      }
972
973    }
974  }
975}
976
977