MachineVerifier.cpp revision 245431
1212904Sdim//===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// Pass to verify generated machine code. The following is checked: 11193323Sed// 12193323Sed// Operand counts: All explicit operands must be present. 13193323Sed// 14193323Sed// Register classes: All physical and virtual register operands must be 15193323Sed// compatible with the register class required by the instruction descriptor. 16193323Sed// 17193323Sed// Register live intervals: Registers must be defined only once, and must be 18193323Sed// defined before use. 19193323Sed// 20193323Sed// The machine code verifier is enabled from LLVMTargetMachine.cpp with the 21193323Sed// command-line option -verify-machineinstrs, or by defining the environment 22193323Sed// variable LLVM_VERIFY_MACHINEINSTRS to the name of a file that will receive 23193323Sed// the verifier errors. 24193323Sed//===----------------------------------------------------------------------===// 25193323Sed 26245431Sdim#include "llvm/BasicBlock.h" 27245431Sdim#include "llvm/InlineAsm.h" 28223017Sdim#include "llvm/Instructions.h" 29212904Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 30193323Sed#include "llvm/CodeGen/LiveVariables.h" 31218893Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 32235633Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 33193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 34198090Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 35198090Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 36193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 37193323Sed#include "llvm/CodeGen/Passes.h" 38223017Sdim#include "llvm/MC/MCAsmInfo.h" 39193323Sed#include "llvm/Target/TargetMachine.h" 40193323Sed#include "llvm/Target/TargetRegisterInfo.h" 41193323Sed#include "llvm/Target/TargetInstrInfo.h" 42198090Srdivacky#include "llvm/ADT/DenseSet.h" 43198090Srdivacky#include "llvm/ADT/SetOperations.h" 44198090Srdivacky#include "llvm/ADT/SmallVector.h" 45193323Sed#include "llvm/Support/Debug.h" 46198090Srdivacky#include "llvm/Support/ErrorHandling.h" 47198090Srdivacky#include "llvm/Support/raw_ostream.h" 48193323Sedusing namespace llvm; 49193323Sed 50193323Sednamespace { 51199511Srdivacky struct MachineVerifier { 52193323Sed 53218893Sdim MachineVerifier(Pass *pass, const char *b) : 54199511Srdivacky PASS(pass), 55218893Sdim Banner(b), 56193323Sed OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) 57199511Srdivacky {} 58193323Sed 59193323Sed bool runOnMachineFunction(MachineFunction &MF); 60193323Sed 61199511Srdivacky Pass *const PASS; 62218893Sdim const char *Banner; 63193323Sed const char *const OutFileName; 64198090Srdivacky raw_ostream *OS; 65193323Sed const MachineFunction *MF; 66193323Sed const TargetMachine *TM; 67224145Sdim const TargetInstrInfo *TII; 68193323Sed const TargetRegisterInfo *TRI; 69193323Sed const MachineRegisterInfo *MRI; 70193323Sed 71193323Sed unsigned foundErrors; 72193323Sed 73193323Sed typedef SmallVector<unsigned, 16> RegVector; 74235633Sdim typedef SmallVector<const uint32_t*, 4> RegMaskVector; 75193323Sed typedef DenseSet<unsigned> RegSet; 76193323Sed typedef DenseMap<unsigned, const MachineInstr*> RegMap; 77245431Sdim typedef SmallPtrSet<const MachineBasicBlock*, 8> BlockSet; 78193323Sed 79226890Sdim const MachineInstr *FirstTerminator; 80245431Sdim BlockSet FunctionBlocks; 81226890Sdim 82193323Sed BitVector regsReserved; 83193323Sed RegSet regsLive; 84198090Srdivacky RegVector regsDefined, regsDead, regsKilled; 85235633Sdim RegMaskVector regMasks; 86198090Srdivacky RegSet regsLiveInButUnused; 87193323Sed 88218893Sdim SlotIndex lastIndex; 89218893Sdim 90193323Sed // Add Reg and any sub-registers to RV 91193323Sed void addRegWithSubRegs(RegVector &RV, unsigned Reg) { 92193323Sed RV.push_back(Reg); 93193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) 94245431Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 95245431Sdim RV.push_back(*SubRegs); 96193323Sed } 97193323Sed 98193323Sed struct BBInfo { 99193323Sed // Is this MBB reachable from the MF entry point? 100193323Sed bool reachable; 101193323Sed 102193323Sed // Vregs that must be live in because they are used without being 103193323Sed // defined. Map value is the user. 104193323Sed RegMap vregsLiveIn; 105193323Sed 106193323Sed // Regs killed in MBB. They may be defined again, and will then be in both 107193323Sed // regsKilled and regsLiveOut. 108193323Sed RegSet regsKilled; 109193323Sed 110193323Sed // Regs defined in MBB and live out. Note that vregs passing through may 111193323Sed // be live out without being mentioned here. 112193323Sed RegSet regsLiveOut; 113193323Sed 114193323Sed // Vregs that pass through MBB untouched. This set is disjoint from 115193323Sed // regsKilled and regsLiveOut. 116193323Sed RegSet vregsPassed; 117193323Sed 118199511Srdivacky // Vregs that must pass through MBB because they are needed by a successor 119199511Srdivacky // block. This set is disjoint from regsLiveOut. 120199511Srdivacky RegSet vregsRequired; 121199511Srdivacky 122245431Sdim // Set versions of block's predecessor and successor lists. 123245431Sdim BlockSet Preds, Succs; 124245431Sdim 125193323Sed BBInfo() : reachable(false) {} 126193323Sed 127193323Sed // Add register to vregsPassed if it belongs there. Return true if 128193323Sed // anything changed. 129193323Sed bool addPassed(unsigned Reg) { 130193323Sed if (!TargetRegisterInfo::isVirtualRegister(Reg)) 131193323Sed return false; 132193323Sed if (regsKilled.count(Reg) || regsLiveOut.count(Reg)) 133193323Sed return false; 134193323Sed return vregsPassed.insert(Reg).second; 135193323Sed } 136193323Sed 137193323Sed // Same for a full set. 138193323Sed bool addPassed(const RegSet &RS) { 139193323Sed bool changed = false; 140193323Sed for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 141193323Sed if (addPassed(*I)) 142193323Sed changed = true; 143193323Sed return changed; 144193323Sed } 145193323Sed 146199511Srdivacky // Add register to vregsRequired if it belongs there. Return true if 147199511Srdivacky // anything changed. 148199511Srdivacky bool addRequired(unsigned Reg) { 149199511Srdivacky if (!TargetRegisterInfo::isVirtualRegister(Reg)) 150199511Srdivacky return false; 151199511Srdivacky if (regsLiveOut.count(Reg)) 152199511Srdivacky return false; 153199511Srdivacky return vregsRequired.insert(Reg).second; 154199511Srdivacky } 155199511Srdivacky 156199511Srdivacky // Same for a full set. 157199511Srdivacky bool addRequired(const RegSet &RS) { 158199511Srdivacky bool changed = false; 159199511Srdivacky for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 160199511Srdivacky if (addRequired(*I)) 161199511Srdivacky changed = true; 162199511Srdivacky return changed; 163199511Srdivacky } 164199511Srdivacky 165199511Srdivacky // Same for a full map. 166199511Srdivacky bool addRequired(const RegMap &RM) { 167199511Srdivacky bool changed = false; 168199511Srdivacky for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I) 169199511Srdivacky if (addRequired(I->first)) 170199511Srdivacky changed = true; 171199511Srdivacky return changed; 172199511Srdivacky } 173199511Srdivacky 174193323Sed // Live-out registers are either in regsLiveOut or vregsPassed. 175193323Sed bool isLiveOut(unsigned Reg) const { 176193323Sed return regsLiveOut.count(Reg) || vregsPassed.count(Reg); 177193323Sed } 178193323Sed }; 179193323Sed 180193323Sed // Extra register info per MBB. 181193323Sed DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap; 182193323Sed 183193323Sed bool isReserved(unsigned Reg) { 184198090Srdivacky return Reg < regsReserved.size() && regsReserved.test(Reg); 185193323Sed } 186193323Sed 187235633Sdim bool isAllocatable(unsigned Reg) { 188245431Sdim return Reg < TRI->getNumRegs() && MRI->isAllocatable(Reg); 189235633Sdim } 190235633Sdim 191199511Srdivacky // Analysis information if available 192199511Srdivacky LiveVariables *LiveVars; 193218893Sdim LiveIntervals *LiveInts; 194218893Sdim LiveStacks *LiveStks; 195218893Sdim SlotIndexes *Indexes; 196199511Srdivacky 197193323Sed void visitMachineFunctionBefore(); 198193323Sed void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); 199245431Sdim void visitMachineBundleBefore(const MachineInstr *MI); 200193323Sed void visitMachineInstrBefore(const MachineInstr *MI); 201193323Sed void visitMachineOperand(const MachineOperand *MO, unsigned MONum); 202193323Sed void visitMachineInstrAfter(const MachineInstr *MI); 203245431Sdim void visitMachineBundleAfter(const MachineInstr *MI); 204193323Sed void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB); 205193323Sed void visitMachineFunctionAfter(); 206193323Sed 207193323Sed void report(const char *msg, const MachineFunction *MF); 208193323Sed void report(const char *msg, const MachineBasicBlock *MBB); 209193323Sed void report(const char *msg, const MachineInstr *MI); 210193323Sed void report(const char *msg, const MachineOperand *MO, unsigned MONum); 211245431Sdim void report(const char *msg, const MachineFunction *MF, 212245431Sdim const LiveInterval &LI); 213245431Sdim void report(const char *msg, const MachineBasicBlock *MBB, 214245431Sdim const LiveInterval &LI); 215193323Sed 216245431Sdim void verifyInlineAsm(const MachineInstr *MI); 217245431Sdim 218235633Sdim void checkLiveness(const MachineOperand *MO, unsigned MONum); 219193323Sed void markReachable(const MachineBasicBlock *MBB); 220202375Srdivacky void calcRegsPassed(); 221193323Sed void checkPHIOps(const MachineBasicBlock *MBB); 222199511Srdivacky 223199511Srdivacky void calcRegsRequired(); 224199511Srdivacky void verifyLiveVariables(); 225212904Sdim void verifyLiveIntervals(); 226245431Sdim void verifyLiveInterval(const LiveInterval&); 227245431Sdim void verifyLiveIntervalValue(const LiveInterval&, VNInfo*); 228245431Sdim void verifyLiveIntervalSegment(const LiveInterval&, 229245431Sdim LiveInterval::const_iterator); 230193323Sed }; 231199511Srdivacky 232199511Srdivacky struct MachineVerifierPass : public MachineFunctionPass { 233199511Srdivacky static char ID; // Pass ID, replacement for typeid 234218893Sdim const char *const Banner; 235199511Srdivacky 236218893Sdim MachineVerifierPass(const char *b = 0) 237218893Sdim : MachineFunctionPass(ID), Banner(b) { 238218893Sdim initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry()); 239218893Sdim } 240199511Srdivacky 241199511Srdivacky void getAnalysisUsage(AnalysisUsage &AU) const { 242199511Srdivacky AU.setPreservesAll(); 243199511Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 244199511Srdivacky } 245199511Srdivacky 246199511Srdivacky bool runOnMachineFunction(MachineFunction &MF) { 247218893Sdim MF.verify(this, Banner); 248199511Srdivacky return false; 249199511Srdivacky } 250199511Srdivacky }; 251199511Srdivacky 252193323Sed} 253193323Sed 254199511Srdivackychar MachineVerifierPass::ID = 0; 255212904SdimINITIALIZE_PASS(MachineVerifierPass, "machineverifier", 256218893Sdim "Verify generated machine code", false, false) 257193323Sed 258218893SdimFunctionPass *llvm::createMachineVerifierPass(const char *Banner) { 259218893Sdim return new MachineVerifierPass(Banner); 260193323Sed} 261193323Sed 262218893Sdimvoid MachineFunction::verify(Pass *p, const char *Banner) const { 263218893Sdim MachineVerifier(p, Banner) 264218893Sdim .runOnMachineFunction(const_cast<MachineFunction&>(*this)); 265199481Srdivacky} 266199481Srdivacky 267198090Srdivackybool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { 268198090Srdivacky raw_ostream *OutFile = 0; 269193323Sed if (OutFileName) { 270198090Srdivacky std::string ErrorInfo; 271198090Srdivacky OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, 272198090Srdivacky raw_fd_ostream::F_Append); 273198090Srdivacky if (!ErrorInfo.empty()) { 274198090Srdivacky errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n'; 275198090Srdivacky exit(1); 276198090Srdivacky } 277198090Srdivacky 278198090Srdivacky OS = OutFile; 279193323Sed } else { 280198090Srdivacky OS = &errs(); 281193323Sed } 282193323Sed 283193323Sed foundErrors = 0; 284193323Sed 285193323Sed this->MF = &MF; 286193323Sed TM = &MF.getTarget(); 287224145Sdim TII = TM->getInstrInfo(); 288193323Sed TRI = TM->getRegisterInfo(); 289193323Sed MRI = &MF.getRegInfo(); 290193323Sed 291212904Sdim LiveVars = NULL; 292212904Sdim LiveInts = NULL; 293218893Sdim LiveStks = NULL; 294218893Sdim Indexes = NULL; 295199511Srdivacky if (PASS) { 296212904Sdim LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>(); 297212904Sdim // We don't want to verify LiveVariables if LiveIntervals is available. 298212904Sdim if (!LiveInts) 299212904Sdim LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>(); 300218893Sdim LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>(); 301218893Sdim Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>(); 302199511Srdivacky } 303199511Srdivacky 304193323Sed visitMachineFunctionBefore(); 305193323Sed for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 306193323Sed MFI!=MFE; ++MFI) { 307193323Sed visitMachineBasicBlockBefore(MFI); 308245431Sdim // Keep track of the current bundle header. 309245431Sdim const MachineInstr *CurBundle = 0; 310235633Sdim for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), 311235633Sdim MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) { 312218893Sdim if (MBBI->getParent() != MFI) { 313218893Sdim report("Bad instruction parent pointer", MFI); 314218893Sdim *OS << "Instruction: " << *MBBI; 315218893Sdim continue; 316218893Sdim } 317245431Sdim // Is this a bundle header? 318245431Sdim if (!MBBI->isInsideBundle()) { 319245431Sdim if (CurBundle) 320245431Sdim visitMachineBundleAfter(CurBundle); 321245431Sdim CurBundle = MBBI; 322245431Sdim visitMachineBundleBefore(CurBundle); 323245431Sdim } else if (!CurBundle) 324245431Sdim report("No bundle header", MBBI); 325193323Sed visitMachineInstrBefore(MBBI); 326193323Sed for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) 327193323Sed visitMachineOperand(&MBBI->getOperand(I), I); 328193323Sed visitMachineInstrAfter(MBBI); 329193323Sed } 330245431Sdim if (CurBundle) 331245431Sdim visitMachineBundleAfter(CurBundle); 332193323Sed visitMachineBasicBlockAfter(MFI); 333193323Sed } 334193323Sed visitMachineFunctionAfter(); 335193323Sed 336198090Srdivacky if (OutFile) 337198090Srdivacky delete OutFile; 338198090Srdivacky else if (foundErrors) 339207618Srdivacky report_fatal_error("Found "+Twine(foundErrors)+" machine code errors."); 340193323Sed 341198090Srdivacky // Clean up. 342198090Srdivacky regsLive.clear(); 343198090Srdivacky regsDefined.clear(); 344198090Srdivacky regsDead.clear(); 345198090Srdivacky regsKilled.clear(); 346235633Sdim regMasks.clear(); 347198090Srdivacky regsLiveInButUnused.clear(); 348198090Srdivacky MBBInfoMap.clear(); 349193323Sed 350193323Sed return false; // no changes 351193323Sed} 352193323Sed 353198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineFunction *MF) { 354193323Sed assert(MF); 355198090Srdivacky *OS << '\n'; 356218893Sdim if (!foundErrors++) { 357218893Sdim if (Banner) 358218893Sdim *OS << "# " << Banner << '\n'; 359218893Sdim MF->print(*OS, Indexes); 360218893Sdim } 361193323Sed *OS << "*** Bad machine code: " << msg << " ***\n" 362245431Sdim << "- function: " << MF->getName() << "\n"; 363193323Sed} 364193323Sed 365198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { 366193323Sed assert(MBB); 367193323Sed report(msg, MBB->getParent()); 368245431Sdim *OS << "- basic block: BB#" << MBB->getNumber() 369245431Sdim << ' ' << MBB->getName() 370245431Sdim << " (" << (const void*)MBB << ')'; 371218893Sdim if (Indexes) 372218893Sdim *OS << " [" << Indexes->getMBBStartIdx(MBB) 373218893Sdim << ';' << Indexes->getMBBEndIdx(MBB) << ')'; 374218893Sdim *OS << '\n'; 375193323Sed} 376193323Sed 377198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineInstr *MI) { 378193323Sed assert(MI); 379193323Sed report(msg, MI->getParent()); 380193323Sed *OS << "- instruction: "; 381218893Sdim if (Indexes && Indexes->hasIndex(MI)) 382218893Sdim *OS << Indexes->getInstructionIndex(MI) << '\t'; 383198090Srdivacky MI->print(*OS, TM); 384193323Sed} 385193323Sed 386198090Srdivackyvoid MachineVerifier::report(const char *msg, 387198090Srdivacky const MachineOperand *MO, unsigned MONum) { 388193323Sed assert(MO); 389193323Sed report(msg, MO->getParent()); 390193323Sed *OS << "- operand " << MONum << ": "; 391193323Sed MO->print(*OS, TM); 392193323Sed *OS << "\n"; 393193323Sed} 394193323Sed 395245431Sdimvoid MachineVerifier::report(const char *msg, const MachineFunction *MF, 396245431Sdim const LiveInterval &LI) { 397245431Sdim report(msg, MF); 398245431Sdim *OS << "- interval: "; 399245431Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) 400245431Sdim *OS << PrintReg(LI.reg, TRI); 401245431Sdim else 402245431Sdim *OS << PrintRegUnit(LI.reg, TRI); 403245431Sdim *OS << ' ' << LI << '\n'; 404245431Sdim} 405245431Sdim 406245431Sdimvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, 407245431Sdim const LiveInterval &LI) { 408245431Sdim report(msg, MBB); 409245431Sdim *OS << "- interval: "; 410245431Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) 411245431Sdim *OS << PrintReg(LI.reg, TRI); 412245431Sdim else 413245431Sdim *OS << PrintRegUnit(LI.reg, TRI); 414245431Sdim *OS << ' ' << LI << '\n'; 415245431Sdim} 416245431Sdim 417198090Srdivackyvoid MachineVerifier::markReachable(const MachineBasicBlock *MBB) { 418193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 419193323Sed if (!MInfo.reachable) { 420193323Sed MInfo.reachable = true; 421193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 422193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) 423193323Sed markReachable(*SuI); 424193323Sed } 425193323Sed} 426193323Sed 427198090Srdivackyvoid MachineVerifier::visitMachineFunctionBefore() { 428218893Sdim lastIndex = SlotIndex(); 429245431Sdim regsReserved = MRI->getReservedRegs(); 430198090Srdivacky 431198090Srdivacky // A sub-register of a reserved register is also reserved 432198090Srdivacky for (int Reg = regsReserved.find_first(); Reg>=0; 433198090Srdivacky Reg = regsReserved.find_next(Reg)) { 434245431Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 435198090Srdivacky // FIXME: This should probably be: 436245431Sdim // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register"); 437245431Sdim regsReserved.set(*SubRegs); 438198090Srdivacky } 439198090Srdivacky } 440235633Sdim 441245431Sdim markReachable(&MF->front()); 442235633Sdim 443245431Sdim // Build a set of the basic blocks in the function. 444245431Sdim FunctionBlocks.clear(); 445245431Sdim for (MachineFunction::const_iterator 446245431Sdim I = MF->begin(), E = MF->end(); I != E; ++I) { 447245431Sdim FunctionBlocks.insert(I); 448245431Sdim BBInfo &MInfo = MBBInfoMap[I]; 449245431Sdim 450245431Sdim MInfo.Preds.insert(I->pred_begin(), I->pred_end()); 451245431Sdim if (MInfo.Preds.size() != I->pred_size()) 452245431Sdim report("MBB has duplicate entries in its predecessor list.", I); 453245431Sdim 454245431Sdim MInfo.Succs.insert(I->succ_begin(), I->succ_end()); 455245431Sdim if (MInfo.Succs.size() != I->succ_size()) 456245431Sdim report("MBB has duplicate entries in its successor list.", I); 457245431Sdim } 458193323Sed} 459193323Sed 460199481Srdivacky// Does iterator point to a and b as the first two elements? 461207618Srdivackystatic bool matchPair(MachineBasicBlock::const_succ_iterator i, 462207618Srdivacky const MachineBasicBlock *a, const MachineBasicBlock *b) { 463199481Srdivacky if (*i == a) 464199481Srdivacky return *++i == b; 465199481Srdivacky if (*i == b) 466199481Srdivacky return *++i == a; 467199481Srdivacky return false; 468199481Srdivacky} 469199481Srdivacky 470199481Srdivackyvoid 471199481SrdivackyMachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { 472226890Sdim FirstTerminator = 0; 473226890Sdim 474235633Sdim if (MRI->isSSA()) { 475235633Sdim // If this block has allocatable physical registers live-in, check that 476235633Sdim // it is an entry block or landing pad. 477235633Sdim for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 478235633Sdim LE = MBB->livein_end(); 479235633Sdim LI != LE; ++LI) { 480235633Sdim unsigned reg = *LI; 481235633Sdim if (isAllocatable(reg) && !MBB->isLandingPad() && 482235633Sdim MBB != MBB->getParent()->begin()) { 483235633Sdim report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB); 484235633Sdim } 485235633Sdim } 486235633Sdim } 487235633Sdim 488218893Sdim // Count the number of landing pad successors. 489218893Sdim SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs; 490218893Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 491218893Sdim E = MBB->succ_end(); I != E; ++I) { 492218893Sdim if ((*I)->isLandingPad()) 493218893Sdim LandingPadSuccs.insert(*I); 494245431Sdim if (!FunctionBlocks.count(*I)) 495245431Sdim report("MBB has successor that isn't part of the function.", MBB); 496245431Sdim if (!MBBInfoMap[*I].Preds.count(MBB)) { 497245431Sdim report("Inconsistent CFG", MBB); 498245431Sdim *OS << "MBB is not in the predecessor list of the successor BB#" 499245431Sdim << (*I)->getNumber() << ".\n"; 500245431Sdim } 501218893Sdim } 502223017Sdim 503245431Sdim // Check the predecessor list. 504245431Sdim for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 505245431Sdim E = MBB->pred_end(); I != E; ++I) { 506245431Sdim if (!FunctionBlocks.count(*I)) 507245431Sdim report("MBB has predecessor that isn't part of the function.", MBB); 508245431Sdim if (!MBBInfoMap[*I].Succs.count(MBB)) { 509245431Sdim report("Inconsistent CFG", MBB); 510245431Sdim *OS << "MBB is not in the successor list of the predecessor BB#" 511245431Sdim << (*I)->getNumber() << ".\n"; 512245431Sdim } 513245431Sdim } 514245431Sdim 515223017Sdim const MCAsmInfo *AsmInfo = TM->getMCAsmInfo(); 516223017Sdim const BasicBlock *BB = MBB->getBasicBlock(); 517223017Sdim if (LandingPadSuccs.size() > 1 && 518223017Sdim !(AsmInfo && 519223017Sdim AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj && 520223017Sdim BB && isa<SwitchInst>(BB->getTerminator()))) 521218893Sdim report("MBB has more than one landing pad successor", MBB); 522218893Sdim 523198090Srdivacky // Call AnalyzeBranch. If it succeeds, there several more conditions to check. 524198090Srdivacky MachineBasicBlock *TBB = 0, *FBB = 0; 525198090Srdivacky SmallVector<MachineOperand, 4> Cond; 526198090Srdivacky if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB), 527198090Srdivacky TBB, FBB, Cond)) { 528198090Srdivacky // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's 529198090Srdivacky // check whether its answers match up with reality. 530198090Srdivacky if (!TBB && !FBB) { 531198090Srdivacky // Block falls through to its successor. 532198090Srdivacky MachineFunction::const_iterator MBBI = MBB; 533198090Srdivacky ++MBBI; 534198090Srdivacky if (MBBI == MF->end()) { 535198090Srdivacky // It's possible that the block legitimately ends with a noreturn 536198090Srdivacky // call or an unreachable, in which case it won't actually fall 537198090Srdivacky // out the bottom of the function. 538218893Sdim } else if (MBB->succ_size() == LandingPadSuccs.size()) { 539198090Srdivacky // It's possible that the block legitimately ends with a noreturn 540198090Srdivacky // call or an unreachable, in which case it won't actuall fall 541198090Srdivacky // out of the block. 542218893Sdim } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 543198090Srdivacky report("MBB exits via unconditional fall-through but doesn't have " 544198090Srdivacky "exactly one CFG successor!", MBB); 545218893Sdim } else if (!MBB->isSuccessor(MBBI)) { 546198090Srdivacky report("MBB exits via unconditional fall-through but its successor " 547198090Srdivacky "differs from its CFG successor!", MBB); 548198090Srdivacky } 549245431Sdim if (!MBB->empty() && getBundleStart(&MBB->back())->isBarrier() && 550245431Sdim !TII->isPredicated(getBundleStart(&MBB->back()))) { 551198090Srdivacky report("MBB exits via unconditional fall-through but ends with a " 552198090Srdivacky "barrier instruction!", MBB); 553198090Srdivacky } 554198090Srdivacky if (!Cond.empty()) { 555198090Srdivacky report("MBB exits via unconditional fall-through but has a condition!", 556198090Srdivacky MBB); 557198090Srdivacky } 558198090Srdivacky } else if (TBB && !FBB && Cond.empty()) { 559198090Srdivacky // Block unconditionally branches somewhere. 560218893Sdim if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 561198090Srdivacky report("MBB exits via unconditional branch but doesn't have " 562198090Srdivacky "exactly one CFG successor!", MBB); 563218893Sdim } else if (!MBB->isSuccessor(TBB)) { 564198090Srdivacky report("MBB exits via unconditional branch but the CFG " 565198090Srdivacky "successor doesn't match the actual successor!", MBB); 566198090Srdivacky } 567198090Srdivacky if (MBB->empty()) { 568198090Srdivacky report("MBB exits via unconditional branch but doesn't contain " 569198090Srdivacky "any instructions!", MBB); 570245431Sdim } else if (!getBundleStart(&MBB->back())->isBarrier()) { 571198090Srdivacky report("MBB exits via unconditional branch but doesn't end with a " 572198090Srdivacky "barrier instruction!", MBB); 573245431Sdim } else if (!getBundleStart(&MBB->back())->isTerminator()) { 574198090Srdivacky report("MBB exits via unconditional branch but the branch isn't a " 575198090Srdivacky "terminator instruction!", MBB); 576198090Srdivacky } 577198090Srdivacky } else if (TBB && !FBB && !Cond.empty()) { 578198090Srdivacky // Block conditionally branches somewhere, otherwise falls through. 579198090Srdivacky MachineFunction::const_iterator MBBI = MBB; 580198090Srdivacky ++MBBI; 581198090Srdivacky if (MBBI == MF->end()) { 582198090Srdivacky report("MBB conditionally falls through out of function!", MBB); 583245431Sdim } if (MBB->succ_size() == 1) { 584245431Sdim // A conditional branch with only one successor is weird, but allowed. 585245431Sdim if (&*MBBI != TBB) 586245431Sdim report("MBB exits via conditional branch/fall-through but only has " 587245431Sdim "one CFG successor!", MBB); 588245431Sdim else if (TBB != *MBB->succ_begin()) 589245431Sdim report("MBB exits via conditional branch/fall-through but the CFG " 590245431Sdim "successor don't match the actual successor!", MBB); 591245431Sdim } else if (MBB->succ_size() != 2) { 592198090Srdivacky report("MBB exits via conditional branch/fall-through but doesn't have " 593198090Srdivacky "exactly two CFG successors!", MBB); 594199481Srdivacky } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) { 595198090Srdivacky report("MBB exits via conditional branch/fall-through but the CFG " 596198090Srdivacky "successors don't match the actual successors!", MBB); 597198090Srdivacky } 598198090Srdivacky if (MBB->empty()) { 599198090Srdivacky report("MBB exits via conditional branch/fall-through but doesn't " 600198090Srdivacky "contain any instructions!", MBB); 601245431Sdim } else if (getBundleStart(&MBB->back())->isBarrier()) { 602198090Srdivacky report("MBB exits via conditional branch/fall-through but ends with a " 603198090Srdivacky "barrier instruction!", MBB); 604245431Sdim } else if (!getBundleStart(&MBB->back())->isTerminator()) { 605198090Srdivacky report("MBB exits via conditional branch/fall-through but the branch " 606198090Srdivacky "isn't a terminator instruction!", MBB); 607198090Srdivacky } 608198090Srdivacky } else if (TBB && FBB) { 609198090Srdivacky // Block conditionally branches somewhere, otherwise branches 610198090Srdivacky // somewhere else. 611245431Sdim if (MBB->succ_size() == 1) { 612245431Sdim // A conditional branch with only one successor is weird, but allowed. 613245431Sdim if (FBB != TBB) 614245431Sdim report("MBB exits via conditional branch/branch through but only has " 615245431Sdim "one CFG successor!", MBB); 616245431Sdim else if (TBB != *MBB->succ_begin()) 617245431Sdim report("MBB exits via conditional branch/branch through but the CFG " 618245431Sdim "successor don't match the actual successor!", MBB); 619245431Sdim } else if (MBB->succ_size() != 2) { 620198090Srdivacky report("MBB exits via conditional branch/branch but doesn't have " 621198090Srdivacky "exactly two CFG successors!", MBB); 622199481Srdivacky } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) { 623198090Srdivacky report("MBB exits via conditional branch/branch but the CFG " 624198090Srdivacky "successors don't match the actual successors!", MBB); 625198090Srdivacky } 626198090Srdivacky if (MBB->empty()) { 627198090Srdivacky report("MBB exits via conditional branch/branch but doesn't " 628198090Srdivacky "contain any instructions!", MBB); 629245431Sdim } else if (!getBundleStart(&MBB->back())->isBarrier()) { 630198090Srdivacky report("MBB exits via conditional branch/branch but doesn't end with a " 631198090Srdivacky "barrier instruction!", MBB); 632245431Sdim } else if (!getBundleStart(&MBB->back())->isTerminator()) { 633198090Srdivacky report("MBB exits via conditional branch/branch but the branch " 634198090Srdivacky "isn't a terminator instruction!", MBB); 635198090Srdivacky } 636198090Srdivacky if (Cond.empty()) { 637198090Srdivacky report("MBB exits via conditinal branch/branch but there's no " 638198090Srdivacky "condition!", MBB); 639198090Srdivacky } 640198090Srdivacky } else { 641198090Srdivacky report("AnalyzeBranch returned invalid data!", MBB); 642198090Srdivacky } 643198090Srdivacky } 644198090Srdivacky 645193323Sed regsLive.clear(); 646207618Srdivacky for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 647193323Sed E = MBB->livein_end(); I != E; ++I) { 648193323Sed if (!TargetRegisterInfo::isPhysicalRegister(*I)) { 649193323Sed report("MBB live-in list contains non-physical register", MBB); 650193323Sed continue; 651193323Sed } 652193323Sed regsLive.insert(*I); 653245431Sdim for (MCSubRegIterator SubRegs(*I, TRI); SubRegs.isValid(); ++SubRegs) 654245431Sdim regsLive.insert(*SubRegs); 655193323Sed } 656198090Srdivacky regsLiveInButUnused = regsLive; 657198090Srdivacky 658198090Srdivacky const MachineFrameInfo *MFI = MF->getFrameInfo(); 659198090Srdivacky assert(MFI && "Function has no frame info"); 660198090Srdivacky BitVector PR = MFI->getPristineRegs(MBB); 661198090Srdivacky for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { 662198090Srdivacky regsLive.insert(I); 663245431Sdim for (MCSubRegIterator SubRegs(I, TRI); SubRegs.isValid(); ++SubRegs) 664245431Sdim regsLive.insert(*SubRegs); 665198090Srdivacky } 666198090Srdivacky 667193323Sed regsKilled.clear(); 668193323Sed regsDefined.clear(); 669218893Sdim 670218893Sdim if (Indexes) 671218893Sdim lastIndex = Indexes->getMBBStartIdx(MBB); 672193323Sed} 673193323Sed 674245431Sdim// This function gets called for all bundle headers, including normal 675245431Sdim// stand-alone unbundled instructions. 676245431Sdimvoid MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) { 677245431Sdim if (Indexes && Indexes->hasIndex(MI)) { 678245431Sdim SlotIndex idx = Indexes->getInstructionIndex(MI); 679245431Sdim if (!(idx > lastIndex)) { 680245431Sdim report("Instruction index out of order", MI); 681245431Sdim *OS << "Last instruction was at " << lastIndex << '\n'; 682245431Sdim } 683245431Sdim lastIndex = idx; 684245431Sdim } 685245431Sdim 686245431Sdim // Ensure non-terminators don't follow terminators. 687245431Sdim // Ignore predicated terminators formed by if conversion. 688245431Sdim // FIXME: If conversion shouldn't need to violate this rule. 689245431Sdim if (MI->isTerminator() && !TII->isPredicated(MI)) { 690245431Sdim if (!FirstTerminator) 691245431Sdim FirstTerminator = MI; 692245431Sdim } else if (FirstTerminator) { 693245431Sdim report("Non-terminator instruction after the first terminator", MI); 694245431Sdim *OS << "First terminator was:\t" << *FirstTerminator; 695245431Sdim } 696245431Sdim} 697245431Sdim 698245431Sdim// The operands on an INLINEASM instruction must follow a template. 699245431Sdim// Verify that the flag operands make sense. 700245431Sdimvoid MachineVerifier::verifyInlineAsm(const MachineInstr *MI) { 701245431Sdim // The first two operands on INLINEASM are the asm string and global flags. 702245431Sdim if (MI->getNumOperands() < 2) { 703245431Sdim report("Too few operands on inline asm", MI); 704245431Sdim return; 705245431Sdim } 706245431Sdim if (!MI->getOperand(0).isSymbol()) 707245431Sdim report("Asm string must be an external symbol", MI); 708245431Sdim if (!MI->getOperand(1).isImm()) 709245431Sdim report("Asm flags must be an immediate", MI); 710245431Sdim // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2, 711245431Sdim // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16. 712245431Sdim if (!isUInt<5>(MI->getOperand(1).getImm())) 713245431Sdim report("Unknown asm flags", &MI->getOperand(1), 1); 714245431Sdim 715245431Sdim assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed"); 716245431Sdim 717245431Sdim unsigned OpNo = InlineAsm::MIOp_FirstOperand; 718245431Sdim unsigned NumOps; 719245431Sdim for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) { 720245431Sdim const MachineOperand &MO = MI->getOperand(OpNo); 721245431Sdim // There may be implicit ops after the fixed operands. 722245431Sdim if (!MO.isImm()) 723245431Sdim break; 724245431Sdim NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm()); 725245431Sdim } 726245431Sdim 727245431Sdim if (OpNo > MI->getNumOperands()) 728245431Sdim report("Missing operands in last group", MI); 729245431Sdim 730245431Sdim // An optional MDNode follows the groups. 731245431Sdim if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata()) 732245431Sdim ++OpNo; 733245431Sdim 734245431Sdim // All trailing operands must be implicit registers. 735245431Sdim for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) { 736245431Sdim const MachineOperand &MO = MI->getOperand(OpNo); 737245431Sdim if (!MO.isReg() || !MO.isImplicit()) 738245431Sdim report("Expected implicit register after groups", &MO, OpNo); 739245431Sdim } 740245431Sdim} 741245431Sdim 742198090Srdivackyvoid MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { 743224145Sdim const MCInstrDesc &MCID = MI->getDesc(); 744224145Sdim if (MI->getNumOperands() < MCID.getNumOperands()) { 745193323Sed report("Too few operands", MI); 746224145Sdim *OS << MCID.getNumOperands() << " operands expected, but " 747193323Sed << MI->getNumExplicitOperands() << " given.\n"; 748193323Sed } 749198090Srdivacky 750245431Sdim // Check the tied operands. 751245431Sdim if (MI->isInlineAsm()) 752245431Sdim verifyInlineAsm(MI); 753245431Sdim 754198090Srdivacky // Check the MachineMemOperands for basic consistency. 755198090Srdivacky for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 756198090Srdivacky E = MI->memoperands_end(); I != E; ++I) { 757235633Sdim if ((*I)->isLoad() && !MI->mayLoad()) 758198090Srdivacky report("Missing mayLoad flag", MI); 759235633Sdim if ((*I)->isStore() && !MI->mayStore()) 760198090Srdivacky report("Missing mayStore flag", MI); 761193323Sed } 762212904Sdim 763212904Sdim // Debug values must not have a slot index. 764235633Sdim // Other instructions must have one, unless they are inside a bundle. 765212904Sdim if (LiveInts) { 766212904Sdim bool mapped = !LiveInts->isNotInMIMap(MI); 767212904Sdim if (MI->isDebugValue()) { 768212904Sdim if (mapped) 769212904Sdim report("Debug instruction has a slot index", MI); 770235633Sdim } else if (MI->isInsideBundle()) { 771235633Sdim if (mapped) 772235633Sdim report("Instruction inside bundle has a slot index", MI); 773212904Sdim } else { 774212904Sdim if (!mapped) 775212904Sdim report("Missing slot index", MI); 776212904Sdim } 777212904Sdim } 778212904Sdim 779226890Sdim StringRef ErrorInfo; 780226890Sdim if (!TII->verifyInstruction(MI, ErrorInfo)) 781226890Sdim report(ErrorInfo.data(), MI); 782193323Sed} 783193323Sed 784193323Sedvoid 785198090SrdivackyMachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { 786193323Sed const MachineInstr *MI = MO->getParent(); 787224145Sdim const MCInstrDesc &MCID = MI->getDesc(); 788193323Sed 789224145Sdim // The first MCID.NumDefs operands must be explicit register defines 790224145Sdim if (MONum < MCID.getNumDefs()) { 791245431Sdim const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 792193323Sed if (!MO->isReg()) 793193323Sed report("Explicit definition must be a register", MO, MONum); 794245431Sdim else if (!MO->isDef() && !MCOI.isOptionalDef()) 795193323Sed report("Explicit definition marked as use", MO, MONum); 796193323Sed else if (MO->isImplicit()) 797193323Sed report("Explicit definition marked as implicit", MO, MONum); 798224145Sdim } else if (MONum < MCID.getNumOperands()) { 799245431Sdim const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 800218893Sdim // Don't check if it's the last operand in a variadic instruction. See, 801218893Sdim // e.g., LDM_RET in the arm back end. 802224145Sdim if (MO->isReg() && 803235633Sdim !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { 804224145Sdim if (MO->isDef() && !MCOI.isOptionalDef()) 805218893Sdim report("Explicit operand marked as def", MO, MONum); 806198090Srdivacky if (MO->isImplicit()) 807198090Srdivacky report("Explicit operand marked as implicit", MO, MONum); 808198090Srdivacky } 809245431Sdim 810245431Sdim int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO); 811245431Sdim if (TiedTo != -1) { 812245431Sdim if (!MO->isReg()) 813245431Sdim report("Tied use must be a register", MO, MONum); 814245431Sdim else if (!MO->isTied()) 815245431Sdim report("Operand should be tied", MO, MONum); 816245431Sdim else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum)) 817245431Sdim report("Tied def doesn't match MCInstrDesc", MO, MONum); 818245431Sdim } else if (MO->isReg() && MO->isTied()) 819245431Sdim report("Explicit operand should not be tied", MO, MONum); 820198090Srdivacky } else { 821201360Srdivacky // ARM adds %reg0 operands to indicate predicates. We'll allow that. 822235633Sdim if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg()) 823198090Srdivacky report("Extra explicit operand on non-variadic instruction", MO, MONum); 824193323Sed } 825193323Sed 826193323Sed switch (MO->getType()) { 827193323Sed case MachineOperand::MO_Register: { 828193323Sed const unsigned Reg = MO->getReg(); 829193323Sed if (!Reg) 830193323Sed return; 831235633Sdim if (MRI->tracksLiveness() && !MI->isDebugValue()) 832235633Sdim checkLiveness(MO, MONum); 833193323Sed 834245431Sdim // Verify the consistency of tied operands. 835245431Sdim if (MO->isTied()) { 836245431Sdim unsigned OtherIdx = MI->findTiedOperandIdx(MONum); 837245431Sdim const MachineOperand &OtherMO = MI->getOperand(OtherIdx); 838245431Sdim if (!OtherMO.isReg()) 839245431Sdim report("Must be tied to a register", MO, MONum); 840245431Sdim if (!OtherMO.isTied()) 841245431Sdim report("Missing tie flags on tied operand", MO, MONum); 842245431Sdim if (MI->findTiedOperandIdx(OtherIdx) != MONum) 843245431Sdim report("Inconsistent tie links", MO, MONum); 844245431Sdim if (MONum < MCID.getNumDefs()) { 845245431Sdim if (OtherIdx < MCID.getNumOperands()) { 846245431Sdim if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO)) 847245431Sdim report("Explicit def tied to explicit use without tie constraint", 848245431Sdim MO, MONum); 849245431Sdim } else { 850245431Sdim if (!OtherMO.isImplicit()) 851245431Sdim report("Explicit def should be tied to implicit use", MO, MONum); 852245431Sdim } 853245431Sdim } 854245431Sdim } 855198090Srdivacky 856245431Sdim // Verify two-address constraints after leaving SSA form. 857245431Sdim unsigned DefIdx; 858245431Sdim if (!MRI->isSSA() && MO->isUse() && 859245431Sdim MI->isRegTiedToDefOperand(MONum, &DefIdx) && 860245431Sdim Reg != MI->getOperand(DefIdx).getReg()) 861245431Sdim report("Two-address instruction operands must be identical", MO, MONum); 862245431Sdim 863193323Sed // Check register classes. 864224145Sdim if (MONum < MCID.getNumOperands() && !MO->isImplicit()) { 865193323Sed unsigned SubIdx = MO->getSubReg(); 866193323Sed 867193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 868193323Sed if (SubIdx) { 869226890Sdim report("Illegal subregister index for physical register", MO, MONum); 870226890Sdim return; 871193323Sed } 872245431Sdim if (const TargetRegisterClass *DRC = 873245431Sdim TII->getRegClass(MCID, MONum, TRI, *MF)) { 874226890Sdim if (!DRC->contains(Reg)) { 875193323Sed report("Illegal physical register for instruction", MO, MONum); 876226890Sdim *OS << TRI->getName(Reg) << " is not a " 877193323Sed << DRC->getName() << " register.\n"; 878193323Sed } 879193323Sed } 880193323Sed } else { 881193323Sed // Virtual register. 882193323Sed const TargetRegisterClass *RC = MRI->getRegClass(Reg); 883193323Sed if (SubIdx) { 884226890Sdim const TargetRegisterClass *SRC = 885226890Sdim TRI->getSubClassWithSubReg(RC, SubIdx); 886208599Srdivacky if (!SRC) { 887193323Sed report("Invalid subregister index for virtual register", MO, MONum); 888208599Srdivacky *OS << "Register class " << RC->getName() 889208599Srdivacky << " does not support subreg index " << SubIdx << "\n"; 890193323Sed return; 891193323Sed } 892226890Sdim if (RC != SRC) { 893226890Sdim report("Invalid register class for subregister index", MO, MONum); 894226890Sdim *OS << "Register class " << RC->getName() 895226890Sdim << " does not fully support subreg index " << SubIdx << "\n"; 896226890Sdim return; 897226890Sdim } 898193323Sed } 899245431Sdim if (const TargetRegisterClass *DRC = 900245431Sdim TII->getRegClass(MCID, MONum, TRI, *MF)) { 901226890Sdim if (SubIdx) { 902226890Sdim const TargetRegisterClass *SuperRC = 903226890Sdim TRI->getLargestLegalSuperClass(RC); 904226890Sdim if (!SuperRC) { 905226890Sdim report("No largest legal super class exists.", MO, MONum); 906226890Sdim return; 907226890Sdim } 908226890Sdim DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx); 909226890Sdim if (!DRC) { 910226890Sdim report("No matching super-reg register class.", MO, MONum); 911226890Sdim return; 912226890Sdim } 913226890Sdim } 914223017Sdim if (!RC->hasSuperClassEq(DRC)) { 915193323Sed report("Illegal virtual register for instruction", MO, MONum); 916193323Sed *OS << "Expected a " << DRC->getName() << " register, but got a " 917193323Sed << RC->getName() << " register\n"; 918193323Sed } 919193323Sed } 920193323Sed } 921193323Sed } 922193323Sed break; 923193323Sed } 924198090Srdivacky 925235633Sdim case MachineOperand::MO_RegisterMask: 926235633Sdim regMasks.push_back(MO->getRegMask()); 927235633Sdim break; 928235633Sdim 929198090Srdivacky case MachineOperand::MO_MachineBasicBlock: 930203954Srdivacky if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent())) 931203954Srdivacky report("PHI operand is not in the CFG", MO, MONum); 932198090Srdivacky break; 933198090Srdivacky 934218893Sdim case MachineOperand::MO_FrameIndex: 935218893Sdim if (LiveStks && LiveStks->hasInterval(MO->getIndex()) && 936218893Sdim LiveInts && !LiveInts->isNotInMIMap(MI)) { 937218893Sdim LiveInterval &LI = LiveStks->getInterval(MO->getIndex()); 938218893Sdim SlotIndex Idx = LiveInts->getInstructionIndex(MI); 939235633Sdim if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) { 940218893Sdim report("Instruction loads from dead spill slot", MO, MONum); 941218893Sdim *OS << "Live stack: " << LI << '\n'; 942218893Sdim } 943235633Sdim if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) { 944218893Sdim report("Instruction stores to dead spill slot", MO, MONum); 945218893Sdim *OS << "Live stack: " << LI << '\n'; 946218893Sdim } 947218893Sdim } 948218893Sdim break; 949218893Sdim 950193323Sed default: 951193323Sed break; 952193323Sed } 953193323Sed} 954193323Sed 955235633Sdimvoid MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { 956235633Sdim const MachineInstr *MI = MO->getParent(); 957235633Sdim const unsigned Reg = MO->getReg(); 958235633Sdim 959235633Sdim // Both use and def operands can read a register. 960235633Sdim if (MO->readsReg()) { 961235633Sdim regsLiveInButUnused.erase(Reg); 962235633Sdim 963245431Sdim if (MO->isKill()) 964235633Sdim addRegWithSubRegs(regsKilled, Reg); 965235633Sdim 966235633Sdim // Check that LiveVars knows this kill. 967235633Sdim if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) && 968235633Sdim MO->isKill()) { 969235633Sdim LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 970235633Sdim if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end()) 971235633Sdim report("Kill missing from LiveVariables", MO, MONum); 972235633Sdim } 973235633Sdim 974235633Sdim // Check LiveInts liveness and kill. 975245431Sdim if (LiveInts && !LiveInts->isNotInMIMap(MI)) { 976245431Sdim SlotIndex UseIdx = LiveInts->getInstructionIndex(MI); 977245431Sdim // Check the cached regunit intervals. 978245431Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) { 979245431Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 980245431Sdim if (const LiveInterval *LI = LiveInts->getCachedRegUnit(*Units)) { 981245431Sdim LiveRangeQuery LRQ(*LI, UseIdx); 982245431Sdim if (!LRQ.valueIn()) { 983245431Sdim report("No live range at use", MO, MONum); 984245431Sdim *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI) 985245431Sdim << ' ' << *LI << '\n'; 986245431Sdim } 987245431Sdim if (MO->isKill() && !LRQ.isKill()) { 988245431Sdim report("Live range continues after kill flag", MO, MONum); 989245431Sdim *OS << PrintRegUnit(*Units, TRI) << ' ' << *LI << '\n'; 990245431Sdim } 991245431Sdim } 992235633Sdim } 993245431Sdim } 994245431Sdim 995245431Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 996245431Sdim if (LiveInts->hasInterval(Reg)) { 997245431Sdim // This is a virtual register interval. 998245431Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 999245431Sdim LiveRangeQuery LRQ(LI, UseIdx); 1000245431Sdim if (!LRQ.valueIn()) { 1001245431Sdim report("No live range at use", MO, MONum); 1002245431Sdim *OS << UseIdx << " is not live in " << LI << '\n'; 1003245431Sdim } 1004245431Sdim // Check for extra kill flags. 1005245431Sdim // Note that we allow missing kill flags for now. 1006245431Sdim if (MO->isKill() && !LRQ.isKill()) { 1007245431Sdim report("Live range continues after kill flag", MO, MONum); 1008245431Sdim *OS << "Live range: " << LI << '\n'; 1009245431Sdim } 1010245431Sdim } else { 1011245431Sdim report("Virtual register has no live interval", MO, MONum); 1012235633Sdim } 1013235633Sdim } 1014235633Sdim } 1015235633Sdim 1016235633Sdim // Use of a dead register. 1017235633Sdim if (!regsLive.count(Reg)) { 1018235633Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 1019235633Sdim // Reserved registers may be used even when 'dead'. 1020235633Sdim if (!isReserved(Reg)) 1021235633Sdim report("Using an undefined physical register", MO, MONum); 1022245431Sdim } else if (MRI->def_empty(Reg)) { 1023245431Sdim report("Reading virtual register without a def", MO, MONum); 1024235633Sdim } else { 1025235633Sdim BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1026235633Sdim // We don't know which virtual registers are live in, so only complain 1027235633Sdim // if vreg was killed in this MBB. Otherwise keep track of vregs that 1028235633Sdim // must be live in. PHI instructions are handled separately. 1029235633Sdim if (MInfo.regsKilled.count(Reg)) 1030235633Sdim report("Using a killed virtual register", MO, MONum); 1031235633Sdim else if (!MI->isPHI()) 1032235633Sdim MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 1033235633Sdim } 1034235633Sdim } 1035235633Sdim } 1036235633Sdim 1037235633Sdim if (MO->isDef()) { 1038235633Sdim // Register defined. 1039235633Sdim // TODO: verify that earlyclobber ops are not used. 1040235633Sdim if (MO->isDead()) 1041235633Sdim addRegWithSubRegs(regsDead, Reg); 1042235633Sdim else 1043235633Sdim addRegWithSubRegs(regsDefined, Reg); 1044235633Sdim 1045235633Sdim // Verify SSA form. 1046235633Sdim if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) && 1047235633Sdim llvm::next(MRI->def_begin(Reg)) != MRI->def_end()) 1048235633Sdim report("Multiple virtual register defs in SSA form", MO, MONum); 1049235633Sdim 1050235633Sdim // Check LiveInts for a live range, but only for virtual registers. 1051235633Sdim if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) && 1052235633Sdim !LiveInts->isNotInMIMap(MI)) { 1053245431Sdim SlotIndex DefIdx = LiveInts->getInstructionIndex(MI); 1054245431Sdim DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber()); 1055235633Sdim if (LiveInts->hasInterval(Reg)) { 1056235633Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1057235633Sdim if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) { 1058235633Sdim assert(VNI && "NULL valno is not allowed"); 1059245431Sdim if (VNI->def != DefIdx) { 1060235633Sdim report("Inconsistent valno->def", MO, MONum); 1061235633Sdim *OS << "Valno " << VNI->id << " is not defined at " 1062235633Sdim << DefIdx << " in " << LI << '\n'; 1063235633Sdim } 1064235633Sdim } else { 1065235633Sdim report("No live range at def", MO, MONum); 1066235633Sdim *OS << DefIdx << " is not live in " << LI << '\n'; 1067235633Sdim } 1068235633Sdim } else { 1069235633Sdim report("Virtual register has no Live interval", MO, MONum); 1070235633Sdim } 1071235633Sdim } 1072235633Sdim } 1073235633Sdim} 1074235633Sdim 1075198090Srdivackyvoid MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { 1076245431Sdim} 1077245431Sdim 1078245431Sdim// This function gets called after visiting all instructions in a bundle. The 1079245431Sdim// argument points to the bundle header. 1080245431Sdim// Normal stand-alone instructions are also considered 'bundles', and this 1081245431Sdim// function is called for all of them. 1082245431Sdimvoid MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) { 1083193323Sed BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1084193323Sed set_union(MInfo.regsKilled, regsKilled); 1085212904Sdim set_subtract(regsLive, regsKilled); regsKilled.clear(); 1086235633Sdim // Kill any masked registers. 1087235633Sdim while (!regMasks.empty()) { 1088235633Sdim const uint32_t *Mask = regMasks.pop_back_val(); 1089235633Sdim for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I) 1090235633Sdim if (TargetRegisterInfo::isPhysicalRegister(*I) && 1091235633Sdim MachineOperand::clobbersPhysReg(Mask, *I)) 1092235633Sdim regsDead.push_back(*I); 1093235633Sdim } 1094212904Sdim set_subtract(regsLive, regsDead); regsDead.clear(); 1095212904Sdim set_union(regsLive, regsDefined); regsDefined.clear(); 1096193323Sed} 1097193323Sed 1098193323Sedvoid 1099198090SrdivackyMachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { 1100193323Sed MBBInfoMap[MBB].regsLiveOut = regsLive; 1101193323Sed regsLive.clear(); 1102218893Sdim 1103218893Sdim if (Indexes) { 1104218893Sdim SlotIndex stop = Indexes->getMBBEndIdx(MBB); 1105218893Sdim if (!(stop > lastIndex)) { 1106218893Sdim report("Block ends before last instruction index", MBB); 1107218893Sdim *OS << "Block ends at " << stop 1108218893Sdim << " last instruction was at " << lastIndex << '\n'; 1109218893Sdim } 1110218893Sdim lastIndex = stop; 1111218893Sdim } 1112193323Sed} 1113193323Sed 1114193323Sed// Calculate the largest possible vregsPassed sets. These are the registers that 1115193323Sed// can pass through an MBB live, but may not be live every time. It is assumed 1116193323Sed// that all vregsPassed sets are empty before the call. 1117202375Srdivackyvoid MachineVerifier::calcRegsPassed() { 1118193323Sed // First push live-out regs to successors' vregsPassed. Remember the MBBs that 1119193323Sed // have any vregsPassed. 1120235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> todo; 1121193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1122193323Sed MFI != MFE; ++MFI) { 1123193323Sed const MachineBasicBlock &MBB(*MFI); 1124193323Sed BBInfo &MInfo = MBBInfoMap[&MBB]; 1125193323Sed if (!MInfo.reachable) 1126193323Sed continue; 1127193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 1128193323Sed SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 1129193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 1130193323Sed if (SInfo.addPassed(MInfo.regsLiveOut)) 1131193323Sed todo.insert(*SuI); 1132193323Sed } 1133193323Sed } 1134193323Sed 1135193323Sed // Iteratively push vregsPassed to successors. This will converge to the same 1136193323Sed // final state regardless of DenseSet iteration order. 1137193323Sed while (!todo.empty()) { 1138193323Sed const MachineBasicBlock *MBB = *todo.begin(); 1139193323Sed todo.erase(MBB); 1140193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 1141193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 1142193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 1143193323Sed if (*SuI == MBB) 1144193323Sed continue; 1145193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 1146193323Sed if (SInfo.addPassed(MInfo.vregsPassed)) 1147193323Sed todo.insert(*SuI); 1148193323Sed } 1149193323Sed } 1150193323Sed} 1151193323Sed 1152199511Srdivacky// Calculate the set of virtual registers that must be passed through each basic 1153199511Srdivacky// block in order to satisfy the requirements of successor blocks. This is very 1154202375Srdivacky// similar to calcRegsPassed, only backwards. 1155199511Srdivackyvoid MachineVerifier::calcRegsRequired() { 1156199511Srdivacky // First push live-in regs to predecessors' vregsRequired. 1157235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> todo; 1158199511Srdivacky for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1159199511Srdivacky MFI != MFE; ++MFI) { 1160199511Srdivacky const MachineBasicBlock &MBB(*MFI); 1161199511Srdivacky BBInfo &MInfo = MBBInfoMap[&MBB]; 1162199511Srdivacky for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(), 1163199511Srdivacky PrE = MBB.pred_end(); PrI != PrE; ++PrI) { 1164199511Srdivacky BBInfo &PInfo = MBBInfoMap[*PrI]; 1165199511Srdivacky if (PInfo.addRequired(MInfo.vregsLiveIn)) 1166199511Srdivacky todo.insert(*PrI); 1167199511Srdivacky } 1168199511Srdivacky } 1169199511Srdivacky 1170199511Srdivacky // Iteratively push vregsRequired to predecessors. This will converge to the 1171199511Srdivacky // same final state regardless of DenseSet iteration order. 1172199511Srdivacky while (!todo.empty()) { 1173199511Srdivacky const MachineBasicBlock *MBB = *todo.begin(); 1174199511Srdivacky todo.erase(MBB); 1175199511Srdivacky BBInfo &MInfo = MBBInfoMap[MBB]; 1176199511Srdivacky for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1177199511Srdivacky PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1178199511Srdivacky if (*PrI == MBB) 1179199511Srdivacky continue; 1180199511Srdivacky BBInfo &SInfo = MBBInfoMap[*PrI]; 1181199511Srdivacky if (SInfo.addRequired(MInfo.vregsRequired)) 1182199511Srdivacky todo.insert(*PrI); 1183199511Srdivacky } 1184199511Srdivacky } 1185199511Srdivacky} 1186199511Srdivacky 1187193323Sed// Check PHI instructions at the beginning of MBB. It is assumed that 1188202375Srdivacky// calcRegsPassed has been run so BBInfo::isLiveOut is valid. 1189198090Srdivackyvoid MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) { 1190235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> seen; 1191193323Sed for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 1192203954Srdivacky BBI != BBE && BBI->isPHI(); ++BBI) { 1193235633Sdim seen.clear(); 1194193323Sed 1195193323Sed for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 1196193323Sed unsigned Reg = BBI->getOperand(i).getReg(); 1197193323Sed const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB(); 1198193323Sed if (!Pre->isSuccessor(MBB)) 1199193323Sed continue; 1200193323Sed seen.insert(Pre); 1201193323Sed BBInfo &PrInfo = MBBInfoMap[Pre]; 1202193323Sed if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 1203193323Sed report("PHI operand is not live-out from predecessor", 1204193323Sed &BBI->getOperand(i), i); 1205193323Sed } 1206193323Sed 1207193323Sed // Did we see all predecessors? 1208193323Sed for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1209193323Sed PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1210193323Sed if (!seen.count(*PrI)) { 1211193323Sed report("Missing PHI operand", BBI); 1212198892Srdivacky *OS << "BB#" << (*PrI)->getNumber() 1213193323Sed << " is a predecessor according to the CFG.\n"; 1214193323Sed } 1215193323Sed } 1216193323Sed } 1217193323Sed} 1218193323Sed 1219198090Srdivackyvoid MachineVerifier::visitMachineFunctionAfter() { 1220202375Srdivacky calcRegsPassed(); 1221193323Sed 1222193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1223193323Sed MFI != MFE; ++MFI) { 1224193323Sed BBInfo &MInfo = MBBInfoMap[MFI]; 1225193323Sed 1226193323Sed // Skip unreachable MBBs. 1227193323Sed if (!MInfo.reachable) 1228193323Sed continue; 1229193323Sed 1230202375Srdivacky checkPHIOps(MFI); 1231193323Sed } 1232193323Sed 1233212904Sdim // Now check liveness info if available 1234235633Sdim calcRegsRequired(); 1235235633Sdim 1236245431Sdim // Check for killed virtual registers that should be live out. 1237245431Sdim for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1238245431Sdim MFI != MFE; ++MFI) { 1239245431Sdim BBInfo &MInfo = MBBInfoMap[MFI]; 1240245431Sdim for (RegSet::iterator 1241245431Sdim I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1242245431Sdim ++I) 1243245431Sdim if (MInfo.regsKilled.count(*I)) { 1244245431Sdim report("Virtual register killed in block, but needed live out.", MFI); 1245245431Sdim *OS << "Virtual register " << PrintReg(*I) 1246245431Sdim << " is used after the block.\n"; 1247245431Sdim } 1248245431Sdim } 1249245431Sdim 1250245431Sdim if (!MF->empty()) { 1251235633Sdim BBInfo &MInfo = MBBInfoMap[&MF->front()]; 1252235633Sdim for (RegSet::iterator 1253235633Sdim I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1254235633Sdim ++I) 1255235633Sdim report("Virtual register def doesn't dominate all uses.", 1256235633Sdim MRI->getVRegDef(*I)); 1257235633Sdim } 1258235633Sdim 1259212904Sdim if (LiveVars) 1260199511Srdivacky verifyLiveVariables(); 1261212904Sdim if (LiveInts) 1262212904Sdim verifyLiveIntervals(); 1263193323Sed} 1264199511Srdivacky 1265199511Srdivackyvoid MachineVerifier::verifyLiveVariables() { 1266199511Srdivacky assert(LiveVars && "Don't call verifyLiveVariables without LiveVars"); 1267218893Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1268218893Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1269199511Srdivacky LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1270199511Srdivacky for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1271199511Srdivacky MFI != MFE; ++MFI) { 1272199511Srdivacky BBInfo &MInfo = MBBInfoMap[MFI]; 1273199511Srdivacky 1274199511Srdivacky // Our vregsRequired should be identical to LiveVariables' AliveBlocks 1275199511Srdivacky if (MInfo.vregsRequired.count(Reg)) { 1276199511Srdivacky if (!VI.AliveBlocks.test(MFI->getNumber())) { 1277199511Srdivacky report("LiveVariables: Block missing from AliveBlocks", MFI); 1278218893Sdim *OS << "Virtual register " << PrintReg(Reg) 1279199511Srdivacky << " must be live through the block.\n"; 1280199511Srdivacky } 1281199511Srdivacky } else { 1282199511Srdivacky if (VI.AliveBlocks.test(MFI->getNumber())) { 1283199511Srdivacky report("LiveVariables: Block should not be in AliveBlocks", MFI); 1284218893Sdim *OS << "Virtual register " << PrintReg(Reg) 1285199511Srdivacky << " is not needed live through the block.\n"; 1286199511Srdivacky } 1287199511Srdivacky } 1288199511Srdivacky } 1289199511Srdivacky } 1290199511Srdivacky} 1291199511Srdivacky 1292212904Sdimvoid MachineVerifier::verifyLiveIntervals() { 1293212904Sdim assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts"); 1294245431Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1295245431Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1296218893Sdim 1297218893Sdim // Spilling and splitting may leave unused registers around. Skip them. 1298245431Sdim if (MRI->reg_nodbg_empty(Reg)) 1299218893Sdim continue; 1300218893Sdim 1301245431Sdim if (!LiveInts->hasInterval(Reg)) { 1302245431Sdim report("Missing live interval for virtual register", MF); 1303245431Sdim *OS << PrintReg(Reg, TRI) << " still has defs or uses\n"; 1304218893Sdim continue; 1305245431Sdim } 1306218893Sdim 1307245431Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1308245431Sdim assert(Reg == LI.reg && "Invalid reg to interval mapping"); 1309245431Sdim verifyLiveInterval(LI); 1310245431Sdim } 1311199511Srdivacky 1312245431Sdim // Verify all the cached regunit intervals. 1313245431Sdim for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 1314245431Sdim if (const LiveInterval *LI = LiveInts->getCachedRegUnit(i)) 1315245431Sdim verifyLiveInterval(*LI); 1316245431Sdim} 1317212904Sdim 1318245431Sdimvoid MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI, 1319245431Sdim VNInfo *VNI) { 1320245431Sdim if (VNI->isUnused()) 1321245431Sdim return; 1322212904Sdim 1323245431Sdim const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def); 1324212904Sdim 1325245431Sdim if (!DefVNI) { 1326245431Sdim report("Valno not live at def and not marked unused", MF, LI); 1327245431Sdim *OS << "Valno #" << VNI->id << '\n'; 1328245431Sdim return; 1329245431Sdim } 1330212904Sdim 1331245431Sdim if (DefVNI != VNI) { 1332245431Sdim report("Live range at def has different valno", MF, LI); 1333245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1334245431Sdim << " where valno #" << DefVNI->id << " is live\n"; 1335245431Sdim return; 1336245431Sdim } 1337218893Sdim 1338245431Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); 1339245431Sdim if (!MBB) { 1340245431Sdim report("Invalid definition index", MF, LI); 1341245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1342245431Sdim << " in " << LI << '\n'; 1343245431Sdim return; 1344245431Sdim } 1345218893Sdim 1346245431Sdim if (VNI->isPHIDef()) { 1347245431Sdim if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { 1348245431Sdim report("PHIDef value is not defined at MBB start", MBB, LI); 1349245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1350245431Sdim << ", not at the beginning of BB#" << MBB->getNumber() << '\n'; 1351245431Sdim } 1352245431Sdim return; 1353245431Sdim } 1354218893Sdim 1355245431Sdim // Non-PHI def. 1356245431Sdim const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); 1357245431Sdim if (!MI) { 1358245431Sdim report("No instruction at def index", MBB, LI); 1359245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1360245431Sdim return; 1361245431Sdim } 1362235633Sdim 1363245431Sdim bool hasDef = false; 1364245431Sdim bool isEarlyClobber = false; 1365245431Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1366245431Sdim if (!MOI->isReg() || !MOI->isDef()) 1367245431Sdim continue; 1368245431Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1369245431Sdim if (MOI->getReg() != LI.reg) 1370245431Sdim continue; 1371245431Sdim } else { 1372245431Sdim if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || 1373245431Sdim !TRI->hasRegUnit(MOI->getReg(), LI.reg)) 1374245431Sdim continue; 1375212904Sdim } 1376245431Sdim hasDef = true; 1377245431Sdim if (MOI->isEarlyClobber()) 1378245431Sdim isEarlyClobber = true; 1379245431Sdim } 1380212904Sdim 1381245431Sdim if (!hasDef) { 1382245431Sdim report("Defining instruction does not modify register", MI); 1383245431Sdim *OS << "Valno #" << VNI->id << " in " << LI << '\n'; 1384245431Sdim } 1385212904Sdim 1386245431Sdim // Early clobber defs begin at USE slots, but other defs must begin at 1387245431Sdim // DEF slots. 1388245431Sdim if (isEarlyClobber) { 1389245431Sdim if (!VNI->def.isEarlyClobber()) { 1390245431Sdim report("Early clobber def must be at an early-clobber slot", MBB, LI); 1391245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1392245431Sdim } 1393245431Sdim } else if (!VNI->def.isRegister()) { 1394245431Sdim report("Non-PHI, non-early clobber def must be at a register slot", 1395245431Sdim MBB, LI); 1396245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1397245431Sdim } 1398245431Sdim} 1399212904Sdim 1400245431Sdimvoid 1401245431SdimMachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI, 1402245431Sdim LiveInterval::const_iterator I) { 1403245431Sdim const VNInfo *VNI = I->valno; 1404245431Sdim assert(VNI && "Live range has no valno"); 1405212904Sdim 1406245431Sdim if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) { 1407245431Sdim report("Foreign valno in live range", MF, LI); 1408245431Sdim *OS << *I << " has a bad valno\n"; 1409245431Sdim } 1410218893Sdim 1411245431Sdim if (VNI->isUnused()) { 1412245431Sdim report("Live range valno is marked unused", MF, LI); 1413245431Sdim *OS << *I << '\n'; 1414245431Sdim } 1415235633Sdim 1416245431Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start); 1417245431Sdim if (!MBB) { 1418245431Sdim report("Bad start of live segment, no basic block", MF, LI); 1419245431Sdim *OS << *I << '\n'; 1420245431Sdim return; 1421245431Sdim } 1422245431Sdim SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB); 1423245431Sdim if (I->start != MBBStartIdx && I->start != VNI->def) { 1424245431Sdim report("Live segment must begin at MBB entry or valno def", MBB, LI); 1425245431Sdim *OS << *I << '\n'; 1426245431Sdim } 1427235633Sdim 1428245431Sdim const MachineBasicBlock *EndMBB = 1429245431Sdim LiveInts->getMBBFromIndex(I->end.getPrevSlot()); 1430245431Sdim if (!EndMBB) { 1431245431Sdim report("Bad end of live segment, no basic block", MF, LI); 1432245431Sdim *OS << *I << '\n'; 1433245431Sdim return; 1434245431Sdim } 1435245431Sdim 1436245431Sdim // No more checks for live-out segments. 1437245431Sdim if (I->end == LiveInts->getMBBEndIdx(EndMBB)) 1438245431Sdim return; 1439245431Sdim 1440245431Sdim // RegUnit intervals are allowed dead phis. 1441245431Sdim if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && VNI->isPHIDef() && 1442245431Sdim I->start == VNI->def && I->end == VNI->def.getDeadSlot()) 1443245431Sdim return; 1444245431Sdim 1445245431Sdim // The live segment is ending inside EndMBB 1446245431Sdim const MachineInstr *MI = 1447245431Sdim LiveInts->getInstructionFromIndex(I->end.getPrevSlot()); 1448245431Sdim if (!MI) { 1449245431Sdim report("Live segment doesn't end at a valid instruction", EndMBB, LI); 1450245431Sdim *OS << *I << '\n'; 1451245431Sdim return; 1452245431Sdim } 1453245431Sdim 1454245431Sdim // The block slot must refer to a basic block boundary. 1455245431Sdim if (I->end.isBlock()) { 1456245431Sdim report("Live segment ends at B slot of an instruction", EndMBB, LI); 1457245431Sdim *OS << *I << '\n'; 1458245431Sdim } 1459245431Sdim 1460245431Sdim if (I->end.isDead()) { 1461245431Sdim // Segment ends on the dead slot. 1462245431Sdim // That means there must be a dead def. 1463245431Sdim if (!SlotIndex::isSameInstr(I->start, I->end)) { 1464245431Sdim report("Live segment ending at dead slot spans instructions", EndMBB, LI); 1465245431Sdim *OS << *I << '\n'; 1466245431Sdim } 1467245431Sdim } 1468245431Sdim 1469245431Sdim // A live segment can only end at an early-clobber slot if it is being 1470245431Sdim // redefined by an early-clobber def. 1471245431Sdim if (I->end.isEarlyClobber()) { 1472245431Sdim if (I+1 == LI.end() || (I+1)->start != I->end) { 1473245431Sdim report("Live segment ending at early clobber slot must be " 1474245431Sdim "redefined by an EC def in the same instruction", EndMBB, LI); 1475245431Sdim *OS << *I << '\n'; 1476245431Sdim } 1477245431Sdim } 1478245431Sdim 1479245431Sdim // The following checks only apply to virtual registers. Physreg liveness 1480245431Sdim // is too weird to check. 1481245431Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1482245431Sdim // A live range can end with either a redefinition, a kill flag on a 1483245431Sdim // use, or a dead flag on a def. 1484245431Sdim bool hasRead = false; 1485245431Sdim bool hasDeadDef = false; 1486245431Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1487245431Sdim if (!MOI->isReg() || MOI->getReg() != LI.reg) 1488235633Sdim continue; 1489245431Sdim if (MOI->readsReg()) 1490245431Sdim hasRead = true; 1491245431Sdim if (MOI->isDef() && MOI->isDead()) 1492245431Sdim hasDeadDef = true; 1493245431Sdim } 1494218893Sdim 1495245431Sdim if (I->end.isDead()) { 1496245431Sdim if (!hasDeadDef) { 1497245431Sdim report("Instruction doesn't have a dead def operand", MI); 1498235633Sdim I->print(*OS); 1499235633Sdim *OS << " in " << LI << '\n'; 1500235633Sdim } 1501245431Sdim } else { 1502245431Sdim if (!hasRead) { 1503245431Sdim report("Instruction ending live range doesn't read the register", MI); 1504245431Sdim *OS << *I << " in " << LI << '\n'; 1505235633Sdim } 1506245431Sdim } 1507245431Sdim } 1508235633Sdim 1509245431Sdim // Now check all the basic blocks in this live segment. 1510245431Sdim MachineFunction::const_iterator MFI = MBB; 1511245431Sdim // Is this live range the beginning of a non-PHIDef VN? 1512245431Sdim if (I->start == VNI->def && !VNI->isPHIDef()) { 1513245431Sdim // Not live-in to any blocks. 1514245431Sdim if (MBB == EndMBB) 1515245431Sdim return; 1516245431Sdim // Skip this block. 1517245431Sdim ++MFI; 1518245431Sdim } 1519245431Sdim for (;;) { 1520245431Sdim assert(LiveInts->isLiveInToMBB(LI, MFI)); 1521245431Sdim // We don't know how to track physregs into a landing pad. 1522245431Sdim if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && 1523245431Sdim MFI->isLandingPad()) { 1524245431Sdim if (&*MFI == EndMBB) 1525245431Sdim break; 1526245431Sdim ++MFI; 1527245431Sdim continue; 1528245431Sdim } 1529235633Sdim 1530245431Sdim // Is VNI a PHI-def in the current block? 1531245431Sdim bool IsPHI = VNI->isPHIDef() && 1532245431Sdim VNI->def == LiveInts->getMBBStartIdx(MFI); 1533235633Sdim 1534245431Sdim // Check that VNI is live-out of all predecessors. 1535245431Sdim for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(), 1536245431Sdim PE = MFI->pred_end(); PI != PE; ++PI) { 1537245431Sdim SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI); 1538245431Sdim const VNInfo *PVNI = LI.getVNInfoBefore(PEnd); 1539245431Sdim 1540245431Sdim // All predecessors must have a live-out value. 1541245431Sdim if (!PVNI) { 1542245431Sdim report("Register not marked live out of predecessor", *PI, LI); 1543245431Sdim *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber() 1544245431Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before " 1545245431Sdim << PEnd << '\n'; 1546245431Sdim continue; 1547218893Sdim } 1548218893Sdim 1549245431Sdim // Only PHI-defs can take different predecessor values. 1550245431Sdim if (!IsPHI && PVNI != VNI) { 1551245431Sdim report("Different value live out of predecessor", *PI, LI); 1552245431Sdim *OS << "Valno #" << PVNI->id << " live out of BB#" 1553245431Sdim << (*PI)->getNumber() << '@' << PEnd 1554245431Sdim << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber() 1555245431Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << '\n'; 1556218893Sdim } 1557245431Sdim } 1558245431Sdim if (&*MFI == EndMBB) 1559245431Sdim break; 1560245431Sdim ++MFI; 1561245431Sdim } 1562245431Sdim} 1563218893Sdim 1564245431Sdimvoid MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { 1565245431Sdim for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 1566245431Sdim I!=E; ++I) 1567245431Sdim verifyLiveIntervalValue(LI, *I); 1568218893Sdim 1569245431Sdim for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) 1570245431Sdim verifyLiveIntervalSegment(LI, I); 1571218893Sdim 1572245431Sdim // Check the LI only has one connected component. 1573245431Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1574245431Sdim ConnectedVNInfoEqClasses ConEQ(*LiveInts); 1575245431Sdim unsigned NumComp = ConEQ.Classify(&LI); 1576245431Sdim if (NumComp > 1) { 1577245431Sdim report("Multiple connected components in live interval", MF, LI); 1578245431Sdim for (unsigned comp = 0; comp != NumComp; ++comp) { 1579245431Sdim *OS << comp << ": valnos"; 1580245431Sdim for (LiveInterval::const_vni_iterator I = LI.vni_begin(), 1581245431Sdim E = LI.vni_end(); I!=E; ++I) 1582245431Sdim if (comp == ConEQ.getEqClass(*I)) 1583245431Sdim *OS << ' ' << (*I)->id; 1584245431Sdim *OS << '\n'; 1585218893Sdim } 1586212904Sdim } 1587212904Sdim } 1588212904Sdim} 1589