1 //===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Pass to verify generated machine code. The following is checked:
12 // Operand counts: All explicit operands must be present.
14 // Register classes: All physical and virtual register operands must be
15 // compatible with the register class required by the instruction descriptor.
17 // Register live intervals: Registers must be defined only once, and must be
18 // defined before use.
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 //===----------------------------------------------------------------------===//
26 #include "llvm/Instructions.h"
27 #include "llvm/Function.h"
28 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
29 #include "llvm/CodeGen/LiveVariables.h"
30 #include "llvm/CodeGen/LiveStackAnalysis.h"
31 #include "llvm/CodeGen/MachineFunctionPass.h"
32 #include "llvm/CodeGen/MachineFrameInfo.h"
33 #include "llvm/CodeGen/MachineMemOperand.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/MC/MCAsmInfo.h"
37 #include "llvm/Target/TargetMachine.h"
38 #include "llvm/Target/TargetRegisterInfo.h"
39 #include "llvm/Target/TargetInstrInfo.h"
40 #include "llvm/ADT/DenseSet.h"
41 #include "llvm/ADT/SetOperations.h"
42 #include "llvm/ADT/SmallVector.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Support/ErrorHandling.h"
45 #include "llvm/Support/raw_ostream.h"
49 struct MachineVerifier {
51 MachineVerifier(Pass *pass, const char *b) :
54 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
57 bool runOnMachineFunction(MachineFunction &MF);
61 const char *const OutFileName;
63 const MachineFunction *MF;
64 const TargetMachine *TM;
65 const TargetInstrInfo *TII;
66 const TargetRegisterInfo *TRI;
67 const MachineRegisterInfo *MRI;
71 typedef SmallVector<unsigned, 16> RegVector;
72 typedef SmallVector<const uint32_t*, 4> RegMaskVector;
73 typedef DenseSet<unsigned> RegSet;
74 typedef DenseMap<unsigned, const MachineInstr*> RegMap;
76 const MachineInstr *FirstTerminator;
78 BitVector regsReserved;
79 BitVector regsAllocatable;
81 RegVector regsDefined, regsDead, regsKilled;
82 RegMaskVector regMasks;
83 RegSet regsLiveInButUnused;
87 // Add Reg and any sub-registers to RV
88 void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
90 if (TargetRegisterInfo::isPhysicalRegister(Reg))
91 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
96 // Is this MBB reachable from the MF entry point?
99 // Vregs that must be live in because they are used without being
100 // defined. Map value is the user.
103 // Regs killed in MBB. They may be defined again, and will then be in both
104 // regsKilled and regsLiveOut.
107 // Regs defined in MBB and live out. Note that vregs passing through may
108 // be live out without being mentioned here.
111 // Vregs that pass through MBB untouched. This set is disjoint from
112 // regsKilled and regsLiveOut.
115 // Vregs that must pass through MBB because they are needed by a successor
116 // block. This set is disjoint from regsLiveOut.
117 RegSet vregsRequired;
119 BBInfo() : reachable(false) {}
121 // Add register to vregsPassed if it belongs there. Return true if
123 bool addPassed(unsigned Reg) {
124 if (!TargetRegisterInfo::isVirtualRegister(Reg))
126 if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
128 return vregsPassed.insert(Reg).second;
131 // Same for a full set.
132 bool addPassed(const RegSet &RS) {
133 bool changed = false;
134 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
140 // Add register to vregsRequired if it belongs there. Return true if
142 bool addRequired(unsigned Reg) {
143 if (!TargetRegisterInfo::isVirtualRegister(Reg))
145 if (regsLiveOut.count(Reg))
147 return vregsRequired.insert(Reg).second;
150 // Same for a full set.
151 bool addRequired(const RegSet &RS) {
152 bool changed = false;
153 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
159 // Same for a full map.
160 bool addRequired(const RegMap &RM) {
161 bool changed = false;
162 for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
163 if (addRequired(I->first))
168 // Live-out registers are either in regsLiveOut or vregsPassed.
169 bool isLiveOut(unsigned Reg) const {
170 return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
174 // Extra register info per MBB.
175 DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
177 bool isReserved(unsigned Reg) {
178 return Reg < regsReserved.size() && regsReserved.test(Reg);
181 bool isAllocatable(unsigned Reg) {
182 return Reg < regsAllocatable.size() && regsAllocatable.test(Reg);
185 // Analysis information if available
186 LiveVariables *LiveVars;
187 LiveIntervals *LiveInts;
188 LiveStacks *LiveStks;
189 SlotIndexes *Indexes;
191 void visitMachineFunctionBefore();
192 void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
193 void visitMachineInstrBefore(const MachineInstr *MI);
194 void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
195 void visitMachineInstrAfter(const MachineInstr *MI);
196 void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
197 void visitMachineFunctionAfter();
199 void report(const char *msg, const MachineFunction *MF);
200 void report(const char *msg, const MachineBasicBlock *MBB);
201 void report(const char *msg, const MachineInstr *MI);
202 void report(const char *msg, const MachineOperand *MO, unsigned MONum);
204 void markReachable(const MachineBasicBlock *MBB);
205 void calcRegsPassed();
206 void checkPHIOps(const MachineBasicBlock *MBB);
208 void calcRegsRequired();
209 void verifyLiveVariables();
210 void verifyLiveIntervals();
213 struct MachineVerifierPass : public MachineFunctionPass {
214 static char ID; // Pass ID, replacement for typeid
215 const char *const Banner;
217 MachineVerifierPass(const char *b = 0)
218 : MachineFunctionPass(ID), Banner(b) {
219 initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
222 void getAnalysisUsage(AnalysisUsage &AU) const {
223 AU.setPreservesAll();
224 MachineFunctionPass::getAnalysisUsage(AU);
227 bool runOnMachineFunction(MachineFunction &MF) {
228 MF.verify(this, Banner);
235 char MachineVerifierPass::ID = 0;
236 INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
237 "Verify generated machine code", false, false)
239 FunctionPass *llvm::createMachineVerifierPass(const char *Banner) {
240 return new MachineVerifierPass(Banner);
243 void MachineFunction::verify(Pass *p, const char *Banner) const {
244 MachineVerifier(p, Banner)
245 .runOnMachineFunction(const_cast<MachineFunction&>(*this));
248 bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
249 raw_ostream *OutFile = 0;
251 std::string ErrorInfo;
252 OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
253 raw_fd_ostream::F_Append);
254 if (!ErrorInfo.empty()) {
255 errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
267 TM = &MF.getTarget();
268 TII = TM->getInstrInfo();
269 TRI = TM->getRegisterInfo();
270 MRI = &MF.getRegInfo();
277 LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
278 // We don't want to verify LiveVariables if LiveIntervals is available.
280 LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
281 LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
282 Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
285 visitMachineFunctionBefore();
286 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
288 visitMachineBasicBlockBefore(MFI);
289 for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
290 MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
291 if (MBBI->getParent() != MFI) {
292 report("Bad instruction parent pointer", MFI);
293 *OS << "Instruction: " << *MBBI;
296 // Skip BUNDLE instruction for now. FIXME: We should add code to verify
297 // the BUNDLE's specifically.
298 if (MBBI->isBundle())
300 visitMachineInstrBefore(MBBI);
301 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
302 visitMachineOperand(&MBBI->getOperand(I), I);
303 visitMachineInstrAfter(MBBI);
305 visitMachineBasicBlockAfter(MFI);
307 visitMachineFunctionAfter();
311 else if (foundErrors)
312 report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
320 regsLiveInButUnused.clear();
323 return false; // no changes
326 void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
329 if (!foundErrors++) {
331 *OS << "# " << Banner << '\n';
332 MF->print(*OS, Indexes);
334 *OS << "*** Bad machine code: " << msg << " ***\n"
335 << "- function: " << MF->getFunction()->getName() << "\n";
338 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
340 report(msg, MBB->getParent());
341 *OS << "- basic block: " << MBB->getName()
343 << " (BB#" << MBB->getNumber() << ")";
345 *OS << " [" << Indexes->getMBBStartIdx(MBB)
346 << ';' << Indexes->getMBBEndIdx(MBB) << ')';
350 void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
352 report(msg, MI->getParent());
353 *OS << "- instruction: ";
354 if (Indexes && Indexes->hasIndex(MI))
355 *OS << Indexes->getInstructionIndex(MI) << '\t';
359 void MachineVerifier::report(const char *msg,
360 const MachineOperand *MO, unsigned MONum) {
362 report(msg, MO->getParent());
363 *OS << "- operand " << MONum << ": ";
368 void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
369 BBInfo &MInfo = MBBInfoMap[MBB];
370 if (!MInfo.reachable) {
371 MInfo.reachable = true;
372 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
373 SuE = MBB->succ_end(); SuI != SuE; ++SuI)
378 void MachineVerifier::visitMachineFunctionBefore() {
379 lastIndex = SlotIndex();
380 regsReserved = TRI->getReservedRegs(*MF);
382 // A sub-register of a reserved register is also reserved
383 for (int Reg = regsReserved.find_first(); Reg>=0;
384 Reg = regsReserved.find_next(Reg)) {
385 for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
386 // FIXME: This should probably be:
387 // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
388 regsReserved.set(*Sub);
392 regsAllocatable = TRI->getAllocatableSet(*MF);
394 markReachable(&MF->front());
397 // Does iterator point to a and b as the first two elements?
398 static bool matchPair(MachineBasicBlock::const_succ_iterator i,
399 const MachineBasicBlock *a, const MachineBasicBlock *b) {
408 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
412 // If this block has allocatable physical registers live-in, check that
413 // it is an entry block or landing pad.
414 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
415 LE = MBB->livein_end();
418 if (isAllocatable(reg) && !MBB->isLandingPad() &&
419 MBB != MBB->getParent()->begin()) {
420 report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB);
425 // Count the number of landing pad successors.
426 SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
427 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
428 E = MBB->succ_end(); I != E; ++I) {
429 if ((*I)->isLandingPad())
430 LandingPadSuccs.insert(*I);
433 const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
434 const BasicBlock *BB = MBB->getBasicBlock();
435 if (LandingPadSuccs.size() > 1 &&
437 AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
438 BB && isa<SwitchInst>(BB->getTerminator())))
439 report("MBB has more than one landing pad successor", MBB);
441 // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
442 MachineBasicBlock *TBB = 0, *FBB = 0;
443 SmallVector<MachineOperand, 4> Cond;
444 if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
446 // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
447 // check whether its answers match up with reality.
449 // Block falls through to its successor.
450 MachineFunction::const_iterator MBBI = MBB;
452 if (MBBI == MF->end()) {
453 // It's possible that the block legitimately ends with a noreturn
454 // call or an unreachable, in which case it won't actually fall
455 // out the bottom of the function.
456 } else if (MBB->succ_size() == LandingPadSuccs.size()) {
457 // It's possible that the block legitimately ends with a noreturn
458 // call or an unreachable, in which case it won't actuall fall
460 } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
461 report("MBB exits via unconditional fall-through but doesn't have "
462 "exactly one CFG successor!", MBB);
463 } else if (!MBB->isSuccessor(MBBI)) {
464 report("MBB exits via unconditional fall-through but its successor "
465 "differs from its CFG successor!", MBB);
467 if (!MBB->empty() && MBB->back().isBarrier() &&
468 !TII->isPredicated(&MBB->back())) {
469 report("MBB exits via unconditional fall-through but ends with a "
470 "barrier instruction!", MBB);
473 report("MBB exits via unconditional fall-through but has a condition!",
476 } else if (TBB && !FBB && Cond.empty()) {
477 // Block unconditionally branches somewhere.
478 if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
479 report("MBB exits via unconditional branch but doesn't have "
480 "exactly one CFG successor!", MBB);
481 } else if (!MBB->isSuccessor(TBB)) {
482 report("MBB exits via unconditional branch but the CFG "
483 "successor doesn't match the actual successor!", MBB);
486 report("MBB exits via unconditional branch but doesn't contain "
487 "any instructions!", MBB);
488 } else if (!MBB->back().isBarrier()) {
489 report("MBB exits via unconditional branch but doesn't end with a "
490 "barrier instruction!", MBB);
491 } else if (!MBB->back().isTerminator()) {
492 report("MBB exits via unconditional branch but the branch isn't a "
493 "terminator instruction!", MBB);
495 } else if (TBB && !FBB && !Cond.empty()) {
496 // Block conditionally branches somewhere, otherwise falls through.
497 MachineFunction::const_iterator MBBI = MBB;
499 if (MBBI == MF->end()) {
500 report("MBB conditionally falls through out of function!", MBB);
501 } if (MBB->succ_size() != 2) {
502 report("MBB exits via conditional branch/fall-through but doesn't have "
503 "exactly two CFG successors!", MBB);
504 } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
505 report("MBB exits via conditional branch/fall-through but the CFG "
506 "successors don't match the actual successors!", MBB);
509 report("MBB exits via conditional branch/fall-through but doesn't "
510 "contain any instructions!", MBB);
511 } else if (MBB->back().isBarrier()) {
512 report("MBB exits via conditional branch/fall-through but ends with a "
513 "barrier instruction!", MBB);
514 } else if (!MBB->back().isTerminator()) {
515 report("MBB exits via conditional branch/fall-through but the branch "
516 "isn't a terminator instruction!", MBB);
518 } else if (TBB && FBB) {
519 // Block conditionally branches somewhere, otherwise branches
521 if (MBB->succ_size() != 2) {
522 report("MBB exits via conditional branch/branch but doesn't have "
523 "exactly two CFG successors!", MBB);
524 } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
525 report("MBB exits via conditional branch/branch but the CFG "
526 "successors don't match the actual successors!", MBB);
529 report("MBB exits via conditional branch/branch but doesn't "
530 "contain any instructions!", MBB);
531 } else if (!MBB->back().isBarrier()) {
532 report("MBB exits via conditional branch/branch but doesn't end with a "
533 "barrier instruction!", MBB);
534 } else if (!MBB->back().isTerminator()) {
535 report("MBB exits via conditional branch/branch but the branch "
536 "isn't a terminator instruction!", MBB);
539 report("MBB exits via conditinal branch/branch but there's no "
543 report("AnalyzeBranch returned invalid data!", MBB);
548 for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
549 E = MBB->livein_end(); I != E; ++I) {
550 if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
551 report("MBB live-in list contains non-physical register", MBB);
555 for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
558 regsLiveInButUnused = regsLive;
560 const MachineFrameInfo *MFI = MF->getFrameInfo();
561 assert(MFI && "Function has no frame info");
562 BitVector PR = MFI->getPristineRegs(MBB);
563 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
565 for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
573 lastIndex = Indexes->getMBBStartIdx(MBB);
576 void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
577 const MCInstrDesc &MCID = MI->getDesc();
578 if (MI->getNumOperands() < MCID.getNumOperands()) {
579 report("Too few operands", MI);
580 *OS << MCID.getNumOperands() << " operands expected, but "
581 << MI->getNumExplicitOperands() << " given.\n";
584 // Check the MachineMemOperands for basic consistency.
585 for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
586 E = MI->memoperands_end(); I != E; ++I) {
587 if ((*I)->isLoad() && !MI->mayLoad())
588 report("Missing mayLoad flag", MI);
589 if ((*I)->isStore() && !MI->mayStore())
590 report("Missing mayStore flag", MI);
593 // Debug values must not have a slot index.
594 // Other instructions must have one, unless they are inside a bundle.
596 bool mapped = !LiveInts->isNotInMIMap(MI);
597 if (MI->isDebugValue()) {
599 report("Debug instruction has a slot index", MI);
600 } else if (MI->isInsideBundle()) {
602 report("Instruction inside bundle has a slot index", MI);
605 report("Missing slot index", MI);
609 // Ensure non-terminators don't follow terminators.
610 if (MI->isTerminator()) {
611 if (!FirstTerminator)
612 FirstTerminator = MI;
613 } else if (FirstTerminator) {
614 report("Non-terminator instruction after the first terminator", MI);
615 *OS << "First terminator was:\t" << *FirstTerminator;
619 if (!TII->verifyInstruction(MI, ErrorInfo))
620 report(ErrorInfo.data(), MI);
624 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
625 const MachineInstr *MI = MO->getParent();
626 const MCInstrDesc &MCID = MI->getDesc();
627 const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
629 // The first MCID.NumDefs operands must be explicit register defines
630 if (MONum < MCID.getNumDefs()) {
632 report("Explicit definition must be a register", MO, MONum);
633 else if (!MO->isDef())
634 report("Explicit definition marked as use", MO, MONum);
635 else if (MO->isImplicit())
636 report("Explicit definition marked as implicit", MO, MONum);
637 } else if (MONum < MCID.getNumOperands()) {
638 // Don't check if it's the last operand in a variadic instruction. See,
639 // e.g., LDM_RET in the arm back end.
641 !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
642 if (MO->isDef() && !MCOI.isOptionalDef())
643 report("Explicit operand marked as def", MO, MONum);
644 if (MO->isImplicit())
645 report("Explicit operand marked as implicit", MO, MONum);
648 // ARM adds %reg0 operands to indicate predicates. We'll allow that.
649 if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
650 report("Extra explicit operand on non-variadic instruction", MO, MONum);
653 switch (MO->getType()) {
654 case MachineOperand::MO_Register: {
655 const unsigned Reg = MO->getReg();
659 // Check Live Variables.
660 if (MI->isDebugValue()) {
661 // Liveness checks are not valid for debug values.
662 } else if (MO->isUse() && !MO->isUndef()) {
663 regsLiveInButUnused.erase(Reg);
667 if (MI->isRegTiedToDefOperand(MONum, &defIdx)) {
668 // A two-addr use counts as a kill if use and def are the same.
669 unsigned DefReg = MI->getOperand(defIdx).getReg();
672 else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
673 report("Two-address instruction operands must be identical",
677 isKill = MO->isKill();
680 addRegWithSubRegs(regsKilled, Reg);
682 // Check that LiveVars knows this kill.
683 if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
685 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
686 if (std::find(VI.Kills.begin(),
687 VI.Kills.end(), MI) == VI.Kills.end())
688 report("Kill missing from LiveVariables", MO, MONum);
691 // Check LiveInts liveness and kill.
692 if (TargetRegisterInfo::isVirtualRegister(Reg) &&
693 LiveInts && !LiveInts->isNotInMIMap(MI)) {
694 SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getRegSlot(true);
695 if (LiveInts->hasInterval(Reg)) {
696 const LiveInterval &LI = LiveInts->getInterval(Reg);
697 if (!LI.liveAt(UseIdx)) {
698 report("No live range at use", MO, MONum);
699 *OS << UseIdx << " is not live in " << LI << '\n';
701 // Check for extra kill flags.
702 // Note that we allow missing kill flags for now.
703 if (MO->isKill() && !LI.killedAt(UseIdx.getRegSlot())) {
704 report("Live range continues after kill flag", MO, MONum);
705 *OS << "Live range: " << LI << '\n';
708 report("Virtual register has no Live interval", MO, MONum);
712 // Use of a dead register.
713 if (!regsLive.count(Reg)) {
714 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
715 // Reserved registers may be used even when 'dead'.
716 if (!isReserved(Reg))
717 report("Using an undefined physical register", MO, MONum);
719 BBInfo &MInfo = MBBInfoMap[MI->getParent()];
720 // We don't know which virtual registers are live in, so only complain
721 // if vreg was killed in this MBB. Otherwise keep track of vregs that
722 // must be live in. PHI instructions are handled separately.
723 if (MInfo.regsKilled.count(Reg))
724 report("Using a killed virtual register", MO, MONum);
725 else if (!MI->isPHI())
726 MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
729 } else if (MO->isDef()) {
731 // TODO: verify that earlyclobber ops are not used.
733 addRegWithSubRegs(regsDead, Reg);
735 addRegWithSubRegs(regsDefined, Reg);
738 if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
739 llvm::next(MRI->def_begin(Reg)) != MRI->def_end())
740 report("Multiple virtual register defs in SSA form", MO, MONum);
742 // Check LiveInts for a live range, but only for virtual registers.
743 if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
744 !LiveInts->isNotInMIMap(MI)) {
745 SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getRegSlot();
746 if (LiveInts->hasInterval(Reg)) {
747 const LiveInterval &LI = LiveInts->getInterval(Reg);
748 if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
749 assert(VNI && "NULL valno is not allowed");
750 if (VNI->def != DefIdx && !MO->isEarlyClobber()) {
751 report("Inconsistent valno->def", MO, MONum);
752 *OS << "Valno " << VNI->id << " is not defined at "
753 << DefIdx << " in " << LI << '\n';
756 report("No live range at def", MO, MONum);
757 *OS << DefIdx << " is not live in " << LI << '\n';
760 report("Virtual register has no Live interval", MO, MONum);
765 // Check register classes.
766 if (MONum < MCID.getNumOperands() && !MO->isImplicit()) {
767 unsigned SubIdx = MO->getSubReg();
769 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
771 report("Illegal subregister index for physical register", MO, MONum);
774 if (const TargetRegisterClass *DRC = TII->getRegClass(MCID,MONum,TRI)) {
775 if (!DRC->contains(Reg)) {
776 report("Illegal physical register for instruction", MO, MONum);
777 *OS << TRI->getName(Reg) << " is not a "
778 << DRC->getName() << " register.\n";
783 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
785 const TargetRegisterClass *SRC =
786 TRI->getSubClassWithSubReg(RC, SubIdx);
788 report("Invalid subregister index for virtual register", MO, MONum);
789 *OS << "Register class " << RC->getName()
790 << " does not support subreg index " << SubIdx << "\n";
794 report("Invalid register class for subregister index", MO, MONum);
795 *OS << "Register class " << RC->getName()
796 << " does not fully support subreg index " << SubIdx << "\n";
800 if (const TargetRegisterClass *DRC = TII->getRegClass(MCID,MONum,TRI)) {
802 const TargetRegisterClass *SuperRC =
803 TRI->getLargestLegalSuperClass(RC);
805 report("No largest legal super class exists.", MO, MONum);
808 DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
810 report("No matching super-reg register class.", MO, MONum);
814 if (!RC->hasSuperClassEq(DRC)) {
815 report("Illegal virtual register for instruction", MO, MONum);
816 *OS << "Expected a " << DRC->getName() << " register, but got a "
817 << RC->getName() << " register\n";
825 case MachineOperand::MO_RegisterMask:
826 regMasks.push_back(MO->getRegMask());
829 case MachineOperand::MO_MachineBasicBlock:
830 if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
831 report("PHI operand is not in the CFG", MO, MONum);
834 case MachineOperand::MO_FrameIndex:
835 if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
836 LiveInts && !LiveInts->isNotInMIMap(MI)) {
837 LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
838 SlotIndex Idx = LiveInts->getInstructionIndex(MI);
839 if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) {
840 report("Instruction loads from dead spill slot", MO, MONum);
841 *OS << "Live stack: " << LI << '\n';
843 if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) {
844 report("Instruction stores to dead spill slot", MO, MONum);
845 *OS << "Live stack: " << LI << '\n';
855 void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
856 BBInfo &MInfo = MBBInfoMap[MI->getParent()];
857 set_union(MInfo.regsKilled, regsKilled);
858 set_subtract(regsLive, regsKilled); regsKilled.clear();
859 // Kill any masked registers.
860 while (!regMasks.empty()) {
861 const uint32_t *Mask = regMasks.pop_back_val();
862 for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
863 if (TargetRegisterInfo::isPhysicalRegister(*I) &&
864 MachineOperand::clobbersPhysReg(Mask, *I))
865 regsDead.push_back(*I);
867 set_subtract(regsLive, regsDead); regsDead.clear();
868 set_union(regsLive, regsDefined); regsDefined.clear();
870 if (Indexes && Indexes->hasIndex(MI)) {
871 SlotIndex idx = Indexes->getInstructionIndex(MI);
872 if (!(idx > lastIndex)) {
873 report("Instruction index out of order", MI);
874 *OS << "Last instruction was at " << lastIndex << '\n';
881 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
882 MBBInfoMap[MBB].regsLiveOut = regsLive;
886 SlotIndex stop = Indexes->getMBBEndIdx(MBB);
887 if (!(stop > lastIndex)) {
888 report("Block ends before last instruction index", MBB);
889 *OS << "Block ends at " << stop
890 << " last instruction was at " << lastIndex << '\n';
896 // Calculate the largest possible vregsPassed sets. These are the registers that
897 // can pass through an MBB live, but may not be live every time. It is assumed
898 // that all vregsPassed sets are empty before the call.
899 void MachineVerifier::calcRegsPassed() {
900 // First push live-out regs to successors' vregsPassed. Remember the MBBs that
901 // have any vregsPassed.
902 DenseSet<const MachineBasicBlock*> todo;
903 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
905 const MachineBasicBlock &MBB(*MFI);
906 BBInfo &MInfo = MBBInfoMap[&MBB];
907 if (!MInfo.reachable)
909 for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
910 SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
911 BBInfo &SInfo = MBBInfoMap[*SuI];
912 if (SInfo.addPassed(MInfo.regsLiveOut))
917 // Iteratively push vregsPassed to successors. This will converge to the same
918 // final state regardless of DenseSet iteration order.
919 while (!todo.empty()) {
920 const MachineBasicBlock *MBB = *todo.begin();
922 BBInfo &MInfo = MBBInfoMap[MBB];
923 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
924 SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
927 BBInfo &SInfo = MBBInfoMap[*SuI];
928 if (SInfo.addPassed(MInfo.vregsPassed))
934 // Calculate the set of virtual registers that must be passed through each basic
935 // block in order to satisfy the requirements of successor blocks. This is very
936 // similar to calcRegsPassed, only backwards.
937 void MachineVerifier::calcRegsRequired() {
938 // First push live-in regs to predecessors' vregsRequired.
939 DenseSet<const MachineBasicBlock*> todo;
940 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
942 const MachineBasicBlock &MBB(*MFI);
943 BBInfo &MInfo = MBBInfoMap[&MBB];
944 for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
945 PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
946 BBInfo &PInfo = MBBInfoMap[*PrI];
947 if (PInfo.addRequired(MInfo.vregsLiveIn))
952 // Iteratively push vregsRequired to predecessors. This will converge to the
953 // same final state regardless of DenseSet iteration order.
954 while (!todo.empty()) {
955 const MachineBasicBlock *MBB = *todo.begin();
957 BBInfo &MInfo = MBBInfoMap[MBB];
958 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
959 PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
962 BBInfo &SInfo = MBBInfoMap[*PrI];
963 if (SInfo.addRequired(MInfo.vregsRequired))
969 // Check PHI instructions at the beginning of MBB. It is assumed that
970 // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
971 void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
972 for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
973 BBI != BBE && BBI->isPHI(); ++BBI) {
974 DenseSet<const MachineBasicBlock*> seen;
976 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
977 unsigned Reg = BBI->getOperand(i).getReg();
978 const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
979 if (!Pre->isSuccessor(MBB))
982 BBInfo &PrInfo = MBBInfoMap[Pre];
983 if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
984 report("PHI operand is not live-out from predecessor",
985 &BBI->getOperand(i), i);
988 // Did we see all predecessors?
989 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
990 PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
991 if (!seen.count(*PrI)) {
992 report("Missing PHI operand", BBI);
993 *OS << "BB#" << (*PrI)->getNumber()
994 << " is a predecessor according to the CFG.\n";
1000 void MachineVerifier::visitMachineFunctionAfter() {
1003 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1004 MFI != MFE; ++MFI) {
1005 BBInfo &MInfo = MBBInfoMap[MFI];
1007 // Skip unreachable MBBs.
1008 if (!MInfo.reachable)
1014 // Now check liveness info if available
1015 if (LiveVars || LiveInts)
1018 verifyLiveVariables();
1020 verifyLiveIntervals();
1023 void MachineVerifier::verifyLiveVariables() {
1024 assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
1025 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1026 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1027 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1028 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1029 MFI != MFE; ++MFI) {
1030 BBInfo &MInfo = MBBInfoMap[MFI];
1032 // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1033 if (MInfo.vregsRequired.count(Reg)) {
1034 if (!VI.AliveBlocks.test(MFI->getNumber())) {
1035 report("LiveVariables: Block missing from AliveBlocks", MFI);
1036 *OS << "Virtual register " << PrintReg(Reg)
1037 << " must be live through the block.\n";
1040 if (VI.AliveBlocks.test(MFI->getNumber())) {
1041 report("LiveVariables: Block should not be in AliveBlocks", MFI);
1042 *OS << "Virtual register " << PrintReg(Reg)
1043 << " is not needed live through the block.\n";
1050 void MachineVerifier::verifyLiveIntervals() {
1051 assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
1052 for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
1053 LVE = LiveInts->end(); LVI != LVE; ++LVI) {
1054 const LiveInterval &LI = *LVI->second;
1056 // Spilling and splitting may leave unused registers around. Skip them.
1057 if (MRI->use_empty(LI.reg))
1060 // Physical registers have much weirdness going on, mostly from coalescing.
1061 // We should probably fix it, but for now just ignore them.
1062 if (TargetRegisterInfo::isPhysicalRegister(LI.reg))
1065 assert(LVI->first == LI.reg && "Invalid reg to interval mapping");
1067 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
1070 const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
1073 if (!VNI->isUnused()) {
1074 report("Valno not live at def and not marked unused", MF);
1075 *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1080 if (VNI->isUnused())
1083 if (DefVNI != VNI) {
1084 report("Live range at def has different valno", MF);
1085 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1086 << " where valno #" << DefVNI->id << " is live in " << LI << '\n';
1090 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1092 report("Invalid definition index", MF);
1093 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1094 << " in " << LI << '\n';
1098 if (VNI->isPHIDef()) {
1099 if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1100 report("PHIDef value is not defined at MBB start", MF);
1101 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1102 << ", not at the beginning of BB#" << MBB->getNumber()
1103 << " in " << LI << '\n';
1107 MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1109 report("No instruction at def index", MF);
1110 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1111 << " in " << LI << '\n';
1115 bool hasDef = false;
1116 bool isEarlyClobber = false;
1117 for (MIOperands MOI(MI, true); MOI.isValid(); ++MOI) {
1118 if (!MOI->isReg() || !MOI->isDef())
1120 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1121 if (MOI->getReg() != LI.reg)
1124 if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1125 !TRI->regsOverlap(LI.reg, MOI->getReg()))
1129 if (MOI->isEarlyClobber())
1130 isEarlyClobber = true;
1134 report("Defining instruction does not modify register", MI);
1135 *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1138 // Early clobber defs begin at USE slots, but other defs must begin at
1140 if (isEarlyClobber) {
1141 if (!VNI->def.isEarlyClobber()) {
1142 report("Early clobber def must be at an early-clobber slot", MF);
1143 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1144 << " in " << LI << '\n';
1146 } else if (!VNI->def.isRegister()) {
1147 report("Non-PHI, non-early clobber def must be at a register slot",
1149 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1150 << " in " << LI << '\n';
1155 for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
1156 const VNInfo *VNI = I->valno;
1157 assert(VNI && "Live range has no valno");
1159 if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
1160 report("Foreign valno in live range", MF);
1162 *OS << " has a valno not in " << LI << '\n';
1165 if (VNI->isUnused()) {
1166 report("Live range valno is marked unused", MF);
1168 *OS << " in " << LI << '\n';
1171 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
1173 report("Bad start of live segment, no basic block", MF);
1175 *OS << " in " << LI << '\n';
1178 SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1179 if (I->start != MBBStartIdx && I->start != VNI->def) {
1180 report("Live segment must begin at MBB entry or valno def", MBB);
1182 *OS << " in " << LI << '\n' << "Basic block starts at "
1183 << MBBStartIdx << '\n';
1186 const MachineBasicBlock *EndMBB =
1187 LiveInts->getMBBFromIndex(I->end.getPrevSlot());
1189 report("Bad end of live segment, no basic block", MF);
1191 *OS << " in " << LI << '\n';
1195 // No more checks for live-out segments.
1196 if (I->end == LiveInts->getMBBEndIdx(EndMBB))
1199 // The live segment is ending inside EndMBB
1201 LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
1203 report("Live segment doesn't end at a valid instruction", EndMBB);
1205 *OS << " in " << LI << '\n' << "Basic block starts at "
1206 << MBBStartIdx << '\n';
1210 // The block slot must refer to a basic block boundary.
1211 if (I->end.isBlock()) {
1212 report("Live segment ends at B slot of an instruction", MI);
1214 *OS << " in " << LI << '\n';
1217 if (I->end.isDead()) {
1218 // Segment ends on the dead slot.
1219 // That means there must be a dead def.
1220 if (!SlotIndex::isSameInstr(I->start, I->end)) {
1221 report("Live segment ending at dead slot spans instructions", MI);
1223 *OS << " in " << LI << '\n';
1227 // A live segment can only end at an early-clobber slot if it is being
1228 // redefined by an early-clobber def.
1229 if (I->end.isEarlyClobber()) {
1230 if (I+1 == E || (I+1)->start != I->end) {
1231 report("Live segment ending at early clobber slot must be "
1232 "redefined by an EC def in the same instruction", MI);
1234 *OS << " in " << LI << '\n';
1238 // The following checks only apply to virtual registers. Physreg liveness
1239 // is too weird to check.
1240 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1241 // A live range can end with either a redefinition, a kill flag on a
1242 // use, or a dead flag on a def.
1243 bool hasRead = false;
1244 bool hasDeadDef = false;
1245 for (MIOperands MOI(MI, true); MOI.isValid(); ++MOI) {
1246 if (!MOI->isReg() || MOI->getReg() != LI.reg)
1248 if (MOI->readsReg())
1250 if (MOI->isDef() && MOI->isDead())
1254 if (I->end.isDead()) {
1256 report("Instruction doesn't have a dead def operand", MI);
1258 *OS << " in " << LI << '\n';
1262 report("Instruction ending live range doesn't read the register",
1265 *OS << " in " << LI << '\n';
1270 // Now check all the basic blocks in this live segment.
1271 MachineFunction::const_iterator MFI = MBB;
1272 // Is this live range the beginning of a non-PHIDef VN?
1273 if (I->start == VNI->def && !VNI->isPHIDef()) {
1274 // Not live-in to any blocks.
1281 assert(LiveInts->isLiveInToMBB(LI, MFI));
1282 // We don't know how to track physregs into a landing pad.
1283 if (TargetRegisterInfo::isPhysicalRegister(LI.reg) &&
1284 MFI->isLandingPad()) {
1285 if (&*MFI == EndMBB)
1290 // Check that VNI is live-out of all predecessors.
1291 for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1292 PE = MFI->pred_end(); PI != PE; ++PI) {
1293 SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
1294 const VNInfo *PVNI = LI.getVNInfoBefore(PEnd);
1296 if (VNI->isPHIDef() && VNI->def == LiveInts->getMBBStartIdx(MFI))
1300 report("Register not marked live out of predecessor", *PI);
1301 *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1302 << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
1303 << PEnd << " in " << LI << '\n';
1308 report("Different value live out of predecessor", *PI);
1309 *OS << "Valno #" << PVNI->id << " live out of BB#"
1310 << (*PI)->getNumber() << '@' << PEnd
1311 << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1312 << '@' << LiveInts->getMBBStartIdx(MFI) << " in " << LI << '\n';
1315 if (&*MFI == EndMBB)
1321 // Check the LI only has one connected component.
1322 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1323 ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1324 unsigned NumComp = ConEQ.Classify(&LI);
1326 report("Multiple connected components in live interval", MF);
1327 *OS << NumComp << " components in " << LI << '\n';
1328 for (unsigned comp = 0; comp != NumComp; ++comp) {
1329 *OS << comp << ": valnos";
1330 for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1331 E = LI.vni_end(); I!=E; ++I)
1332 if (comp == ConEQ.getEqClass(*I))
1333 *OS << ' ' << (*I)->id;