X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineVerifier.cpp;h=d61470c173bcd0713dc99ec9f486851f309739e1;hb=5be77762a3aa434ee877b0a03b98b5c3a7571918;hp=bf4882044b64e6074f8e65c00f594772db7419ac;hpb=90a4f78d3b23576da92a60a731cb34767fd75db8;p=oota-llvm.git diff --git a/lib/CodeGen/MachineVerifier.cpp b/lib/CodeGen/MachineVerifier.cpp index bf4882044b6..d61470c173b 100644 --- a/lib/CodeGen/MachineVerifier.cpp +++ b/lib/CodeGen/MachineVerifier.cpp @@ -23,28 +23,29 @@ // the verifier errors. //===----------------------------------------------------------------------===// -#include "llvm/BasicBlock.h" -#include "llvm/InlineAsm.h" -#include "llvm/Instructions.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SetOperations.h" +#include "llvm/ADT/SmallVector.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/LiveVariables.h" #include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/InlineAsm.h" +#include "llvm/IR/Instructions.h" #include "llvm/MC/MCAsmInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/SetOperations.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" using namespace llvm; namespace { @@ -80,7 +81,6 @@ namespace { BlockSet FunctionBlocks; BitVector regsReserved; - BitVector regsAllocatable; RegSet regsLive; RegVector regsDefined, regsDead, regsKilled; RegMaskVector regMasks; @@ -186,7 +186,7 @@ namespace { } bool isAllocatable(unsigned Reg) { - return Reg < regsAllocatable.size() && regsAllocatable.test(Reg); + return Reg < TRI->getNumRegs() && MRI->isAllocatable(Reg); } // Analysis information if available @@ -213,9 +213,12 @@ namespace { const LiveInterval &LI); void report(const char *msg, const MachineBasicBlock *MBB, const LiveInterval &LI); + void report(const char *msg, const MachineFunction *MF, + const LiveRange &LR); + void report(const char *msg, const MachineBasicBlock *MBB, + const LiveRange &LR); void verifyInlineAsm(const MachineInstr *MI); - void verifyTiedOperands(const MachineInstr *MI); void checkLiveness(const MachineOperand *MO, unsigned MONum); void markReachable(const MachineBasicBlock *MBB); @@ -226,9 +229,12 @@ namespace { void verifyLiveVariables(); void verifyLiveIntervals(); void verifyLiveInterval(const LiveInterval&); - void verifyLiveIntervalValue(const LiveInterval&, VNInfo*); - void verifyLiveIntervalSegment(const LiveInterval&, - LiveInterval::const_iterator); + void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned); + void verifyLiveRangeSegment(const LiveRange&, + const LiveRange::const_iterator I, unsigned); + void verifyLiveRange(const LiveRange&, unsigned); + + void verifyStackFrame(); }; struct MachineVerifierPass : public MachineFunctionPass { @@ -270,8 +276,7 @@ bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { raw_ostream *OutFile = 0; if (OutFileName) { std::string ErrorInfo; - OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, - raw_fd_ostream::F_Append); + OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, sys::fs::F_Append); if (!ErrorInfo.empty()) { errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n'; exit(1); @@ -309,6 +314,9 @@ bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { visitMachineBasicBlockBefore(MFI); // Keep track of the current bundle header. const MachineInstr *CurBundle = 0; + // Do we expect the next instruction to be part of the same bundle? + bool InBundle = false; + for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) { if (MBBI->getParent() != MFI) { @@ -316,6 +324,15 @@ bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { *OS << "Instruction: " << *MBBI; continue; } + + // Check for consistent bundle flags. + if (InBundle && !MBBI->isBundledWithPred()) + report("Missing BundledPred flag, " + "BundledSucc was set on predecessor", MBBI); + if (!InBundle && MBBI->isBundledWithPred()) + report("BundledPred flag is set, " + "but BundledSucc not set on predecessor", MBBI); + // Is this a bundle header? if (!MBBI->isInsideBundle()) { if (CurBundle) @@ -328,9 +345,14 @@ bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) visitMachineOperand(&MBBI->getOperand(I), I); visitMachineInstrAfter(MBBI); + + // Was this the last bundled instruction? + InBundle = MBBI->isBundledWithSucc(); } if (CurBundle) visitMachineBundleAfter(CurBundle); + if (InBundle) + report("BundledSucc flag set on last instruction in block", &MFI->back()); visitMachineBasicBlockAfter(MFI); } visitMachineFunctionAfter(); @@ -369,7 +391,7 @@ void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { report(msg, MBB->getParent()); *OS << "- basic block: BB#" << MBB->getNumber() << ' ' << MBB->getName() - << " (" << (void*)MBB << ')'; + << " (" << (const void*)MBB << ')'; if (Indexes) *OS << " [" << Indexes->getMBBStartIdx(MBB) << ';' << Indexes->getMBBEndIdx(MBB) << ')'; @@ -397,23 +419,25 @@ void MachineVerifier::report(const char *msg, void MachineVerifier::report(const char *msg, const MachineFunction *MF, const LiveInterval &LI) { report(msg, MF); - *OS << "- interval: "; - if (TargetRegisterInfo::isVirtualRegister(LI.reg)) - *OS << PrintReg(LI.reg, TRI); - else - *OS << PrintRegUnit(LI.reg, TRI); - *OS << ' ' << LI << '\n'; + *OS << "- interval: " << LI << '\n'; } void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, const LiveInterval &LI) { report(msg, MBB); - *OS << "- interval: "; - if (TargetRegisterInfo::isVirtualRegister(LI.reg)) - *OS << PrintReg(LI.reg, TRI); - else - *OS << PrintRegUnit(LI.reg, TRI); - *OS << ' ' << LI << '\n'; + *OS << "- interval: " << LI << '\n'; +} + +void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, + const LiveRange &LR) { + report(msg, MBB); + *OS << "- liverange: " << LR << "\n"; +} + +void MachineVerifier::report(const char *msg, const MachineFunction *MF, + const LiveRange &LR) { + report(msg, MF); + *OS << "- liverange: " << LR << "\n"; } void MachineVerifier::markReachable(const MachineBasicBlock *MBB) { @@ -428,7 +452,7 @@ void MachineVerifier::markReachable(const MachineBasicBlock *MBB) { void MachineVerifier::visitMachineFunctionBefore() { lastIndex = SlotIndex(); - regsReserved = TRI->getReservedRegs(*MF); + regsReserved = MRI->getReservedRegs(); // A sub-register of a reserved register is also reserved for (int Reg = regsReserved.find_first(); Reg>=0; @@ -440,8 +464,6 @@ void MachineVerifier::visitMachineFunctionBefore() { } } - regsAllocatable = TRI->getAllocatableSet(*MF); - markReachable(&MF->front()); // Build a set of the basic blocks in the function. @@ -459,6 +481,11 @@ void MachineVerifier::visitMachineFunctionBefore() { if (MInfo.Succs.size() != I->succ_size()) report("MBB has duplicate entries in its successor list.", I); } + + // Check that the register use lists are sane. + MRI->verifyUseLists(); + + verifyStackFrame(); } // Does iterator point to a and b as the first two elements? @@ -584,7 +611,7 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { ++MBBI; if (MBBI == MF->end()) { report("MBB conditionally falls through out of function!", MBB); - } if (MBB->succ_size() == 1) { + } else if (MBB->succ_size() == 1) { // A conditional branch with only one successor is weird, but allowed. if (&*MBBI != TBB) report("MBB exits via conditional branch/fall-through but only has " @@ -653,8 +680,8 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { report("MBB live-in list contains non-physical register", MBB); continue; } - regsLive.insert(*I); - for (MCSubRegIterator SubRegs(*I, TRI); SubRegs.isValid(); ++SubRegs) + for (MCSubRegIterator SubRegs(*I, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) regsLive.insert(*SubRegs); } regsLiveInButUnused = regsLive; @@ -663,8 +690,8 @@ MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { assert(MFI && "Function has no frame info"); BitVector PR = MFI->getPristineRegs(MBB); for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { - regsLive.insert(I); - for (MCSubRegIterator SubRegs(I, TRI); SubRegs.isValid(); ++SubRegs) + for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) regsLive.insert(*SubRegs); } @@ -711,8 +738,9 @@ void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) { report("Asm string must be an external symbol", MI); if (!MI->getOperand(1).isImm()) report("Asm flags must be an immediate", MI); - // Allowed flags are Extra_HasSideEffects = 1, and Extra_IsAlignStack = 2. - if (!isUInt<2>(MI->getOperand(1).getImm())) + // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2, + // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16. + if (!isUInt<5>(MI->getOperand(1).getImm())) report("Unknown asm flags", &MI->getOperand(1), 1); assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed"); @@ -742,51 +770,17 @@ void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) { } } -// Verify the consistency of tied operands. -void MachineVerifier::verifyTiedOperands(const MachineInstr *MI) { - const MCInstrDesc &MCID = MI->getDesc(); - SmallVector Defs; - SmallVector Uses; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isTied()) - continue; - if (MO.isDef()) { - Defs.push_back(i); - continue; - } - Uses.push_back(i); - if (Defs.size() < Uses.size()) { - report("No tied def for tied use", &MO, i); - break; - } - if (i >= MCID.getNumOperands()) - continue; - int DefIdx = MCID.getOperandConstraint(i, MCOI::TIED_TO); - if (unsigned(DefIdx) != Defs[Uses.size() - 1]) { - report(" def doesn't match MCInstrDesc", &MO, i); - *OS << "Descriptor says tied def should be operand " << DefIdx << ".\n"; - } - } - if (Defs.size() > Uses.size()) { - unsigned i = Defs[Uses.size() - 1]; - report("No tied use for tied def", &MI->getOperand(i), i); - } -} - void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { const MCInstrDesc &MCID = MI->getDesc(); if (MI->getNumOperands() < MCID.getNumOperands()) { report("Too few operands", MI); *OS << MCID.getNumOperands() << " operands expected, but " - << MI->getNumExplicitOperands() << " given.\n"; + << MI->getNumOperands() << " given.\n"; } // Check the tied operands. if (MI->isInlineAsm()) verifyInlineAsm(MI); - else - verifyTiedOperands(MI); // Check the MachineMemOperands for basic consistency. for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), @@ -839,16 +833,19 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { if (MO->isReg() && !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { if (MO->isDef() && !MCOI.isOptionalDef()) - report("Explicit operand marked as def", MO, MONum); + report("Explicit operand marked as def", MO, MONum); if (MO->isImplicit()) report("Explicit operand marked as implicit", MO, MONum); } - if (MCID.getOperandConstraint(MONum, MCOI::TIED_TO) != -1) { + int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO); + if (TiedTo != -1) { if (!MO->isReg()) report("Tied use must be a register", MO, MONum); else if (!MO->isTied()) report("Operand should be tied", MO, MONum); + else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum)) + report("Tied def doesn't match MCInstrDesc", MO, MONum); } else if (MO->isReg() && MO->isTied()) report("Explicit operand should not be tied", MO, MONum); } else { @@ -865,6 +862,28 @@ MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { if (MRI->tracksLiveness() && !MI->isDebugValue()) checkLiveness(MO, MONum); + // Verify the consistency of tied operands. + if (MO->isTied()) { + unsigned OtherIdx = MI->findTiedOperandIdx(MONum); + const MachineOperand &OtherMO = MI->getOperand(OtherIdx); + if (!OtherMO.isReg()) + report("Must be tied to a register", MO, MONum); + if (!OtherMO.isTied()) + report("Missing tie flags on tied operand", MO, MONum); + if (MI->findTiedOperandIdx(OtherIdx) != MONum) + report("Inconsistent tie links", MO, MONum); + if (MONum < MCID.getNumDefs()) { + if (OtherIdx < MCID.getNumOperands()) { + if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO)) + report("Explicit def tied to explicit use without tie constraint", + MO, MONum); + } else { + if (!OtherMO.isImplicit()) + report("Explicit def should be tied to implicit use", MO, MONum); + } + } + } + // Verify two-address constraints after leaving SSA form. unsigned DefIdx; if (!MRI->isSSA() && MO->isUse() && @@ -989,16 +1008,16 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { // Check the cached regunit intervals. if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) { for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { - if (const LiveInterval *LI = LiveInts->getCachedRegUnit(*Units)) { - LiveRangeQuery LRQ(*LI, UseIdx); + if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units)) { + LiveQueryResult LRQ = LR->Query(UseIdx); if (!LRQ.valueIn()) { - report("No live range at use", MO, MONum); + report("No live segment at use", MO, MONum); *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI) - << ' ' << *LI << '\n'; + << ' ' << *LR << '\n'; } if (MO->isKill() && !LRQ.isKill()) { report("Live range continues after kill flag", MO, MONum); - *OS << PrintRegUnit(*Units, TRI) << ' ' << *LI << '\n'; + *OS << PrintRegUnit(*Units, TRI) << ' ' << *LR << '\n'; } } } @@ -1008,9 +1027,9 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { if (LiveInts->hasInterval(Reg)) { // This is a virtual register interval. const LiveInterval &LI = LiveInts->getInterval(Reg); - LiveRangeQuery LRQ(LI, UseIdx); + LiveQueryResult LRQ = LI.Query(UseIdx); if (!LRQ.valueIn()) { - report("No live range at use", MO, MONum); + report("No live segment at use", MO, MONum); *OS << UseIdx << " is not live in " << LI << '\n'; } // Check for extra kill flags. @@ -1059,7 +1078,7 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { 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. + // Check LiveInts for a live segment, but only for virtual registers. if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) && !LiveInts->isNotInMIMap(MI)) { SlotIndex DefIdx = LiveInts->getInstructionIndex(MI); @@ -1074,9 +1093,17 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { << DefIdx << " in " << LI << '\n'; } } else { - report("No live range at def", MO, MONum); + report("No live segment at def", MO, MONum); *OS << DefIdx << " is not live in " << LI << '\n'; } + // Check that, if the dead def flag is present, LiveInts agree. + if (MO->isDead()) { + LiveQueryResult LRQ = LI.Query(DefIdx); + if (!LRQ.isDeadDef()) { + report("Live range continues after dead def flag", MO, MONum); + *OS << "Live range: " << LI << '\n'; + } + } } else { report("Virtual register has no Live interval", MO, MONum); } @@ -1323,25 +1350,26 @@ void MachineVerifier::verifyLiveIntervals() { // Verify all the cached regunit intervals. for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) - if (const LiveInterval *LI = LiveInts->getCachedRegUnit(i)) - verifyLiveInterval(*LI); + if (const LiveRange *LR = LiveInts->getCachedRegUnit(i)) + verifyLiveRange(*LR, i); } -void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI, - VNInfo *VNI) { +void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR, + const VNInfo *VNI, + unsigned Reg) { if (VNI->isUnused()) return; - const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def); + const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def); if (!DefVNI) { - report("Valno not live at def and not marked unused", MF, LI); + report("Valno not live at def and not marked unused", MF, LR); *OS << "Valno #" << VNI->id << '\n'; return; } if (DefVNI != VNI) { - report("Live range at def has different valno", MF, LI); + report("Live segment at def has different valno", MF, LR); *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << " where valno #" << DefVNI->id << " is live\n"; return; @@ -1349,15 +1377,15 @@ void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI, const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); if (!MBB) { - report("Invalid definition index", MF, LI); + report("Invalid definition index", MF, LR); *OS << "Valno #" << VNI->id << " is defined at " << VNI->def - << " in " << LI << '\n'; + << " in " << LR << '\n'; return; } if (VNI->isPHIDef()) { if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { - report("PHIDef value is not defined at MBB start", MBB, LI); + report("PHIDef value is not defined at MBB start", MBB, LR); *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << ", not at the beginning of BB#" << MBB->getNumber() << '\n'; } @@ -1367,161 +1395,154 @@ void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI, // Non-PHI def. const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); if (!MI) { - report("No instruction at def index", MBB, LI); + report("No instruction at def index", MBB, LR); *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; return; } - 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->hasRegUnit(MOI->getReg(), LI.reg)) + if (Reg != 0) { + bool hasDef = false; + bool isEarlyClobber = false; + for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { + if (!MOI->isReg() || !MOI->isDef()) continue; + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + if (MOI->getReg() != Reg) + continue; + } else { + if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || + !TRI->hasRegUnit(MOI->getReg(), Reg)) + continue; + } + hasDef = true; + if (MOI->isEarlyClobber()) + isEarlyClobber = true; } - hasDef = true; - if (MOI->isEarlyClobber()) - isEarlyClobber = true; - } - if (!hasDef) { - report("Defining instruction does not modify register", MI); - *OS << "Valno #" << VNI->id << " in " << LI << '\n'; - } + if (!hasDef) { + report("Defining instruction does not modify register", MI); + *OS << "Valno #" << VNI->id << " in " << LR << '\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", MBB, LI); + // 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", MBB, LR); + *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; + } + } else if (!VNI->def.isRegister()) { + report("Non-PHI, non-early clobber def must be at a register slot", + MBB, LR); *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; } - } else if (!VNI->def.isRegister()) { - report("Non-PHI, non-early clobber def must be at a register slot", - MBB, LI); - *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; } } -void -MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI, - LiveInterval::const_iterator 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, LI); - *OS << *I << " has a bad valno\n"; +void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR, + const LiveRange::const_iterator I, + unsigned Reg) { + const LiveRange::Segment &S = *I; + const VNInfo *VNI = S.valno; + assert(VNI && "Live segment has no valno"); + + if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) { + report("Foreign valno in live segment", MF, LR); + *OS << S << " has a bad valno\n"; } if (VNI->isUnused()) { - report("Live range valno is marked unused", MF, LI); - *OS << *I << '\n'; + report("Live segment valno is marked unused", MF, LR); + *OS << S << '\n'; } - const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start); + const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start); if (!MBB) { - report("Bad start of live segment, no basic block", MF, LI); - *OS << *I << '\n'; + report("Bad start of live segment, no basic block", MF, LR); + *OS << S << '\n'; return; } 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, LI); - *OS << *I << '\n'; + if (S.start != MBBStartIdx && S.start != VNI->def) { + report("Live segment must begin at MBB entry or valno def", MBB, LR); + *OS << S << '\n'; } const MachineBasicBlock *EndMBB = - LiveInts->getMBBFromIndex(I->end.getPrevSlot()); + LiveInts->getMBBFromIndex(S.end.getPrevSlot()); if (!EndMBB) { - report("Bad end of live segment, no basic block", MF, LI); - *OS << *I << '\n'; + report("Bad end of live segment, no basic block", MF, LR); + *OS << S << '\n'; return; } // No more checks for live-out segments. - if (I->end == LiveInts->getMBBEndIdx(EndMBB)) + if (S.end == LiveInts->getMBBEndIdx(EndMBB)) return; // RegUnit intervals are allowed dead phis. - if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && VNI->isPHIDef() && - I->start == VNI->def && I->end == VNI->def.getDeadSlot()) + if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() && + S.start == VNI->def && S.end == VNI->def.getDeadSlot()) return; // The live segment is ending inside EndMBB const MachineInstr *MI = - LiveInts->getInstructionFromIndex(I->end.getPrevSlot()); + LiveInts->getInstructionFromIndex(S.end.getPrevSlot()); if (!MI) { - report("Live segment doesn't end at a valid instruction", EndMBB, LI); - *OS << *I << '\n'; + report("Live segment doesn't end at a valid instruction", EndMBB, LR); + *OS << S << '\n'; return; } // The block slot must refer to a basic block boundary. - if (I->end.isBlock()) { - report("Live segment ends at B slot of an instruction", EndMBB, LI); - *OS << *I << '\n'; + if (S.end.isBlock()) { + report("Live segment ends at B slot of an instruction", EndMBB, LR); + *OS << S << '\n'; } - if (I->end.isDead()) { + if (S.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", EndMBB, LI); - *OS << *I << '\n'; + if (!SlotIndex::isSameInstr(S.start, S.end)) { + report("Live segment ending at dead slot spans instructions", EndMBB, LR); + *OS << S << '\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 == LI.end() || (I+1)->start != I->end) { + if (S.end.isEarlyClobber()) { + if (I+1 == LR.end() || (I+1)->start != S.end) { report("Live segment ending at early clobber slot must be " - "redefined by an EC def in the same instruction", EndMBB, LI); - *OS << *I << '\n'; + "redefined by an EC def in the same instruction", EndMBB, LR); + *OS << S << '\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 + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + // A live segment 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) + if (!MOI->isReg() || MOI->getReg() != 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 (!S.end.isDead()) { if (!hasRead) { - report("Instruction ending live range doesn't read the register", MI); - *OS << *I << " in " << LI << '\n'; + report("Instruction ending live segment doesn't read the register", MI); + *OS << S << " in " << LR << '\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()) { + // Is this live segment the beginning of a non-PHIDef VN? + if (S.start == VNI->def && !VNI->isPHIDef()) { // Not live-in to any blocks. if (MBB == EndMBB) return; @@ -1529,9 +1550,9 @@ MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI, ++MFI; } for (;;) { - assert(LiveInts->isLiveInToMBB(LI, MFI)); + assert(LiveInts->isLiveInToMBB(LR, MFI)); // We don't know how to track physregs into a landing pad. - if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && + if (!TargetRegisterInfo::isVirtualRegister(Reg) && MFI->isLandingPad()) { if (&*MFI == EndMBB) break; @@ -1547,11 +1568,11 @@ MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI, 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); + const VNInfo *PVNI = LR.getVNInfoBefore(PEnd); // All predecessors must have a live-out value. if (!PVNI) { - report("Register not marked live out of predecessor", *PI, LI); + report("Register not marked live out of predecessor", *PI, LR); *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber() << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before " << PEnd << '\n'; @@ -1560,7 +1581,7 @@ MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI, // Only PHI-defs can take different predecessor values. if (!IsPHI && PVNI != VNI) { - report("Different value live out of predecessor", *PI, LI); + report("Different value live out of predecessor", *PI, LR); *OS << "Valno #" << PVNI->id << " live out of BB#" << (*PI)->getNumber() << '@' << PEnd << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber() @@ -1573,13 +1594,17 @@ MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI, } } -void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { - for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); - I!=E; ++I) - verifyLiveIntervalValue(LI, *I); +void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg) { + for (LiveRange::const_vni_iterator I = LR.vni_begin(), E = LR.vni_end(); + I != E; ++I) + verifyLiveRangeValue(LR, *I, Reg); + + for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I) + verifyLiveRangeSegment(LR, I, Reg); +} - for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) - verifyLiveIntervalSegment(LI, I); +void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { + verifyLiveRange(LI, LI.reg); // Check the LI only has one connected component. if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { @@ -1598,3 +1623,130 @@ void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { } } } + +namespace { + // FrameSetup and FrameDestroy can have zero adjustment, so using a single + // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the + // value is zero. + // We use a bool plus an integer to capture the stack state. + struct StackStateOfBB { + StackStateOfBB() : EntryValue(0), ExitValue(0), EntryIsSetup(false), + ExitIsSetup(false) { } + StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) : + EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup), + ExitIsSetup(ExitSetup) { } + // Can be negative, which means we are setting up a frame. + int EntryValue; + int ExitValue; + bool EntryIsSetup; + bool ExitIsSetup; + }; +} + +/// Make sure on every path through the CFG, a FrameSetup is always followed +/// by a FrameDestroy , stack adjustments are identical on all +/// CFG edges to a merge point, and frame is destroyed at end of a return block. +void MachineVerifier::verifyStackFrame() { + int FrameSetupOpcode = TII->getCallFrameSetupOpcode(); + int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode(); + + SmallVector SPState; + SPState.resize(MF->getNumBlockIDs()); + SmallPtrSet Reachable; + + // Visit the MBBs in DFS order. + for (df_ext_iterator > + DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable); + DFI != DFE; ++DFI) { + const MachineBasicBlock *MBB = *DFI; + + StackStateOfBB BBState; + // Check the exit state of the DFS stack predecessor. + if (DFI.getPathLength() >= 2) { + const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); + assert(Reachable.count(StackPred) && + "DFS stack predecessor is already visited.\n"); + BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue; + BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup; + BBState.ExitValue = BBState.EntryValue; + BBState.ExitIsSetup = BBState.EntryIsSetup; + } + + // Update stack state by checking contents of MBB. + for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I) { + if (I->getOpcode() == FrameSetupOpcode) { + // The first operand of a FrameOpcode should be i32. + int Size = I->getOperand(0).getImm(); + assert(Size >= 0 && + "Value should be non-negative in FrameSetup and FrameDestroy.\n"); + + if (BBState.ExitIsSetup) + report("FrameSetup is after another FrameSetup", I); + BBState.ExitValue -= Size; + BBState.ExitIsSetup = true; + } + + if (I->getOpcode() == FrameDestroyOpcode) { + // The first operand of a FrameOpcode should be i32. + int Size = I->getOperand(0).getImm(); + assert(Size >= 0 && + "Value should be non-negative in FrameSetup and FrameDestroy.\n"); + + if (!BBState.ExitIsSetup) + report("FrameDestroy is not after a FrameSetup", I); + int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue : + BBState.ExitValue; + if (BBState.ExitIsSetup && AbsSPAdj != Size) { + report("FrameDestroy is after FrameSetup ", I); + *OS << "FrameDestroy <" << Size << "> is after FrameSetup <" + << AbsSPAdj << ">.\n"; + } + BBState.ExitValue += Size; + BBState.ExitIsSetup = false; + } + } + SPState[MBB->getNumber()] = BBState; + + // Make sure the exit state of any predecessor is consistent with the entry + // state. + for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), + E = MBB->pred_end(); I != E; ++I) { + if (Reachable.count(*I) && + (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue || + SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) { + report("The exit stack state of a predecessor is inconsistent.", MBB); + *OS << "Predecessor BB#" << (*I)->getNumber() << " has exit state (" + << SPState[(*I)->getNumber()].ExitValue << ", " + << SPState[(*I)->getNumber()].ExitIsSetup + << "), while BB#" << MBB->getNumber() << " has entry state (" + << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n"; + } + } + + // Make sure the entry state of any successor is consistent with the exit + // state. + for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), + E = MBB->succ_end(); I != E; ++I) { + if (Reachable.count(*I) && + (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue || + SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) { + report("The entry stack state of a successor is inconsistent.", MBB); + *OS << "Successor BB#" << (*I)->getNumber() << " has entry state (" + << SPState[(*I)->getNumber()].EntryValue << ", " + << SPState[(*I)->getNumber()].EntryIsSetup + << "), while BB#" << MBB->getNumber() << " has exit state (" + << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n"; + } + } + + // Make sure a basic block with return ends with zero stack adjustment. + if (!MBB->empty() && MBB->back().isReturn()) { + if (BBState.ExitIsSetup) + report("A return block ends with a FrameSetup.", MBB); + if (BBState.ExitValue) + report("A return block ends with a nonzero stack adjustment.", MBB); + } + } +}