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