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