MachineVerifier.cpp revision d71b0b0bc402d151d7ea364cad32ad44ac7fbee2 
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/MachineRegisterInfo.h"
31#include "llvm/CodeGen/Passes.h"
32#include "llvm/Target/TargetMachine.h"
33#include "llvm/Target/TargetRegisterInfo.h"
34#include "llvm/Target/TargetInstrInfo.h"
35#include "llvm/ADT/DenseSet.h"
36#include "llvm/ADT/SetOperations.h"
37#include "llvm/ADT/SmallVector.h"
38#include "llvm/Support/Compiler.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 VISIBILITY_HIDDEN MachineVerifier : public MachineFunctionPass {
46    static char ID; // Pass ID, replacement for typeid
47
48    MachineVerifier(bool allowDoubleDefs = false) :
49      MachineFunctionPass(&ID),
50      allowVirtDoubleDefs(allowDoubleDefs),
51      allowPhysDoubleDefs(allowDoubleDefs),
52      OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
53        {}
54
55    void getAnalysisUsage(AnalysisUsage &AU) const {
56      AU.setPreservesAll();
57      MachineFunctionPass::getAnalysisUsage(AU);
58    }
59
60    bool runOnMachineFunction(MachineFunction &MF);
61
62    const bool allowVirtDoubleDefs;
63    const bool allowPhysDoubleDefs;
64
65    const char *const OutFileName;
66    raw_ostream *OS;
67    const MachineFunction *MF;
68    const TargetMachine *TM;
69    const TargetRegisterInfo *TRI;
70    const MachineRegisterInfo *MRI;
71
72    unsigned foundErrors;
73
74    typedef SmallVector<unsigned, 16> RegVector;
75    typedef DenseSet<unsigned> RegSet;
76    typedef DenseMap<unsigned, const MachineInstr*> RegMap;
77
78    BitVector regsReserved;
79    RegSet regsLive;
80    RegVector regsDefined, regsDead, regsKilled;
81    RegSet regsLiveInButUnused;
82
83    // Add Reg and any sub-registers to RV
84    void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
85      RV.push_back(Reg);
86      if (TargetRegisterInfo::isPhysicalRegister(Reg))
87        for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
88          RV.push_back(*R);
89    }
90
91    struct BBInfo {
92      // Is this MBB reachable from the MF entry point?
93      bool reachable;
94
95      // Vregs that must be live in because they are used without being
96      // defined. Map value is the user.
97      RegMap vregsLiveIn;
98
99      // Vregs that must be dead in because they are defined without being
100      // killed first. Map value is the defining instruction.
101      RegMap vregsDeadIn;
102
103      // Regs killed in MBB. They may be defined again, and will then be in both
104      // regsKilled and regsLiveOut.
105      RegSet regsKilled;
106
107      // Regs defined in MBB and live out. Note that vregs passing through may
108      // be live out without being mentioned here.
109      RegSet regsLiveOut;
110
111      // Vregs that pass through MBB untouched. This set is disjoint from
112      // regsKilled and regsLiveOut.
113      RegSet vregsPassed;
114
115      BBInfo() : reachable(false) {}
116
117      // Add register to vregsPassed if it belongs there. Return true if
118      // anything changed.
119      bool addPassed(unsigned Reg) {
120        if (!TargetRegisterInfo::isVirtualRegister(Reg))
121          return false;
122        if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
123          return false;
124        return vregsPassed.insert(Reg).second;
125      }
126
127      // Same for a full set.
128      bool addPassed(const RegSet &RS) {
129        bool changed = false;
130        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
131          if (addPassed(*I))
132            changed = true;
133        return changed;
134      }
135
136      // Live-out registers are either in regsLiveOut or vregsPassed.
137      bool isLiveOut(unsigned Reg) const {
138        return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
139      }
140    };
141
142    // Extra register info per MBB.
143    DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
144
145    bool isReserved(unsigned Reg) {
146      return Reg < regsReserved.size() && regsReserved.test(Reg);
147    }
148
149    void visitMachineFunctionBefore();
150    void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
151    void visitMachineInstrBefore(const MachineInstr *MI);
152    void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
153    void visitMachineInstrAfter(const MachineInstr *MI);
154    void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
155    void visitMachineFunctionAfter();
156
157    void report(const char *msg, const MachineFunction *MF);
158    void report(const char *msg, const MachineBasicBlock *MBB);
159    void report(const char *msg, const MachineInstr *MI);
160    void report(const char *msg, const MachineOperand *MO, unsigned MONum);
161
162    void markReachable(const MachineBasicBlock *MBB);
163    void calcMaxRegsPassed();
164    void calcMinRegsPassed();
165    void checkPHIOps(const MachineBasicBlock *MBB);
166  };
167}
168
169char MachineVerifier::ID = 0;
170static RegisterPass<MachineVerifier>
171MachineVer("machineverifier", "Verify generated machine code");
172static const PassInfo *const MachineVerifyID = &MachineVer;
173
174FunctionPass *llvm::createMachineVerifierPass(bool allowPhysDoubleDefs) {
175  return new MachineVerifier(allowPhysDoubleDefs);
176}
177
178bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
179  raw_ostream *OutFile = 0;
180  if (OutFileName) {
181    std::string ErrorInfo;
182    OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
183                                 raw_fd_ostream::F_Append);
184    if (!ErrorInfo.empty()) {
185      errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
186      exit(1);
187    }
188
189    OS = OutFile;
190  } else {
191    OS = &errs();
192  }
193
194  foundErrors = 0;
195
196  this->MF = &MF;
197  TM = &MF.getTarget();
198  TRI = TM->getRegisterInfo();
199  MRI = &MF.getRegInfo();
200
201  visitMachineFunctionBefore();
202  for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
203       MFI!=MFE; ++MFI) {
204    visitMachineBasicBlockBefore(MFI);
205    for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
206           MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
207      visitMachineInstrBefore(MBBI);
208      for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
209        visitMachineOperand(&MBBI->getOperand(I), I);
210      visitMachineInstrAfter(MBBI);
211    }
212    visitMachineBasicBlockAfter(MFI);
213  }
214  visitMachineFunctionAfter();
215
216  if (OutFile)
217    delete OutFile;
218  else if (foundErrors)
219    llvm_report_error("Found "+Twine(foundErrors)+" machine code errors.");
220
221  // Clean up.
222  regsLive.clear();
223  regsDefined.clear();
224  regsDead.clear();
225  regsKilled.clear();
226  regsLiveInButUnused.clear();
227  MBBInfoMap.clear();
228
229  return false;                 // no changes
230}
231
232void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
233  assert(MF);
234  *OS << '\n';
235  if (!foundErrors++)
236    MF->print(*OS);
237  *OS << "*** Bad machine code: " << msg << " ***\n"
238      << "- function:    " << MF->getFunction()->getNameStr() << "\n";
239}
240
241void
242MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB)
243{
244  assert(MBB);
245  report(msg, MBB->getParent());
246  *OS << "- basic block: " << MBB->getBasicBlock()->getNameStr()
247      << " " << (void*)MBB
248      << " (#" << MBB->getNumber() << ")\n";
249}
250
251void
252MachineVerifier::report(const char *msg, const MachineInstr *MI)
253{
254  assert(MI);
255  report(msg, MI->getParent());
256  *OS << "- instruction: ";
257  MI->print(*OS, TM);
258}
259
260void
261MachineVerifier::report(const char *msg,
262                        const MachineOperand *MO, unsigned MONum)
263{
264  assert(MO);
265  report(msg, MO->getParent());
266  *OS << "- operand " << MONum << ":   ";
267  MO->print(*OS, TM);
268  *OS << "\n";
269}
270
271void
272MachineVerifier::markReachable(const MachineBasicBlock *MBB)
273{
274  BBInfo &MInfo = MBBInfoMap[MBB];
275  if (!MInfo.reachable) {
276    MInfo.reachable = true;
277    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
278           SuE = MBB->succ_end(); SuI != SuE; ++SuI)
279      markReachable(*SuI);
280  }
281}
282
283void
284MachineVerifier::visitMachineFunctionBefore()
285{
286  regsReserved = TRI->getReservedRegs(*MF);
287
288  // A sub-register of a reserved register is also reserved
289  for (int Reg = regsReserved.find_first(); Reg>=0;
290       Reg = regsReserved.find_next(Reg)) {
291    for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
292      // FIXME: This should probably be:
293      // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
294      regsReserved.set(*Sub);
295    }
296  }
297  markReachable(&MF->front());
298}
299
300void
301MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB)
302{
303  regsLive.clear();
304  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
305         E = MBB->livein_end(); I != E; ++I) {
306    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
307      report("MBB live-in list contains non-physical register", MBB);
308      continue;
309    }
310    regsLive.insert(*I);
311    for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
312      regsLive.insert(*R);
313  }
314  regsLiveInButUnused = regsLive;
315
316  const MachineFrameInfo *MFI = MF->getFrameInfo();
317  assert(MFI && "Function has no frame info");
318  BitVector PR = MFI->getPristineRegs(MBB);
319  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
320    regsLive.insert(I);
321    for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
322      regsLive.insert(*R);
323  }
324
325  regsKilled.clear();
326  regsDefined.clear();
327}
328
329void
330MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI)
331{
332  const TargetInstrDesc &TI = MI->getDesc();
333  if (MI->getNumExplicitOperands() < TI.getNumOperands()) {
334    report("Too few operands", MI);
335    *OS << TI.getNumOperands() << " operands expected, but "
336        << MI->getNumExplicitOperands() << " given.\n";
337  }
338  if (!TI.isVariadic()) {
339    if (MI->getNumExplicitOperands() > TI.getNumOperands()) {
340      report("Too many operands", MI);
341      *OS << TI.getNumOperands() << " operands expected, but "
342          << MI->getNumExplicitOperands() << " given.\n";
343    }
344  }
345}
346
347void
348MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum)
349{
350  const MachineInstr *MI = MO->getParent();
351  const TargetInstrDesc &TI = MI->getDesc();
352
353  // The first TI.NumDefs operands must be explicit register defines
354  if (MONum < TI.getNumDefs()) {
355    if (!MO->isReg())
356      report("Explicit definition must be a register", MO, MONum);
357    else if (!MO->isDef())
358      report("Explicit definition marked as use", MO, MONum);
359    else if (MO->isImplicit())
360      report("Explicit definition marked as implicit", MO, MONum);
361  }
362
363  switch (MO->getType()) {
364  case MachineOperand::MO_Register: {
365    const unsigned Reg = MO->getReg();
366    if (!Reg)
367      return;
368
369    // Check Live Variables.
370    if (MO->isUndef()) {
371      // An <undef> doesn't refer to any register, so just skip it.
372    } else if (MO->isUse()) {
373      regsLiveInButUnused.erase(Reg);
374
375      if (MO->isKill()) {
376        addRegWithSubRegs(regsKilled, Reg);
377        // Tied operands on two-address instuctions MUST NOT have a <kill> flag.
378        if (MI->isRegTiedToDefOperand(MONum))
379            report("Illegal kill flag on two-address instruction operand",
380                   MO, MONum);
381      } else {
382        // TwoAddress instr modifying a reg is treated as kill+def.
383        unsigned defIdx;
384        if (MI->isRegTiedToDefOperand(MONum, &defIdx) &&
385            MI->getOperand(defIdx).getReg() == Reg)
386          addRegWithSubRegs(regsKilled, Reg);
387      }
388      // Use of a dead register.
389      if (!regsLive.count(Reg)) {
390        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
391          // Reserved registers may be used even when 'dead'.
392          if (!isReserved(Reg))
393            report("Using an undefined physical register", MO, MONum);
394        } else {
395          BBInfo &MInfo = MBBInfoMap[MI->getParent()];
396          // We don't know which virtual registers are live in, so only complain
397          // if vreg was killed in this MBB. Otherwise keep track of vregs that
398          // must be live in. PHI instructions are handled separately.
399          if (MInfo.regsKilled.count(Reg))
400            report("Using a killed virtual register", MO, MONum);
401          else if (MI->getOpcode() != TargetInstrInfo::PHI)
402            MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
403        }
404      }
405    } else {
406      assert(MO->isDef());
407      // Register defined.
408      // TODO: verify that earlyclobber ops are not used.
409      if (MO->isDead())
410        addRegWithSubRegs(regsDead, Reg);
411      else
412        addRegWithSubRegs(regsDefined, Reg);
413    }
414
415    // Check register classes.
416    if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
417      const TargetOperandInfo &TOI = TI.OpInfo[MONum];
418      unsigned SubIdx = MO->getSubReg();
419
420      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
421        unsigned sr = Reg;
422        if (SubIdx) {
423          unsigned s = TRI->getSubReg(Reg, SubIdx);
424          if (!s) {
425            report("Invalid subregister index for physical register",
426                   MO, MONum);
427            return;
428          }
429          sr = s;
430        }
431        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
432          if (!DRC->contains(sr)) {
433            report("Illegal physical register for instruction", MO, MONum);
434            *OS << TRI->getName(sr) << " is not a "
435                << DRC->getName() << " register.\n";
436          }
437        }
438      } else {
439        // Virtual register.
440        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
441        if (SubIdx) {
442          if (RC->subregclasses_begin()+SubIdx >= RC->subregclasses_end()) {
443            report("Invalid subregister index for virtual register", MO, MONum);
444            return;
445          }
446          RC = *(RC->subregclasses_begin()+SubIdx);
447        }
448        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
449          if (RC != DRC && !RC->hasSuperClass(DRC)) {
450            report("Illegal virtual register for instruction", MO, MONum);
451            *OS << "Expected a " << DRC->getName() << " register, but got a "
452                << RC->getName() << " register\n";
453          }
454        }
455      }
456    }
457    break;
458  }
459    // Can PHI instrs refer to MBBs not in the CFG? X86 and ARM do.
460    // case MachineOperand::MO_MachineBasicBlock:
461    //   if (MI->getOpcode() == TargetInstrInfo::PHI) {
462    //     if (!MO->getMBB()->isSuccessor(MI->getParent()))
463    //       report("PHI operand is not in the CFG", MO, MONum);
464    //   }
465    //   break;
466  default:
467    break;
468  }
469}
470
471void
472MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI)
473{
474  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
475  set_union(MInfo.regsKilled, regsKilled);
476  set_subtract(regsLive, regsKilled);
477  regsKilled.clear();
478
479  // Verify that both <def> and <def,dead> operands refer to dead registers.
480  RegVector defs(regsDefined);
481  defs.append(regsDead.begin(), regsDead.end());
482
483  for (RegVector::const_iterator I = defs.begin(), E = defs.end();
484       I != E; ++I) {
485    if (regsLive.count(*I)) {
486      if (TargetRegisterInfo::isPhysicalRegister(*I)) {
487        if (!allowPhysDoubleDefs && !isReserved(*I) &&
488            !regsLiveInButUnused.count(*I)) {
489          report("Redefining a live physical register", MI);
490          *OS << "Register " << TRI->getName(*I)
491              << " was defined but already live.\n";
492        }
493      } else {
494        if (!allowVirtDoubleDefs) {
495          report("Redefining a live virtual register", MI);
496          *OS << "Virtual register %reg" << *I
497              << " was defined but already live.\n";
498        }
499      }
500    } else if (TargetRegisterInfo::isVirtualRegister(*I) &&
501               !MInfo.regsKilled.count(*I)) {
502      // Virtual register defined without being killed first must be dead on
503      // entry.
504      MInfo.vregsDeadIn.insert(std::make_pair(*I, MI));
505    }
506  }
507
508  set_subtract(regsLive, regsDead); regsDead.clear();
509  set_union(regsLive, regsDefined); regsDefined.clear();
510}
511
512void
513MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB)
514{
515  MBBInfoMap[MBB].regsLiveOut = regsLive;
516  regsLive.clear();
517}
518
519// Calculate the largest possible vregsPassed sets. These are the registers that
520// can pass through an MBB live, but may not be live every time. It is assumed
521// that all vregsPassed sets are empty before the call.
522void
523MachineVerifier::calcMaxRegsPassed()
524{
525  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
526  // have any vregsPassed.
527  DenseSet<const MachineBasicBlock*> todo;
528  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
529       MFI != MFE; ++MFI) {
530    const MachineBasicBlock &MBB(*MFI);
531    BBInfo &MInfo = MBBInfoMap[&MBB];
532    if (!MInfo.reachable)
533      continue;
534    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
535           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
536      BBInfo &SInfo = MBBInfoMap[*SuI];
537      if (SInfo.addPassed(MInfo.regsLiveOut))
538        todo.insert(*SuI);
539    }
540  }
541
542  // Iteratively push vregsPassed to successors. This will converge to the same
543  // final state regardless of DenseSet iteration order.
544  while (!todo.empty()) {
545    const MachineBasicBlock *MBB = *todo.begin();
546    todo.erase(MBB);
547    BBInfo &MInfo = MBBInfoMap[MBB];
548    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
549           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
550      if (*SuI == MBB)
551        continue;
552      BBInfo &SInfo = MBBInfoMap[*SuI];
553      if (SInfo.addPassed(MInfo.vregsPassed))
554        todo.insert(*SuI);
555    }
556  }
557}
558
559// Calculate the minimum vregsPassed set. These are the registers that always
560// pass live through an MBB. The calculation assumes that calcMaxRegsPassed has
561// been called earlier.
562void
563MachineVerifier::calcMinRegsPassed()
564{
565  DenseSet<const MachineBasicBlock*> todo;
566  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
567       MFI != MFE; ++MFI)
568    todo.insert(MFI);
569
570  while (!todo.empty()) {
571    const MachineBasicBlock *MBB = *todo.begin();
572    todo.erase(MBB);
573    BBInfo &MInfo = MBBInfoMap[MBB];
574
575    // Remove entries from vRegsPassed that are not live out from all
576    // reachable predecessors.
577    RegSet dead;
578    for (RegSet::iterator I = MInfo.vregsPassed.begin(),
579           E = MInfo.vregsPassed.end(); I != E; ++I) {
580      for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
581             PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
582        BBInfo &PrInfo = MBBInfoMap[*PrI];
583        if (PrInfo.reachable && !PrInfo.isLiveOut(*I)) {
584          dead.insert(*I);
585          break;
586        }
587      }
588    }
589    // If any regs removed, we need to recheck successors.
590    if (!dead.empty()) {
591      set_subtract(MInfo.vregsPassed, dead);
592      todo.insert(MBB->succ_begin(), MBB->succ_end());
593    }
594  }
595}
596
597// Check PHI instructions at the beginning of MBB. It is assumed that
598// calcMinRegsPassed has been run so BBInfo::isLiveOut is valid.
599void
600MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB)
601{
602  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
603       BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
604    DenseSet<const MachineBasicBlock*> seen;
605
606    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
607      unsigned Reg = BBI->getOperand(i).getReg();
608      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
609      if (!Pre->isSuccessor(MBB))
610        continue;
611      seen.insert(Pre);
612      BBInfo &PrInfo = MBBInfoMap[Pre];
613      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
614        report("PHI operand is not live-out from predecessor",
615               &BBI->getOperand(i), i);
616    }
617
618    // Did we see all predecessors?
619    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
620           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
621      if (!seen.count(*PrI)) {
622        report("Missing PHI operand", BBI);
623        *OS << "MBB #" << (*PrI)->getNumber()
624            << " is a predecessor according to the CFG.\n";
625      }
626    }
627  }
628}
629
630void
631MachineVerifier::visitMachineFunctionAfter()
632{
633  calcMaxRegsPassed();
634
635  // With the maximal set of vregsPassed we can verify dead-in registers.
636  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
637       MFI != MFE; ++MFI) {
638    BBInfo &MInfo = MBBInfoMap[MFI];
639
640    // Skip unreachable MBBs.
641    if (!MInfo.reachable)
642      continue;
643
644    for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
645           PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
646      BBInfo &PrInfo = MBBInfoMap[*PrI];
647      if (!PrInfo.reachable)
648        continue;
649
650      // Verify physical live-ins. EH landing pads have magic live-ins so we
651      // ignore them.
652      if (!MFI->isLandingPad()) {
653        for (MachineBasicBlock::const_livein_iterator I = MFI->livein_begin(),
654               E = MFI->livein_end(); I != E; ++I) {
655          if (TargetRegisterInfo::isPhysicalRegister(*I) &&
656              !isReserved (*I) && !PrInfo.isLiveOut(*I)) {
657            report("Live-in physical register is not live-out from predecessor",
658                   MFI);
659            *OS << "Register " << TRI->getName(*I)
660                << " is not live-out from MBB #" << (*PrI)->getNumber()
661                << ".\n";
662          }
663        }
664      }
665
666
667      // Verify dead-in virtual registers.
668      if (!allowVirtDoubleDefs) {
669        for (RegMap::iterator I = MInfo.vregsDeadIn.begin(),
670               E = MInfo.vregsDeadIn.end(); I != E; ++I) {
671          // DeadIn register must be in neither regsLiveOut or vregsPassed of
672          // any predecessor.
673          if (PrInfo.isLiveOut(I->first)) {
674            report("Live-in virtual register redefined", I->second);
675            *OS << "Register %reg" << I->first
676                << " was live-out from predecessor MBB #"
677                << (*PrI)->getNumber() << ".\n";
678          }
679        }
680      }
681    }
682  }
683
684  calcMinRegsPassed();
685
686  // With the minimal set of vregsPassed we can verify live-in virtual
687  // registers, including PHI instructions.
688  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
689       MFI != MFE; ++MFI) {
690    BBInfo &MInfo = MBBInfoMap[MFI];
691
692    // Skip unreachable MBBs.
693    if (!MInfo.reachable)
694      continue;
695
696    checkPHIOps(MFI);
697
698    for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
699           PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
700      BBInfo &PrInfo = MBBInfoMap[*PrI];
701      if (!PrInfo.reachable)
702        continue;
703
704      for (RegMap::iterator I = MInfo.vregsLiveIn.begin(),
705             E = MInfo.vregsLiveIn.end(); I != E; ++I) {
706        if (!PrInfo.isLiveOut(I->first)) {
707          report("Used virtual register is not live-in", I->second);
708          *OS << "Register %reg" << I->first
709              << " is not live-out from predecessor MBB #"
710              << (*PrI)->getNumber()
711              << ".\n";
712        }
713      }
714    }
715  }
716}
717