MachineVerifier.cpp revision cc0aeb29f77c1d84341f2843edf6c0f78642f125 
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 MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
242  assert(MBB);
243  report(msg, MBB->getParent());
244  *OS << "- basic block: " << MBB->getBasicBlock()->getNameStr()
245      << " " << (void*)MBB
246      << " (#" << MBB->getNumber() << ")\n";
247}
248
249void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
250  assert(MI);
251  report(msg, MI->getParent());
252  *OS << "- instruction: ";
253  MI->print(*OS, TM);
254}
255
256void MachineVerifier::report(const char *msg,
257                             const MachineOperand *MO, unsigned MONum) {
258  assert(MO);
259  report(msg, MO->getParent());
260  *OS << "- operand " << MONum << ":   ";
261  MO->print(*OS, TM);
262  *OS << "\n";
263}
264
265void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
266  BBInfo &MInfo = MBBInfoMap[MBB];
267  if (!MInfo.reachable) {
268    MInfo.reachable = true;
269    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
270           SuE = MBB->succ_end(); SuI != SuE; ++SuI)
271      markReachable(*SuI);
272  }
273}
274
275void MachineVerifier::visitMachineFunctionBefore() {
276  regsReserved = TRI->getReservedRegs(*MF);
277
278  // A sub-register of a reserved register is also reserved
279  for (int Reg = regsReserved.find_first(); Reg>=0;
280       Reg = regsReserved.find_next(Reg)) {
281    for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
282      // FIXME: This should probably be:
283      // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
284      regsReserved.set(*Sub);
285    }
286  }
287  markReachable(&MF->front());
288}
289
290void MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
291  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
292
293  // Start with minimal CFG sanity checks.
294  MachineFunction::const_iterator MBBI = MBB;
295  ++MBBI;
296  if (MBBI != MF->end()) {
297    // Block is not last in function.
298    if (!MBB->isSuccessor(MBBI)) {
299      // Block does not fall through.
300      if (MBB->empty()) {
301        report("MBB doesn't fall through but is empty!", MBB);
302      }
303    }
304    if (TII->BlockHasNoFallThrough(*MBB)) {
305      if (MBB->empty()) {
306        report("TargetInstrInfo says the block has no fall through, but the "
307               "block is empty!", MBB);
308      } else if (!MBB->back().getDesc().isBarrier()) {
309        report("TargetInstrInfo says the block has no fall through, but the "
310               "block does not end in a barrier!", MBB);
311      }
312    }
313  } else {
314    // Block is last in function.
315    if (MBB->empty()) {
316      report("MBB is last in function but is empty!", MBB);
317    }
318  }
319
320  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
321  MachineBasicBlock *TBB = 0, *FBB = 0;
322  SmallVector<MachineOperand, 4> Cond;
323  if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
324                          TBB, FBB, Cond)) {
325    // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
326    // check whether its answers match up with reality.
327    if (!TBB && !FBB) {
328      // Block falls through to its successor.
329      MachineFunction::const_iterator MBBI = MBB;
330      ++MBBI;
331      if (MBBI == MF->end()) {
332        // It's possible that the block legitimately ends with a noreturn
333        // call or an unreachable, in which case it won't actually fall
334        // out the bottom of the function.
335      } else if (MBB->succ_empty()) {
336        // It's possible that the block legitimately ends with a noreturn
337        // call or an unreachable, in which case it won't actuall fall
338        // out of the block.
339      } else if (MBB->succ_size() != 1) {
340        report("MBB exits via unconditional fall-through but doesn't have "
341               "exactly one CFG successor!", MBB);
342      } else if (MBB->succ_begin()[0] != MBBI) {
343        report("MBB exits via unconditional fall-through but its successor "
344               "differs from its CFG successor!", MBB);
345      }
346      if (!MBB->empty() && MBB->back().getDesc().isBarrier()) {
347        report("MBB exits via unconditional fall-through but ends with a "
348               "barrier instruction!", MBB);
349      }
350      if (!Cond.empty()) {
351        report("MBB exits via unconditional fall-through but has a condition!",
352               MBB);
353      }
354    } else if (TBB && !FBB && Cond.empty()) {
355      // Block unconditionally branches somewhere.
356      if (MBB->succ_size() != 1) {
357        report("MBB exits via unconditional branch but doesn't have "
358               "exactly one CFG successor!", MBB);
359      } else if (MBB->succ_begin()[0] != TBB) {
360        report("MBB exits via unconditional branch but the CFG "
361               "successor doesn't match the actual successor!", MBB);
362      }
363      if (MBB->empty()) {
364        report("MBB exits via unconditional branch but doesn't contain "
365               "any instructions!", MBB);
366      } else if (!MBB->back().getDesc().isBarrier()) {
367        report("MBB exits via unconditional branch but doesn't end with a "
368               "barrier instruction!", MBB);
369      } else if (!MBB->back().getDesc().isTerminator()) {
370        report("MBB exits via unconditional branch but the branch isn't a "
371               "terminator instruction!", MBB);
372      }
373    } else if (TBB && !FBB && !Cond.empty()) {
374      // Block conditionally branches somewhere, otherwise falls through.
375      MachineFunction::const_iterator MBBI = MBB;
376      ++MBBI;
377      if (MBBI == MF->end()) {
378        report("MBB conditionally falls through out of function!", MBB);
379      } if (MBB->succ_size() != 2) {
380        report("MBB exits via conditional branch/fall-through but doesn't have "
381               "exactly two CFG successors!", MBB);
382      } else if ((MBB->succ_begin()[0] == TBB && MBB->succ_end()[1] == MBBI) ||
383                 (MBB->succ_begin()[1] == TBB && MBB->succ_end()[0] == MBBI)) {
384        report("MBB exits via conditional branch/fall-through but the CFG "
385               "successors don't match the actual successors!", MBB);
386      }
387      if (MBB->empty()) {
388        report("MBB exits via conditional branch/fall-through but doesn't "
389               "contain any instructions!", MBB);
390      } else if (MBB->back().getDesc().isBarrier()) {
391        report("MBB exits via conditional branch/fall-through but ends with a "
392               "barrier instruction!", MBB);
393      } else if (!MBB->back().getDesc().isTerminator()) {
394        report("MBB exits via conditional branch/fall-through but the branch "
395               "isn't a terminator instruction!", MBB);
396      }
397    } else if (TBB && FBB) {
398      // Block conditionally branches somewhere, otherwise branches
399      // somewhere else.
400      if (MBB->succ_size() != 2) {
401        report("MBB exits via conditional branch/branch but doesn't have "
402               "exactly two CFG successors!", MBB);
403      } else if ((MBB->succ_begin()[0] == TBB && MBB->succ_end()[1] == FBB) ||
404                 (MBB->succ_begin()[1] == TBB && MBB->succ_end()[0] == FBB)) {
405        report("MBB exits via conditional branch/branch but the CFG "
406               "successors don't match the actual successors!", MBB);
407      }
408      if (MBB->empty()) {
409        report("MBB exits via conditional branch/branch but doesn't "
410               "contain any instructions!", MBB);
411      } else if (!MBB->back().getDesc().isBarrier()) {
412        report("MBB exits via conditional branch/branch but doesn't end with a "
413               "barrier instruction!", MBB);
414      } else if (!MBB->back().getDesc().isTerminator()) {
415        report("MBB exits via conditional branch/branch but the branch "
416               "isn't a terminator instruction!", MBB);
417      }
418      if (Cond.empty()) {
419        report("MBB exits via conditinal branch/branch but there's no "
420               "condition!", MBB);
421      }
422    } else {
423      report("AnalyzeBranch returned invalid data!", MBB);
424    }
425  }
426
427  regsLive.clear();
428  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
429         E = MBB->livein_end(); I != E; ++I) {
430    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
431      report("MBB live-in list contains non-physical register", MBB);
432      continue;
433    }
434    regsLive.insert(*I);
435    for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
436      regsLive.insert(*R);
437  }
438  regsLiveInButUnused = regsLive;
439
440  const MachineFrameInfo *MFI = MF->getFrameInfo();
441  assert(MFI && "Function has no frame info");
442  BitVector PR = MFI->getPristineRegs(MBB);
443  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
444    regsLive.insert(I);
445    for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
446      regsLive.insert(*R);
447  }
448
449  regsKilled.clear();
450  regsDefined.clear();
451}
452
453void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
454  const TargetInstrDesc &TI = MI->getDesc();
455  if (MI->getNumOperands() < TI.getNumOperands()) {
456    report("Too few operands", MI);
457    *OS << TI.getNumOperands() << " operands expected, but "
458        << MI->getNumExplicitOperands() << " given.\n";
459  }
460}
461
462void
463MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
464  const MachineInstr *MI = MO->getParent();
465  const TargetInstrDesc &TI = MI->getDesc();
466
467  // The first TI.NumDefs operands must be explicit register defines
468  if (MONum < TI.getNumDefs()) {
469    if (!MO->isReg())
470      report("Explicit definition must be a register", MO, MONum);
471    else if (!MO->isDef())
472      report("Explicit definition marked as use", MO, MONum);
473    else if (MO->isImplicit())
474      report("Explicit definition marked as implicit", MO, MONum);
475  } else if (MONum < TI.getNumOperands()) {
476    if (MO->isReg()) {
477      if (MO->isDef())
478        report("Explicit operand marked as def", MO, MONum);
479      if (MO->isImplicit())
480        report("Explicit operand marked as implicit", MO, MONum);
481    }
482  } else {
483    if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic())
484      report("Extra explicit operand on non-variadic instruction", MO, MONum);
485  }
486
487  switch (MO->getType()) {
488  case MachineOperand::MO_Register: {
489    const unsigned Reg = MO->getReg();
490    if (!Reg)
491      return;
492
493    // Check Live Variables.
494    if (MO->isUndef()) {
495      // An <undef> doesn't refer to any register, so just skip it.
496    } else if (MO->isUse()) {
497      regsLiveInButUnused.erase(Reg);
498
499      if (MO->isKill()) {
500        addRegWithSubRegs(regsKilled, Reg);
501        // Tied operands on two-address instuctions MUST NOT have a <kill> flag.
502        if (MI->isRegTiedToDefOperand(MONum))
503            report("Illegal kill flag on two-address instruction operand",
504                   MO, MONum);
505      } else {
506        // TwoAddress instr modifying a reg is treated as kill+def.
507        unsigned defIdx;
508        if (MI->isRegTiedToDefOperand(MONum, &defIdx) &&
509            MI->getOperand(defIdx).getReg() == Reg)
510          addRegWithSubRegs(regsKilled, Reg);
511      }
512      // Use of a dead register.
513      if (!regsLive.count(Reg)) {
514        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
515          // Reserved registers may be used even when 'dead'.
516          if (!isReserved(Reg))
517            report("Using an undefined physical register", MO, MONum);
518        } else {
519          BBInfo &MInfo = MBBInfoMap[MI->getParent()];
520          // We don't know which virtual registers are live in, so only complain
521          // if vreg was killed in this MBB. Otherwise keep track of vregs that
522          // must be live in. PHI instructions are handled separately.
523          if (MInfo.regsKilled.count(Reg))
524            report("Using a killed virtual register", MO, MONum);
525          else if (MI->getOpcode() != TargetInstrInfo::PHI)
526            MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
527        }
528      }
529    } else {
530      assert(MO->isDef());
531      // Register defined.
532      // TODO: verify that earlyclobber ops are not used.
533      if (MO->isDead())
534        addRegWithSubRegs(regsDead, Reg);
535      else
536        addRegWithSubRegs(regsDefined, Reg);
537    }
538
539    // Check register classes.
540    if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
541      const TargetOperandInfo &TOI = TI.OpInfo[MONum];
542      unsigned SubIdx = MO->getSubReg();
543
544      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
545        unsigned sr = Reg;
546        if (SubIdx) {
547          unsigned s = TRI->getSubReg(Reg, SubIdx);
548          if (!s) {
549            report("Invalid subregister index for physical register",
550                   MO, MONum);
551            return;
552          }
553          sr = s;
554        }
555        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
556          if (!DRC->contains(sr)) {
557            report("Illegal physical register for instruction", MO, MONum);
558            *OS << TRI->getName(sr) << " is not a "
559                << DRC->getName() << " register.\n";
560          }
561        }
562      } else {
563        // Virtual register.
564        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
565        if (SubIdx) {
566          if (RC->subregclasses_begin()+SubIdx >= RC->subregclasses_end()) {
567            report("Invalid subregister index for virtual register", MO, MONum);
568            return;
569          }
570          RC = *(RC->subregclasses_begin()+SubIdx);
571        }
572        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
573          if (RC != DRC && !RC->hasSuperClass(DRC)) {
574            report("Illegal virtual register for instruction", MO, MONum);
575            *OS << "Expected a " << DRC->getName() << " register, but got a "
576                << RC->getName() << " register\n";
577          }
578        }
579      }
580    }
581    break;
582  }
583
584  case MachineOperand::MO_MachineBasicBlock:
585    if (MI->getOpcode() == TargetInstrInfo::PHI) {
586      if (!MO->getMBB()->isSuccessor(MI->getParent()))
587        report("PHI operand is not in the CFG", MO, MONum);
588    }
589    break;
590
591  default:
592    break;
593  }
594}
595
596void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
597  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
598  set_union(MInfo.regsKilled, regsKilled);
599  set_subtract(regsLive, regsKilled);
600  regsKilled.clear();
601
602  // Verify that both <def> and <def,dead> operands refer to dead registers.
603  RegVector defs(regsDefined);
604  defs.append(regsDead.begin(), regsDead.end());
605
606  for (RegVector::const_iterator I = defs.begin(), E = defs.end();
607       I != E; ++I) {
608    if (regsLive.count(*I)) {
609      if (TargetRegisterInfo::isPhysicalRegister(*I)) {
610        if (!allowPhysDoubleDefs && !isReserved(*I) &&
611            !regsLiveInButUnused.count(*I)) {
612          report("Redefining a live physical register", MI);
613          *OS << "Register " << TRI->getName(*I)
614              << " was defined but already live.\n";
615        }
616      } else {
617        if (!allowVirtDoubleDefs) {
618          report("Redefining a live virtual register", MI);
619          *OS << "Virtual register %reg" << *I
620              << " was defined but already live.\n";
621        }
622      }
623    } else if (TargetRegisterInfo::isVirtualRegister(*I) &&
624               !MInfo.regsKilled.count(*I)) {
625      // Virtual register defined without being killed first must be dead on
626      // entry.
627      MInfo.vregsDeadIn.insert(std::make_pair(*I, MI));
628    }
629  }
630
631  set_subtract(regsLive, regsDead); regsDead.clear();
632  set_union(regsLive, regsDefined); regsDefined.clear();
633}
634
635void
636MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
637  MBBInfoMap[MBB].regsLiveOut = regsLive;
638  regsLive.clear();
639}
640
641// Calculate the largest possible vregsPassed sets. These are the registers that
642// can pass through an MBB live, but may not be live every time. It is assumed
643// that all vregsPassed sets are empty before the call.
644void MachineVerifier::calcMaxRegsPassed() {
645  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
646  // have any vregsPassed.
647  DenseSet<const MachineBasicBlock*> todo;
648  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
649       MFI != MFE; ++MFI) {
650    const MachineBasicBlock &MBB(*MFI);
651    BBInfo &MInfo = MBBInfoMap[&MBB];
652    if (!MInfo.reachable)
653      continue;
654    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
655           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
656      BBInfo &SInfo = MBBInfoMap[*SuI];
657      if (SInfo.addPassed(MInfo.regsLiveOut))
658        todo.insert(*SuI);
659    }
660  }
661
662  // Iteratively push vregsPassed to successors. This will converge to the same
663  // final state regardless of DenseSet iteration order.
664  while (!todo.empty()) {
665    const MachineBasicBlock *MBB = *todo.begin();
666    todo.erase(MBB);
667    BBInfo &MInfo = MBBInfoMap[MBB];
668    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
669           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
670      if (*SuI == MBB)
671        continue;
672      BBInfo &SInfo = MBBInfoMap[*SuI];
673      if (SInfo.addPassed(MInfo.vregsPassed))
674        todo.insert(*SuI);
675    }
676  }
677}
678
679// Calculate the minimum vregsPassed set. These are the registers that always
680// pass live through an MBB. The calculation assumes that calcMaxRegsPassed has
681// been called earlier.
682void MachineVerifier::calcMinRegsPassed() {
683  DenseSet<const MachineBasicBlock*> todo;
684  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
685       MFI != MFE; ++MFI)
686    todo.insert(MFI);
687
688  while (!todo.empty()) {
689    const MachineBasicBlock *MBB = *todo.begin();
690    todo.erase(MBB);
691    BBInfo &MInfo = MBBInfoMap[MBB];
692
693    // Remove entries from vRegsPassed that are not live out from all
694    // reachable predecessors.
695    RegSet dead;
696    for (RegSet::iterator I = MInfo.vregsPassed.begin(),
697           E = MInfo.vregsPassed.end(); I != E; ++I) {
698      for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
699             PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
700        BBInfo &PrInfo = MBBInfoMap[*PrI];
701        if (PrInfo.reachable && !PrInfo.isLiveOut(*I)) {
702          dead.insert(*I);
703          break;
704        }
705      }
706    }
707    // If any regs removed, we need to recheck successors.
708    if (!dead.empty()) {
709      set_subtract(MInfo.vregsPassed, dead);
710      todo.insert(MBB->succ_begin(), MBB->succ_end());
711    }
712  }
713}
714
715// Check PHI instructions at the beginning of MBB. It is assumed that
716// calcMinRegsPassed has been run so BBInfo::isLiveOut is valid.
717void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
718  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
719       BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
720    DenseSet<const MachineBasicBlock*> seen;
721
722    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
723      unsigned Reg = BBI->getOperand(i).getReg();
724      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
725      if (!Pre->isSuccessor(MBB))
726        continue;
727      seen.insert(Pre);
728      BBInfo &PrInfo = MBBInfoMap[Pre];
729      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
730        report("PHI operand is not live-out from predecessor",
731               &BBI->getOperand(i), i);
732    }
733
734    // Did we see all predecessors?
735    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
736           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
737      if (!seen.count(*PrI)) {
738        report("Missing PHI operand", BBI);
739        *OS << "MBB #" << (*PrI)->getNumber()
740            << " is a predecessor according to the CFG.\n";
741      }
742    }
743  }
744}
745
746void MachineVerifier::visitMachineFunctionAfter() {
747  calcMaxRegsPassed();
748
749  // With the maximal set of vregsPassed we can verify dead-in registers.
750  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
751       MFI != MFE; ++MFI) {
752    BBInfo &MInfo = MBBInfoMap[MFI];
753
754    // Skip unreachable MBBs.
755    if (!MInfo.reachable)
756      continue;
757
758    for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
759           PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
760      BBInfo &PrInfo = MBBInfoMap[*PrI];
761      if (!PrInfo.reachable)
762        continue;
763
764      // Verify physical live-ins. EH landing pads have magic live-ins so we
765      // ignore them.
766      if (!MFI->isLandingPad()) {
767        for (MachineBasicBlock::const_livein_iterator I = MFI->livein_begin(),
768               E = MFI->livein_end(); I != E; ++I) {
769          if (TargetRegisterInfo::isPhysicalRegister(*I) &&
770              !isReserved (*I) && !PrInfo.isLiveOut(*I)) {
771            report("Live-in physical register is not live-out from predecessor",
772                   MFI);
773            *OS << "Register " << TRI->getName(*I)
774                << " is not live-out from MBB #" << (*PrI)->getNumber()
775                << ".\n";
776          }
777        }
778      }
779
780
781      // Verify dead-in virtual registers.
782      if (!allowVirtDoubleDefs) {
783        for (RegMap::iterator I = MInfo.vregsDeadIn.begin(),
784               E = MInfo.vregsDeadIn.end(); I != E; ++I) {
785          // DeadIn register must be in neither regsLiveOut or vregsPassed of
786          // any predecessor.
787          if (PrInfo.isLiveOut(I->first)) {
788            report("Live-in virtual register redefined", I->second);
789            *OS << "Register %reg" << I->first
790                << " was live-out from predecessor MBB #"
791                << (*PrI)->getNumber() << ".\n";
792          }
793        }
794      }
795    }
796  }
797
798  calcMinRegsPassed();
799
800  // With the minimal set of vregsPassed we can verify live-in virtual
801  // registers, including PHI instructions.
802  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
803       MFI != MFE; ++MFI) {
804    BBInfo &MInfo = MBBInfoMap[MFI];
805
806    // Skip unreachable MBBs.
807    if (!MInfo.reachable)
808      continue;
809
810    checkPHIOps(MFI);
811
812    for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
813           PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
814      BBInfo &PrInfo = MBBInfoMap[*PrI];
815      if (!PrInfo.reachable)
816        continue;
817
818      for (RegMap::iterator I = MInfo.vregsLiveIn.begin(),
819             E = MInfo.vregsLiveIn.end(); I != E; ++I) {
820        if (!PrInfo.isLiveOut(I->first)) {
821          report("Used virtual register is not live-in", I->second);
822          *OS << "Register %reg" << I->first
823              << " is not live-out from predecessor MBB #"
824              << (*PrI)->getNumber()
825              << ".\n";
826        }
827      }
828    }
829  }
830}
831