X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineVerifier.cpp;h=830a87632726a72974437c789c79c45431783cfc;hb=5a89434236a4d6ad5fa6a570cbf3e717b757a148;hp=20dd246e5ab7792ae43485fd731014f8c803be73;hpb=1fe9c34d3f55399dee2c41617d8af4f09e5509e7;p=oota-llvm.git diff --git a/lib/CodeGen/MachineVerifier.cpp b/lib/CodeGen/MachineVerifier.cpp index 20dd246e5ab..830a8763272 100644 --- a/lib/CodeGen/MachineVerifier.cpp +++ b/lib/CodeGen/MachineVerifier.cpp @@ -1,4 +1,4 @@ -//===-- MachineVerifier.cpp - Machine Code Verifier -------------*- C++ -*-===// +//===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===// // // The LLVM Compiler Infrastructure // @@ -23,14 +23,18 @@ // the verifier errors. //===----------------------------------------------------------------------===// +#include "llvm/Instructions.h" #include "llvm/Function.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/MC/MCAsmInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" @@ -45,37 +49,47 @@ using namespace llvm; namespace { struct MachineVerifier { - MachineVerifier(Pass *pass) : + MachineVerifier(Pass *pass, const char *b) : PASS(pass), + Banner(b), OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) {} bool runOnMachineFunction(MachineFunction &MF); Pass *const PASS; + const char *Banner; const char *const OutFileName; raw_ostream *OS; const MachineFunction *MF; const TargetMachine *TM; + const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; const MachineRegisterInfo *MRI; unsigned foundErrors; typedef SmallVector RegVector; + typedef SmallVector RegMaskVector; typedef DenseSet RegSet; typedef DenseMap RegMap; + const MachineInstr *FirstTerminator; + BitVector regsReserved; + BitVector regsAllocatable; RegSet regsLive; RegVector regsDefined, regsDead, regsKilled; + RegMaskVector regMasks; RegSet regsLiveInButUnused; + SlotIndex lastIndex; + // Add Reg and any sub-registers to RV void addRegWithSubRegs(RegVector &RV, unsigned Reg) { RV.push_back(Reg); if (TargetRegisterInfo::isPhysicalRegister(Reg)) - for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) + for (const uint16_t *R = TRI->getSubRegisters(Reg); *R; R++) RV.push_back(*R); } @@ -165,9 +179,15 @@ namespace { return Reg < regsReserved.size() && regsReserved.test(Reg); } + bool isAllocatable(unsigned Reg) { + return Reg < regsAllocatable.size() && regsAllocatable.test(Reg); + } + // Analysis information if available LiveVariables *LiveVars; LiveIntervals *LiveInts; + LiveStacks *LiveStks; + SlotIndexes *Indexes; void visitMachineFunctionBefore(); void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); @@ -188,13 +208,17 @@ namespace { void calcRegsRequired(); void verifyLiveVariables(); + void verifyLiveIntervals(); }; struct MachineVerifierPass : public MachineFunctionPass { static char ID; // Pass ID, replacement for typeid + const char *const Banner; - MachineVerifierPass() - : MachineFunctionPass(&ID) {} + MachineVerifierPass(const char *b = 0) + : MachineFunctionPass(ID), Banner(b) { + initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry()); + } void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); @@ -202,7 +226,7 @@ namespace { } bool runOnMachineFunction(MachineFunction &MF) { - MF.verify(this); + MF.verify(this, Banner); return false; } }; @@ -210,16 +234,16 @@ namespace { } char MachineVerifierPass::ID = 0; -static RegisterPass -MachineVer("machineverifier", "Verify generated machine code"); -static const PassInfo *const MachineVerifyID = &MachineVer; +INITIALIZE_PASS(MachineVerifierPass, "machineverifier", + "Verify generated machine code", false, false) -FunctionPass *llvm::createMachineVerifierPass() { - return new MachineVerifierPass(); +FunctionPass *llvm::createMachineVerifierPass(const char *Banner) { + return new MachineVerifierPass(Banner); } -void MachineFunction::verify(Pass *p) const { - MachineVerifier(p).runOnMachineFunction(const_cast(*this)); +void MachineFunction::verify(Pass *p, const char *Banner) const { + MachineVerifier(p, Banner) + .runOnMachineFunction(const_cast(*this)); } bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { @@ -242,23 +266,38 @@ bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { this->MF = &MF; TM = &MF.getTarget(); + TII = TM->getInstrInfo(); TRI = TM->getRegisterInfo(); MRI = &MF.getRegInfo(); + LiveVars = NULL; + LiveInts = NULL; + LiveStks = NULL; + Indexes = NULL; if (PASS) { - LiveVars = PASS->getAnalysisIfAvailable(); LiveInts = PASS->getAnalysisIfAvailable(); - } else { - LiveVars = NULL; - LiveInts = NULL; + // We don't want to verify LiveVariables if LiveIntervals is available. + if (!LiveInts) + LiveVars = PASS->getAnalysisIfAvailable(); + LiveStks = PASS->getAnalysisIfAvailable(); + Indexes = PASS->getAnalysisIfAvailable(); } visitMachineFunctionBefore(); for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); MFI!=MFE; ++MFI) { visitMachineBasicBlockBefore(MFI); - for (MachineBasicBlock::const_iterator MBBI = MFI->begin(), - MBBE = MFI->end(); MBBI != MBBE; ++MBBI) { + for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), + MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) { + if (MBBI->getParent() != MFI) { + report("Bad instruction parent pointer", MFI); + *OS << "Instruction: " << *MBBI; + continue; + } + // Skip BUNDLE instruction for now. FIXME: We should add code to verify + // the BUNDLE's specifically. + if (MBBI->isBundle()) + continue; visitMachineInstrBefore(MBBI); for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) visitMachineOperand(&MBBI->getOperand(I), I); @@ -278,6 +317,7 @@ bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { regsDefined.clear(); regsDead.clear(); regsKilled.clear(); + regMasks.clear(); regsLiveInButUnused.clear(); MBBInfoMap.clear(); @@ -287,10 +327,13 @@ bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { void MachineVerifier::report(const char *msg, const MachineFunction *MF) { assert(MF); *OS << '\n'; - if (!foundErrors++) - MF->print(*OS); + if (!foundErrors++) { + if (Banner) + *OS << "# " << Banner << '\n'; + MF->print(*OS, Indexes); + } *OS << "*** Bad machine code: " << msg << " ***\n" - << "- function: " << MF->getFunction()->getNameStr() << "\n"; + << "- function: " << MF->getFunction()->getName() << "\n"; } void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { @@ -298,13 +341,19 @@ void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { report(msg, MBB->getParent()); *OS << "- basic block: " << MBB->getName() << " " << (void*)MBB - << " (BB#" << MBB->getNumber() << ")\n"; + << " (BB#" << MBB->getNumber() << ")"; + if (Indexes) + *OS << " [" << Indexes->getMBBStartIdx(MBB) + << ';' << Indexes->getMBBEndIdx(MBB) << ')'; + *OS << '\n'; } void MachineVerifier::report(const char *msg, const MachineInstr *MI) { assert(MI); report(msg, MI->getParent()); *OS << "- instruction: "; + if (Indexes && Indexes->hasIndex(MI)) + *OS << Indexes->getInstructionIndex(MI) << '\t'; MI->print(*OS, TM); } @@ -328,17 +377,21 @@ void MachineVerifier::markReachable(const MachineBasicBlock *MBB) { } void MachineVerifier::visitMachineFunctionBefore() { + lastIndex = SlotIndex(); regsReserved = TRI->getReservedRegs(*MF); // A sub-register of a reserved register is also reserved for (int Reg = regsReserved.find_first(); Reg>=0; Reg = regsReserved.find_next(Reg)) { - for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) { + for (const uint16_t *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) { // FIXME: This should probably be: // assert(regsReserved.test(*Sub) && "Non-reserved sub-register"); regsReserved.set(*Sub); } } + + regsAllocatable = TRI->getAllocatableSet(*MF); + markReachable(&MF->front()); } @@ -354,7 +407,37 @@ static bool matchPair(MachineBasicBlock::const_succ_iterator i, void MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { - const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); + FirstTerminator = 0; + + if (MRI->isSSA()) { + // If this block has allocatable physical registers live-in, check that + // it is an entry block or landing pad. + for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), + LE = MBB->livein_end(); + LI != LE; ++LI) { + unsigned reg = *LI; + if (isAllocatable(reg) && !MBB->isLandingPad() && + MBB != MBB->getParent()->begin()) { + report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB); + } + } + } + + // Count the number of landing pad successors. + SmallPtrSet LandingPadSuccs; + for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), + E = MBB->succ_end(); I != E; ++I) { + if ((*I)->isLandingPad()) + LandingPadSuccs.insert(*I); + } + + const MCAsmInfo *AsmInfo = TM->getMCAsmInfo(); + const BasicBlock *BB = MBB->getBasicBlock(); + if (LandingPadSuccs.size() > 1 && + !(AsmInfo && + AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj && + BB && isa(BB->getTerminator()))) + report("MBB has more than one landing pad successor", MBB); // Call AnalyzeBranch. If it succeeds, there several more conditions to check. MachineBasicBlock *TBB = 0, *FBB = 0; @@ -371,18 +454,18 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { // It's possible that the block legitimately ends with a noreturn // call or an unreachable, in which case it won't actually fall // out the bottom of the function. - } else if (MBB->succ_empty()) { + } else if (MBB->succ_size() == LandingPadSuccs.size()) { // It's possible that the block legitimately ends with a noreturn // call or an unreachable, in which case it won't actuall fall // out of the block. - } else if (MBB->succ_size() != 1) { + } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) { report("MBB exits via unconditional fall-through but doesn't have " "exactly one CFG successor!", MBB); - } else if (MBB->succ_begin()[0] != MBBI) { + } else if (!MBB->isSuccessor(MBBI)) { report("MBB exits via unconditional fall-through but its successor " "differs from its CFG successor!", MBB); } - if (!MBB->empty() && MBB->back().getDesc().isBarrier() && + if (!MBB->empty() && MBB->back().isBarrier() && !TII->isPredicated(&MBB->back())) { report("MBB exits via unconditional fall-through but ends with a " "barrier instruction!", MBB); @@ -393,20 +476,20 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { } } else if (TBB && !FBB && Cond.empty()) { // Block unconditionally branches somewhere. - if (MBB->succ_size() != 1) { + if (MBB->succ_size() != 1+LandingPadSuccs.size()) { report("MBB exits via unconditional branch but doesn't have " "exactly one CFG successor!", MBB); - } else if (MBB->succ_begin()[0] != TBB) { + } else if (!MBB->isSuccessor(TBB)) { report("MBB exits via unconditional branch but the CFG " "successor doesn't match the actual successor!", MBB); } if (MBB->empty()) { report("MBB exits via unconditional branch but doesn't contain " "any instructions!", MBB); - } else if (!MBB->back().getDesc().isBarrier()) { + } else if (!MBB->back().isBarrier()) { report("MBB exits via unconditional branch but doesn't end with a " "barrier instruction!", MBB); - } else if (!MBB->back().getDesc().isTerminator()) { + } else if (!MBB->back().isTerminator()) { report("MBB exits via unconditional branch but the branch isn't a " "terminator instruction!", MBB); } @@ -426,10 +509,10 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { if (MBB->empty()) { report("MBB exits via conditional branch/fall-through but doesn't " "contain any instructions!", MBB); - } else if (MBB->back().getDesc().isBarrier()) { + } else if (MBB->back().isBarrier()) { report("MBB exits via conditional branch/fall-through but ends with a " "barrier instruction!", MBB); - } else if (!MBB->back().getDesc().isTerminator()) { + } else if (!MBB->back().isTerminator()) { report("MBB exits via conditional branch/fall-through but the branch " "isn't a terminator instruction!", MBB); } @@ -446,10 +529,10 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { if (MBB->empty()) { report("MBB exits via conditional branch/branch but doesn't " "contain any instructions!", MBB); - } else if (!MBB->back().getDesc().isBarrier()) { + } else if (!MBB->back().isBarrier()) { report("MBB exits via conditional branch/branch but doesn't end with a " "barrier instruction!", MBB); - } else if (!MBB->back().getDesc().isTerminator()) { + } else if (!MBB->back().isTerminator()) { report("MBB exits via conditional branch/branch but the branch " "isn't a terminator instruction!", MBB); } @@ -470,7 +553,7 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { continue; } regsLive.insert(*I); - for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++) + for (const uint16_t *R = TRI->getSubRegisters(*I); *R; R++) regsLive.insert(*R); } regsLiveInButUnused = regsLive; @@ -480,69 +563,91 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { BitVector PR = MFI->getPristineRegs(MBB); for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { regsLive.insert(I); - for (const unsigned *R = TRI->getSubRegisters(I); *R; R++) + for (const uint16_t *R = TRI->getSubRegisters(I); *R; R++) regsLive.insert(*R); } regsKilled.clear(); regsDefined.clear(); + + if (Indexes) + lastIndex = Indexes->getMBBStartIdx(MBB); } void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { - const TargetInstrDesc &TI = MI->getDesc(); - if (MI->getNumOperands() < TI.getNumOperands()) { + const MCInstrDesc &MCID = MI->getDesc(); + if (MI->getNumOperands() < MCID.getNumOperands()) { report("Too few operands", MI); - *OS << TI.getNumOperands() << " operands expected, but " + *OS << MCID.getNumOperands() << " operands expected, but " << MI->getNumExplicitOperands() << " given.\n"; } // Check the MachineMemOperands for basic consistency. for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I) { - if ((*I)->isLoad() && !TI.mayLoad()) + if ((*I)->isLoad() && !MI->mayLoad()) report("Missing mayLoad flag", MI); - if ((*I)->isStore() && !TI.mayStore()) + if ((*I)->isStore() && !MI->mayStore()) report("Missing mayStore flag", MI); } // Debug values must not have a slot index. - // Other instructions must have one. + // Other instructions must have one, unless they are inside a bundle. if (LiveInts) { bool mapped = !LiveInts->isNotInMIMap(MI); if (MI->isDebugValue()) { if (mapped) report("Debug instruction has a slot index", MI); + } else if (MI->isInsideBundle()) { + if (mapped) + report("Instruction inside bundle has a slot index", MI); } else { if (!mapped) report("Missing slot index", MI); } } + // Ensure non-terminators don't follow terminators. + if (MI->isTerminator()) { + if (!FirstTerminator) + FirstTerminator = MI; + } else if (FirstTerminator) { + report("Non-terminator instruction after the first terminator", MI); + *OS << "First terminator was:\t" << *FirstTerminator; + } + + StringRef ErrorInfo; + if (!TII->verifyInstruction(MI, ErrorInfo)) + report(ErrorInfo.data(), MI); } void MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { const MachineInstr *MI = MO->getParent(); - const TargetInstrDesc &TI = MI->getDesc(); + const MCInstrDesc &MCID = MI->getDesc(); + const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; - // The first TI.NumDefs operands must be explicit register defines - if (MONum < TI.getNumDefs()) { + // The first MCID.NumDefs operands must be explicit register defines + if (MONum < MCID.getNumDefs()) { if (!MO->isReg()) report("Explicit definition must be a register", MO, MONum); else if (!MO->isDef()) report("Explicit definition marked as use", MO, MONum); else if (MO->isImplicit()) report("Explicit definition marked as implicit", MO, MONum); - } else if (MONum < TI.getNumOperands()) { - if (MO->isReg()) { - if (MO->isDef()) - report("Explicit operand marked as def", MO, MONum); + } else if (MONum < MCID.getNumOperands()) { + // Don't check if it's the last operand in a variadic instruction. See, + // e.g., LDM_RET in the arm back end. + if (MO->isReg() && + !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { + if (MO->isDef() && !MCOI.isOptionalDef()) + report("Explicit operand marked as def", MO, MONum); if (MO->isImplicit()) report("Explicit operand marked as implicit", MO, MONum); } } else { // ARM adds %reg0 operands to indicate predicates. We'll allow that. - if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic() && MO->getReg()) + if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg()) report("Extra explicit operand on non-variadic instruction", MO, MONum); } @@ -553,9 +658,9 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { return; // Check Live Variables. - if (MO->isUndef()) { - // An doesn't refer to any register, so just skip it. - } else if (MO->isUse()) { + if (MI->isDebugValue()) { + // Liveness checks are not valid for debug values. + } else if (MO->isUse() && !MO->isUndef()) { regsLiveInButUnused.erase(Reg); bool isKill = false; @@ -563,42 +668,44 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { if (MI->isRegTiedToDefOperand(MONum, &defIdx)) { // A two-addr use counts as a kill if use and def are the same. unsigned DefReg = MI->getOperand(defIdx).getReg(); - if (Reg == DefReg) { + if (Reg == DefReg) isKill = true; - // ANd in that case an explicit kill flag is not allowed. - if (MO->isKill()) - report("Illegal kill flag on two-address instruction operand", - MO, MONum); - } else if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + else if (TargetRegisterInfo::isPhysicalRegister(Reg)) { report("Two-address instruction operands must be identical", MO, MONum); } } else isKill = MO->isKill(); - if (isKill) { + if (isKill) addRegWithSubRegs(regsKilled, Reg); - // Check that LiveVars knows this kill - if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg)) { - LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); - if (std::find(VI.Kills.begin(), - VI.Kills.end(), MI) == VI.Kills.end()) - report("Kill missing from LiveVariables", MO, MONum); - } + // Check that LiveVars knows this kill. + if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) && + MO->isKill()) { + LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); + if (std::find(VI.Kills.begin(), + VI.Kills.end(), MI) == VI.Kills.end()) + report("Kill missing from LiveVariables", MO, MONum); } // Check LiveInts liveness and kill. - if (LiveInts && !LiveInts->isNotInMIMap(MI)) { - SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getUseIndex(); + if (TargetRegisterInfo::isVirtualRegister(Reg) && + LiveInts && !LiveInts->isNotInMIMap(MI)) { + SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getRegSlot(true); if (LiveInts->hasInterval(Reg)) { const LiveInterval &LI = LiveInts->getInterval(Reg); if (!LI.liveAt(UseIdx)) { report("No live range at use", MO, MONum); *OS << UseIdx << " is not live in " << LI << '\n'; } - // TODO: Verify isKill == LI.killedAt. - } else if (TargetRegisterInfo::isVirtualRegister(Reg)) { + // Check for extra kill flags. + // Note that we allow missing kill flags for now. + if (MO->isKill() && !LI.killedAt(UseIdx.getRegSlot())) { + report("Live range continues after kill flag", MO, MONum); + *OS << "Live range: " << LI << '\n'; + } + } else { report("Virtual register has no Live interval", MO, MONum); } } @@ -620,8 +727,7 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); } } - } else { - assert(MO->isDef()); + } else if (MO->isDef()) { // Register defined. // TODO: verify that earlyclobber ops are not used. if (MO->isDead()) @@ -629,53 +735,47 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { else addRegWithSubRegs(regsDefined, Reg); - // Check LiveInts for a live range. - if (LiveInts && !LiveInts->isNotInMIMap(MI)) { - SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getDefIndex(); + // Verify SSA form. + if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) && + llvm::next(MRI->def_begin(Reg)) != MRI->def_end()) + report("Multiple virtual register defs in SSA form", MO, MONum); + + // Check LiveInts for a live range, but only for virtual registers. + if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) && + !LiveInts->isNotInMIMap(MI)) { + SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getRegSlot(); if (LiveInts->hasInterval(Reg)) { const LiveInterval &LI = LiveInts->getInterval(Reg); - if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) { - assert(LR->valno && "NULL valno is not allowed"); - if (LR->valno->def != DefIdx) { + if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) { + assert(VNI && "NULL valno is not allowed"); + if (VNI->def != DefIdx && !MO->isEarlyClobber()) { report("Inconsistent valno->def", MO, MONum); - *OS << "Valno " << LR->valno->id << " is not defined at " + *OS << "Valno " << VNI->id << " is not defined at " << DefIdx << " in " << LI << '\n'; } - if (LR->start != DefIdx) { - report("Live range doesn't start at def", MO, MONum); - LR->print(*OS); - *OS << " should start at " << DefIdx << " in " << LI << '\n'; - } } else { report("No live range at def", MO, MONum); *OS << DefIdx << " is not live in " << LI << '\n'; } - } else if (TargetRegisterInfo::isVirtualRegister(Reg)) { + } else { report("Virtual register has no Live interval", MO, MONum); } } } // Check register classes. - if (MONum < TI.getNumOperands() && !MO->isImplicit()) { - const TargetOperandInfo &TOI = TI.OpInfo[MONum]; + if (MONum < MCID.getNumOperands() && !MO->isImplicit()) { unsigned SubIdx = MO->getSubReg(); if (TargetRegisterInfo::isPhysicalRegister(Reg)) { - unsigned sr = Reg; if (SubIdx) { - unsigned s = TRI->getSubReg(Reg, SubIdx); - if (!s) { - report("Invalid subregister index for physical register", - MO, MONum); - return; - } - sr = s; + report("Illegal subregister index for physical register", MO, MONum); + return; } - if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) { - if (!DRC->contains(sr)) { + if (const TargetRegisterClass *DRC = TII->getRegClass(MCID,MONum,TRI)) { + if (!DRC->contains(Reg)) { report("Illegal physical register for instruction", MO, MONum); - *OS << TRI->getName(sr) << " is not a " + *OS << TRI->getName(Reg) << " is not a " << DRC->getName() << " register.\n"; } } @@ -683,17 +783,36 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { // Virtual register. const TargetRegisterClass *RC = MRI->getRegClass(Reg); if (SubIdx) { - const TargetRegisterClass *SRC = RC->getSubRegisterRegClass(SubIdx); + const TargetRegisterClass *SRC = + TRI->getSubClassWithSubReg(RC, SubIdx); if (!SRC) { report("Invalid subregister index for virtual register", MO, MONum); *OS << "Register class " << RC->getName() << " does not support subreg index " << SubIdx << "\n"; return; } - RC = SRC; + if (RC != SRC) { + report("Invalid register class for subregister index", MO, MONum); + *OS << "Register class " << RC->getName() + << " does not fully support subreg index " << SubIdx << "\n"; + return; + } } - if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) { - if (RC != DRC && !RC->hasSuperClass(DRC)) { + if (const TargetRegisterClass *DRC = TII->getRegClass(MCID,MONum,TRI)) { + if (SubIdx) { + const TargetRegisterClass *SuperRC = + TRI->getLargestLegalSuperClass(RC); + if (!SuperRC) { + report("No largest legal super class exists.", MO, MONum); + return; + } + DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx); + if (!DRC) { + report("No matching super-reg register class.", MO, MONum); + return; + } + } + if (!RC->hasSuperClassEq(DRC)) { report("Illegal virtual register for instruction", MO, MONum); *OS << "Expected a " << DRC->getName() << " register, but got a " << RC->getName() << " register\n"; @@ -704,11 +823,31 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { break; } + case MachineOperand::MO_RegisterMask: + regMasks.push_back(MO->getRegMask()); + break; + case MachineOperand::MO_MachineBasicBlock: if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent())) report("PHI operand is not in the CFG", MO, MONum); break; + case MachineOperand::MO_FrameIndex: + if (LiveStks && LiveStks->hasInterval(MO->getIndex()) && + LiveInts && !LiveInts->isNotInMIMap(MI)) { + LiveInterval &LI = LiveStks->getInterval(MO->getIndex()); + SlotIndex Idx = LiveInts->getInstructionIndex(MI); + if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) { + report("Instruction loads from dead spill slot", MO, MONum); + *OS << "Live stack: " << LI << '\n'; + } + if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) { + report("Instruction stores to dead spill slot", MO, MONum); + *OS << "Live stack: " << LI << '\n'; + } + } + break; + default: break; } @@ -718,14 +857,41 @@ void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { BBInfo &MInfo = MBBInfoMap[MI->getParent()]; set_union(MInfo.regsKilled, regsKilled); set_subtract(regsLive, regsKilled); regsKilled.clear(); + // Kill any masked registers. + while (!regMasks.empty()) { + const uint32_t *Mask = regMasks.pop_back_val(); + for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I) + if (TargetRegisterInfo::isPhysicalRegister(*I) && + MachineOperand::clobbersPhysReg(Mask, *I)) + regsDead.push_back(*I); + } set_subtract(regsLive, regsDead); regsDead.clear(); set_union(regsLive, regsDefined); regsDefined.clear(); + + if (Indexes && Indexes->hasIndex(MI)) { + SlotIndex idx = Indexes->getInstructionIndex(MI); + if (!(idx > lastIndex)) { + report("Instruction index out of order", MI); + *OS << "Last instruction was at " << lastIndex << '\n'; + } + lastIndex = idx; + } } void MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { MBBInfoMap[MBB].regsLiveOut = regsLive; regsLive.clear(); + + if (Indexes) { + SlotIndex stop = Indexes->getMBBEndIdx(MBB); + if (!(stop > lastIndex)) { + report("Block ends before last instruction index", MBB); + *OS << "Block ends at " << stop + << " last instruction was at " << lastIndex << '\n'; + } + lastIndex = stop; + } } // Calculate the largest possible vregsPassed sets. These are the registers that @@ -734,7 +900,7 @@ MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { void MachineVerifier::calcRegsPassed() { // First push live-out regs to successors' vregsPassed. Remember the MBBs that // have any vregsPassed. - DenseSet todo; + SmallPtrSet todo; for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); MFI != MFE; ++MFI) { const MachineBasicBlock &MBB(*MFI); @@ -771,7 +937,7 @@ void MachineVerifier::calcRegsPassed() { // similar to calcRegsPassed, only backwards. void MachineVerifier::calcRegsRequired() { // First push live-in regs to predecessors' vregsRequired. - DenseSet todo; + SmallPtrSet todo; for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); MFI != MFE; ++MFI) { const MachineBasicBlock &MBB(*MFI); @@ -804,9 +970,10 @@ void MachineVerifier::calcRegsRequired() { // Check PHI instructions at the beginning of MBB. It is assumed that // calcRegsPassed has been run so BBInfo::isLiveOut is valid. void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) { + SmallPtrSet seen; for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); BBI != BBE && BBI->isPHI(); ++BBI) { - DenseSet seen; + seen.clear(); for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { unsigned Reg = BBI->getOperand(i).getReg(); @@ -846,17 +1013,28 @@ void MachineVerifier::visitMachineFunctionAfter() { checkPHIOps(MFI); } - // Now check LiveVariables info if available - if (LiveVars) { - calcRegsRequired(); - verifyLiveVariables(); + // Now check liveness info if available + calcRegsRequired(); + + if (MRI->isSSA() && !MF->empty()) { + BBInfo &MInfo = MBBInfoMap[&MF->front()]; + for (RegSet::iterator + I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; + ++I) + report("Virtual register def doesn't dominate all uses.", + MRI->getVRegDef(*I)); } + + if (LiveVars) + verifyLiveVariables(); + if (LiveInts) + verifyLiveIntervals(); } void MachineVerifier::verifyLiveVariables() { assert(LiveVars && "Don't call verifyLiveVariables without LiveVars"); - for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister, - RegE = MRI->getLastVirtReg()-1; Reg != RegE; ++Reg) { + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); MFI != MFE; ++MFI) { @@ -866,13 +1044,13 @@ void MachineVerifier::verifyLiveVariables() { if (MInfo.vregsRequired.count(Reg)) { if (!VI.AliveBlocks.test(MFI->getNumber())) { report("LiveVariables: Block missing from AliveBlocks", MFI); - *OS << "Virtual register %reg" << Reg + *OS << "Virtual register " << PrintReg(Reg) << " must be live through the block.\n"; } } else { if (VI.AliveBlocks.test(MFI->getNumber())) { report("LiveVariables: Block should not be in AliveBlocks", MFI); - *OS << "Virtual register %reg" << Reg + *OS << "Virtual register " << PrintReg(Reg) << " is not needed live through the block.\n"; } } @@ -880,4 +1058,294 @@ void MachineVerifier::verifyLiveVariables() { } } +void MachineVerifier::verifyLiveIntervals() { + assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts"); + for (LiveIntervals::const_iterator LVI = LiveInts->begin(), + LVE = LiveInts->end(); LVI != LVE; ++LVI) { + const LiveInterval &LI = *LVI->second; + + // Spilling and splitting may leave unused registers around. Skip them. + if (MRI->use_empty(LI.reg)) + continue; + + // Physical registers have much weirdness going on, mostly from coalescing. + // We should probably fix it, but for now just ignore them. + if (TargetRegisterInfo::isPhysicalRegister(LI.reg)) + continue; + + assert(LVI->first == LI.reg && "Invalid reg to interval mapping"); + + for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); + I!=E; ++I) { + VNInfo *VNI = *I; + const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def); + + if (!DefVNI) { + if (!VNI->isUnused()) { + report("Valno not live at def and not marked unused", MF); + *OS << "Valno #" << VNI->id << " in " << LI << '\n'; + } + continue; + } + + if (VNI->isUnused()) + continue; + + if (DefVNI != VNI) { + report("Live range at def has different valno", MF); + *OS << "Valno #" << VNI->id << " is defined at " << VNI->def + << " where valno #" << DefVNI->id << " is live in " << LI << '\n'; + continue; + } + + const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); + if (!MBB) { + report("Invalid definition index", MF); + *OS << "Valno #" << VNI->id << " is defined at " << VNI->def + << " in " << LI << '\n'; + continue; + } + + if (VNI->isPHIDef()) { + if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { + report("PHIDef value is not defined at MBB start", MF); + *OS << "Valno #" << VNI->id << " is defined at " << VNI->def + << ", not at the beginning of BB#" << MBB->getNumber() + << " in " << LI << '\n'; + } + } else { + // Non-PHI def. + const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); + if (!MI) { + report("No instruction at def index", MF); + *OS << "Valno #" << VNI->id << " is defined at " << VNI->def + << " in " << LI << '\n'; + continue; + } + + bool hasDef = false; + bool isEarlyClobber = false; + for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { + if (!MOI->isReg() || !MOI->isDef()) + continue; + if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { + if (MOI->getReg() != LI.reg) + continue; + } else { + if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || + !TRI->regsOverlap(LI.reg, MOI->getReg())) + continue; + } + hasDef = true; + if (MOI->isEarlyClobber()) + isEarlyClobber = true; + } + + if (!hasDef) { + report("Defining instruction does not modify register", MI); + *OS << "Valno #" << VNI->id << " in " << LI << '\n'; + } + + // Early clobber defs begin at USE slots, but other defs must begin at + // DEF slots. + if (isEarlyClobber) { + if (!VNI->def.isEarlyClobber()) { + report("Early clobber def must be at an early-clobber slot", MF); + *OS << "Valno #" << VNI->id << " is defined at " << VNI->def + << " in " << LI << '\n'; + } + } else if (!VNI->def.isRegister()) { + report("Non-PHI, non-early clobber def must be at a register slot", + MF); + *OS << "Valno #" << VNI->id << " is defined at " << VNI->def + << " in " << LI << '\n'; + } + } + } + + for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) { + const VNInfo *VNI = I->valno; + assert(VNI && "Live range has no valno"); + + if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) { + report("Foreign valno in live range", MF); + I->print(*OS); + *OS << " has a valno not in " << LI << '\n'; + } + + if (VNI->isUnused()) { + report("Live range valno is marked unused", MF); + I->print(*OS); + *OS << " in " << LI << '\n'; + } + + const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start); + if (!MBB) { + report("Bad start of live segment, no basic block", MF); + I->print(*OS); + *OS << " in " << LI << '\n'; + continue; + } + SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB); + if (I->start != MBBStartIdx && I->start != VNI->def) { + report("Live segment must begin at MBB entry or valno def", MBB); + I->print(*OS); + *OS << " in " << LI << '\n' << "Basic block starts at " + << MBBStartIdx << '\n'; + } + + const MachineBasicBlock *EndMBB = + LiveInts->getMBBFromIndex(I->end.getPrevSlot()); + if (!EndMBB) { + report("Bad end of live segment, no basic block", MF); + I->print(*OS); + *OS << " in " << LI << '\n'; + continue; + } + + // No more checks for live-out segments. + if (I->end == LiveInts->getMBBEndIdx(EndMBB)) + continue; + + // The live segment is ending inside EndMBB + const MachineInstr *MI = + LiveInts->getInstructionFromIndex(I->end.getPrevSlot()); + if (!MI) { + report("Live segment doesn't end at a valid instruction", EndMBB); + I->print(*OS); + *OS << " in " << LI << '\n' << "Basic block starts at " + << MBBStartIdx << '\n'; + continue; + } + + // The block slot must refer to a basic block boundary. + if (I->end.isBlock()) { + report("Live segment ends at B slot of an instruction", MI); + I->print(*OS); + *OS << " in " << LI << '\n'; + } + + if (I->end.isDead()) { + // Segment ends on the dead slot. + // That means there must be a dead def. + if (!SlotIndex::isSameInstr(I->start, I->end)) { + report("Live segment ending at dead slot spans instructions", MI); + I->print(*OS); + *OS << " in " << LI << '\n'; + } + } + + // A live segment can only end at an early-clobber slot if it is being + // redefined by an early-clobber def. + if (I->end.isEarlyClobber()) { + if (I+1 == E || (I+1)->start != I->end) { + report("Live segment ending at early clobber slot must be " + "redefined by an EC def in the same instruction", MI); + I->print(*OS); + *OS << " in " << LI << '\n'; + } + } + + // The following checks only apply to virtual registers. Physreg liveness + // is too weird to check. + if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { + // A live range can end with either a redefinition, a kill flag on a + // use, or a dead flag on a def. + bool hasRead = false; + bool hasDeadDef = false; + for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { + if (!MOI->isReg() || MOI->getReg() != LI.reg) + continue; + if (MOI->readsReg()) + hasRead = true; + if (MOI->isDef() && MOI->isDead()) + hasDeadDef = true; + } + + if (I->end.isDead()) { + if (!hasDeadDef) { + report("Instruction doesn't have a dead def operand", MI); + I->print(*OS); + *OS << " in " << LI << '\n'; + } + } else { + if (!hasRead) { + report("Instruction ending live range doesn't read the register", + MI); + I->print(*OS); + *OS << " in " << LI << '\n'; + } + } + } + + // Now check all the basic blocks in this live segment. + MachineFunction::const_iterator MFI = MBB; + // Is this live range the beginning of a non-PHIDef VN? + if (I->start == VNI->def && !VNI->isPHIDef()) { + // Not live-in to any blocks. + if (MBB == EndMBB) + continue; + // Skip this block. + ++MFI; + } + for (;;) { + assert(LiveInts->isLiveInToMBB(LI, MFI)); + // We don't know how to track physregs into a landing pad. + if (TargetRegisterInfo::isPhysicalRegister(LI.reg) && + MFI->isLandingPad()) { + if (&*MFI == EndMBB) + break; + ++MFI; + continue; + } + // Check that VNI is live-out of all predecessors. + for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(), + PE = MFI->pred_end(); PI != PE; ++PI) { + SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI); + const VNInfo *PVNI = LI.getVNInfoBefore(PEnd); + + if (VNI->isPHIDef() && VNI->def == LiveInts->getMBBStartIdx(MFI)) + continue; + + if (!PVNI) { + report("Register not marked live out of predecessor", *PI); + *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber() + << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before " + << PEnd << " in " << LI << '\n'; + continue; + } + + if (PVNI != VNI) { + report("Different value live out of predecessor", *PI); + *OS << "Valno #" << PVNI->id << " live out of BB#" + << (*PI)->getNumber() << '@' << PEnd + << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber() + << '@' << LiveInts->getMBBStartIdx(MFI) << " in " << LI << '\n'; + } + } + if (&*MFI == EndMBB) + break; + ++MFI; + } + } + + // Check the LI only has one connected component. + if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { + ConnectedVNInfoEqClasses ConEQ(*LiveInts); + unsigned NumComp = ConEQ.Classify(&LI); + if (NumComp > 1) { + report("Multiple connected components in live interval", MF); + *OS << NumComp << " components in " << LI << '\n'; + for (unsigned comp = 0; comp != NumComp; ++comp) { + *OS << comp << ": valnos"; + for (LiveInterval::const_vni_iterator I = LI.vni_begin(), + E = LI.vni_end(); I!=E; ++I) + if (comp == ConEQ.getEqClass(*I)) + *OS << ' ' << (*I)->id; + *OS << '\n'; + } + } + } + } +}