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