MachineVerifier.cpp revision 235633
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 26223017Sdim#include "llvm/Instructions.h" 27193323Sed#include "llvm/Function.h" 28212904Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 29193323Sed#include "llvm/CodeGen/LiveVariables.h" 30218893Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 31235633Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 32193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 33198090Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 34198090Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 35193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 36193323Sed#include "llvm/CodeGen/Passes.h" 37223017Sdim#include "llvm/MC/MCAsmInfo.h" 38193323Sed#include "llvm/Target/TargetMachine.h" 39193323Sed#include "llvm/Target/TargetRegisterInfo.h" 40193323Sed#include "llvm/Target/TargetInstrInfo.h" 41198090Srdivacky#include "llvm/ADT/DenseSet.h" 42198090Srdivacky#include "llvm/ADT/SetOperations.h" 43198090Srdivacky#include "llvm/ADT/SmallVector.h" 44193323Sed#include "llvm/Support/Debug.h" 45198090Srdivacky#include "llvm/Support/ErrorHandling.h" 46198090Srdivacky#include "llvm/Support/raw_ostream.h" 47193323Sedusing namespace llvm; 48193323Sed 49193323Sednamespace { 50199511Srdivacky struct MachineVerifier { 51193323Sed 52218893Sdim MachineVerifier(Pass *pass, const char *b) : 53199511Srdivacky PASS(pass), 54218893Sdim Banner(b), 55193323Sed OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) 56199511Srdivacky {} 57193323Sed 58193323Sed bool runOnMachineFunction(MachineFunction &MF); 59193323Sed 60199511Srdivacky Pass *const PASS; 61218893Sdim const char *Banner; 62193323Sed const char *const OutFileName; 63198090Srdivacky raw_ostream *OS; 64193323Sed const MachineFunction *MF; 65193323Sed const TargetMachine *TM; 66224145Sdim const TargetInstrInfo *TII; 67193323Sed const TargetRegisterInfo *TRI; 68193323Sed const MachineRegisterInfo *MRI; 69193323Sed 70193323Sed unsigned foundErrors; 71193323Sed 72193323Sed typedef SmallVector<unsigned, 16> RegVector; 73235633Sdim typedef SmallVector<const uint32_t*, 4> RegMaskVector; 74193323Sed typedef DenseSet<unsigned> RegSet; 75193323Sed typedef DenseMap<unsigned, const MachineInstr*> RegMap; 76193323Sed 77226890Sdim const MachineInstr *FirstTerminator; 78226890Sdim 79193323Sed BitVector regsReserved; 80235633Sdim BitVector regsAllocatable; 81193323Sed RegSet regsLive; 82198090Srdivacky RegVector regsDefined, regsDead, regsKilled; 83235633Sdim RegMaskVector regMasks; 84198090Srdivacky RegSet regsLiveInButUnused; 85193323Sed 86218893Sdim SlotIndex lastIndex; 87218893Sdim 88193323Sed // Add Reg and any sub-registers to RV 89193323Sed void addRegWithSubRegs(RegVector &RV, unsigned Reg) { 90193323Sed RV.push_back(Reg); 91193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) 92235633Sdim for (const uint16_t *R = TRI->getSubRegisters(Reg); *R; R++) 93193323Sed RV.push_back(*R); 94193323Sed } 95193323Sed 96193323Sed struct BBInfo { 97193323Sed // Is this MBB reachable from the MF entry point? 98193323Sed bool reachable; 99193323Sed 100193323Sed // Vregs that must be live in because they are used without being 101193323Sed // defined. Map value is the user. 102193323Sed RegMap vregsLiveIn; 103193323Sed 104193323Sed // Regs killed in MBB. They may be defined again, and will then be in both 105193323Sed // regsKilled and regsLiveOut. 106193323Sed RegSet regsKilled; 107193323Sed 108193323Sed // Regs defined in MBB and live out. Note that vregs passing through may 109193323Sed // be live out without being mentioned here. 110193323Sed RegSet regsLiveOut; 111193323Sed 112193323Sed // Vregs that pass through MBB untouched. This set is disjoint from 113193323Sed // regsKilled and regsLiveOut. 114193323Sed RegSet vregsPassed; 115193323Sed 116199511Srdivacky // Vregs that must pass through MBB because they are needed by a successor 117199511Srdivacky // block. This set is disjoint from regsLiveOut. 118199511Srdivacky RegSet vregsRequired; 119199511Srdivacky 120193323Sed BBInfo() : reachable(false) {} 121193323Sed 122193323Sed // Add register to vregsPassed if it belongs there. Return true if 123193323Sed // anything changed. 124193323Sed bool addPassed(unsigned Reg) { 125193323Sed if (!TargetRegisterInfo::isVirtualRegister(Reg)) 126193323Sed return false; 127193323Sed if (regsKilled.count(Reg) || regsLiveOut.count(Reg)) 128193323Sed return false; 129193323Sed return vregsPassed.insert(Reg).second; 130193323Sed } 131193323Sed 132193323Sed // Same for a full set. 133193323Sed bool addPassed(const RegSet &RS) { 134193323Sed bool changed = false; 135193323Sed for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 136193323Sed if (addPassed(*I)) 137193323Sed changed = true; 138193323Sed return changed; 139193323Sed } 140193323Sed 141199511Srdivacky // Add register to vregsRequired if it belongs there. Return true if 142199511Srdivacky // anything changed. 143199511Srdivacky bool addRequired(unsigned Reg) { 144199511Srdivacky if (!TargetRegisterInfo::isVirtualRegister(Reg)) 145199511Srdivacky return false; 146199511Srdivacky if (regsLiveOut.count(Reg)) 147199511Srdivacky return false; 148199511Srdivacky return vregsRequired.insert(Reg).second; 149199511Srdivacky } 150199511Srdivacky 151199511Srdivacky // Same for a full set. 152199511Srdivacky bool addRequired(const RegSet &RS) { 153199511Srdivacky bool changed = false; 154199511Srdivacky for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 155199511Srdivacky if (addRequired(*I)) 156199511Srdivacky changed = true; 157199511Srdivacky return changed; 158199511Srdivacky } 159199511Srdivacky 160199511Srdivacky // Same for a full map. 161199511Srdivacky bool addRequired(const RegMap &RM) { 162199511Srdivacky bool changed = false; 163199511Srdivacky for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I) 164199511Srdivacky if (addRequired(I->first)) 165199511Srdivacky changed = true; 166199511Srdivacky return changed; 167199511Srdivacky } 168199511Srdivacky 169193323Sed // Live-out registers are either in regsLiveOut or vregsPassed. 170193323Sed bool isLiveOut(unsigned Reg) const { 171193323Sed return regsLiveOut.count(Reg) || vregsPassed.count(Reg); 172193323Sed } 173193323Sed }; 174193323Sed 175193323Sed // Extra register info per MBB. 176193323Sed DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap; 177193323Sed 178193323Sed bool isReserved(unsigned Reg) { 179198090Srdivacky return Reg < regsReserved.size() && regsReserved.test(Reg); 180193323Sed } 181193323Sed 182235633Sdim bool isAllocatable(unsigned Reg) { 183235633Sdim return Reg < regsAllocatable.size() && regsAllocatable.test(Reg); 184235633Sdim } 185235633Sdim 186199511Srdivacky // Analysis information if available 187199511Srdivacky LiveVariables *LiveVars; 188218893Sdim LiveIntervals *LiveInts; 189218893Sdim LiveStacks *LiveStks; 190218893Sdim SlotIndexes *Indexes; 191199511Srdivacky 192193323Sed void visitMachineFunctionBefore(); 193193323Sed void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); 194193323Sed void visitMachineInstrBefore(const MachineInstr *MI); 195193323Sed void visitMachineOperand(const MachineOperand *MO, unsigned MONum); 196193323Sed void visitMachineInstrAfter(const MachineInstr *MI); 197193323Sed void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB); 198193323Sed void visitMachineFunctionAfter(); 199193323Sed 200193323Sed void report(const char *msg, const MachineFunction *MF); 201193323Sed void report(const char *msg, const MachineBasicBlock *MBB); 202193323Sed void report(const char *msg, const MachineInstr *MI); 203193323Sed void report(const char *msg, const MachineOperand *MO, unsigned MONum); 204193323Sed 205235633Sdim void checkLiveness(const MachineOperand *MO, unsigned MONum); 206193323Sed void markReachable(const MachineBasicBlock *MBB); 207202375Srdivacky void calcRegsPassed(); 208193323Sed void checkPHIOps(const MachineBasicBlock *MBB); 209199511Srdivacky 210199511Srdivacky void calcRegsRequired(); 211199511Srdivacky void verifyLiveVariables(); 212212904Sdim void verifyLiveIntervals(); 213193323Sed }; 214199511Srdivacky 215199511Srdivacky struct MachineVerifierPass : public MachineFunctionPass { 216199511Srdivacky static char ID; // Pass ID, replacement for typeid 217218893Sdim const char *const Banner; 218199511Srdivacky 219218893Sdim MachineVerifierPass(const char *b = 0) 220218893Sdim : MachineFunctionPass(ID), Banner(b) { 221218893Sdim initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry()); 222218893Sdim } 223199511Srdivacky 224199511Srdivacky void getAnalysisUsage(AnalysisUsage &AU) const { 225199511Srdivacky AU.setPreservesAll(); 226199511Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 227199511Srdivacky } 228199511Srdivacky 229199511Srdivacky bool runOnMachineFunction(MachineFunction &MF) { 230218893Sdim MF.verify(this, Banner); 231199511Srdivacky return false; 232199511Srdivacky } 233199511Srdivacky }; 234199511Srdivacky 235193323Sed} 236193323Sed 237199511Srdivackychar MachineVerifierPass::ID = 0; 238212904SdimINITIALIZE_PASS(MachineVerifierPass, "machineverifier", 239218893Sdim "Verify generated machine code", false, false) 240193323Sed 241218893SdimFunctionPass *llvm::createMachineVerifierPass(const char *Banner) { 242218893Sdim return new MachineVerifierPass(Banner); 243193323Sed} 244193323Sed 245218893Sdimvoid MachineFunction::verify(Pass *p, const char *Banner) const { 246218893Sdim MachineVerifier(p, Banner) 247218893Sdim .runOnMachineFunction(const_cast<MachineFunction&>(*this)); 248199481Srdivacky} 249199481Srdivacky 250198090Srdivackybool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { 251198090Srdivacky raw_ostream *OutFile = 0; 252193323Sed if (OutFileName) { 253198090Srdivacky std::string ErrorInfo; 254198090Srdivacky OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, 255198090Srdivacky raw_fd_ostream::F_Append); 256198090Srdivacky if (!ErrorInfo.empty()) { 257198090Srdivacky errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n'; 258198090Srdivacky exit(1); 259198090Srdivacky } 260198090Srdivacky 261198090Srdivacky OS = OutFile; 262193323Sed } else { 263198090Srdivacky OS = &errs(); 264193323Sed } 265193323Sed 266193323Sed foundErrors = 0; 267193323Sed 268193323Sed this->MF = &MF; 269193323Sed TM = &MF.getTarget(); 270224145Sdim TII = TM->getInstrInfo(); 271193323Sed TRI = TM->getRegisterInfo(); 272193323Sed MRI = &MF.getRegInfo(); 273193323Sed 274212904Sdim LiveVars = NULL; 275212904Sdim LiveInts = NULL; 276218893Sdim LiveStks = NULL; 277218893Sdim Indexes = NULL; 278199511Srdivacky if (PASS) { 279212904Sdim LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>(); 280212904Sdim // We don't want to verify LiveVariables if LiveIntervals is available. 281212904Sdim if (!LiveInts) 282212904Sdim LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>(); 283218893Sdim LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>(); 284218893Sdim Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>(); 285199511Srdivacky } 286199511Srdivacky 287193323Sed visitMachineFunctionBefore(); 288193323Sed for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 289193323Sed MFI!=MFE; ++MFI) { 290193323Sed visitMachineBasicBlockBefore(MFI); 291235633Sdim for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), 292235633Sdim MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) { 293218893Sdim if (MBBI->getParent() != MFI) { 294218893Sdim report("Bad instruction parent pointer", MFI); 295218893Sdim *OS << "Instruction: " << *MBBI; 296218893Sdim continue; 297218893Sdim } 298235633Sdim // Skip BUNDLE instruction for now. FIXME: We should add code to verify 299235633Sdim // the BUNDLE's specifically. 300235633Sdim if (MBBI->isBundle()) 301235633Sdim continue; 302193323Sed visitMachineInstrBefore(MBBI); 303193323Sed for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) 304193323Sed visitMachineOperand(&MBBI->getOperand(I), I); 305193323Sed visitMachineInstrAfter(MBBI); 306193323Sed } 307193323Sed visitMachineBasicBlockAfter(MFI); 308193323Sed } 309193323Sed visitMachineFunctionAfter(); 310193323Sed 311198090Srdivacky if (OutFile) 312198090Srdivacky delete OutFile; 313198090Srdivacky else if (foundErrors) 314207618Srdivacky report_fatal_error("Found "+Twine(foundErrors)+" machine code errors."); 315193323Sed 316198090Srdivacky // Clean up. 317198090Srdivacky regsLive.clear(); 318198090Srdivacky regsDefined.clear(); 319198090Srdivacky regsDead.clear(); 320198090Srdivacky regsKilled.clear(); 321235633Sdim regMasks.clear(); 322198090Srdivacky regsLiveInButUnused.clear(); 323198090Srdivacky MBBInfoMap.clear(); 324193323Sed 325193323Sed return false; // no changes 326193323Sed} 327193323Sed 328198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineFunction *MF) { 329193323Sed assert(MF); 330198090Srdivacky *OS << '\n'; 331218893Sdim if (!foundErrors++) { 332218893Sdim if (Banner) 333218893Sdim *OS << "# " << Banner << '\n'; 334218893Sdim MF->print(*OS, Indexes); 335218893Sdim } 336193323Sed *OS << "*** Bad machine code: " << msg << " ***\n" 337235633Sdim << "- function: " << MF->getFunction()->getName() << "\n"; 338193323Sed} 339193323Sed 340198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { 341193323Sed assert(MBB); 342193323Sed report(msg, MBB->getParent()); 343199989Srdivacky *OS << "- basic block: " << MBB->getName() 344193323Sed << " " << (void*)MBB 345218893Sdim << " (BB#" << MBB->getNumber() << ")"; 346218893Sdim if (Indexes) 347218893Sdim *OS << " [" << Indexes->getMBBStartIdx(MBB) 348218893Sdim << ';' << Indexes->getMBBEndIdx(MBB) << ')'; 349218893Sdim *OS << '\n'; 350193323Sed} 351193323Sed 352198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineInstr *MI) { 353193323Sed assert(MI); 354193323Sed report(msg, MI->getParent()); 355193323Sed *OS << "- instruction: "; 356218893Sdim if (Indexes && Indexes->hasIndex(MI)) 357218893Sdim *OS << Indexes->getInstructionIndex(MI) << '\t'; 358198090Srdivacky MI->print(*OS, TM); 359193323Sed} 360193323Sed 361198090Srdivackyvoid MachineVerifier::report(const char *msg, 362198090Srdivacky const MachineOperand *MO, unsigned MONum) { 363193323Sed assert(MO); 364193323Sed report(msg, MO->getParent()); 365193323Sed *OS << "- operand " << MONum << ": "; 366193323Sed MO->print(*OS, TM); 367193323Sed *OS << "\n"; 368193323Sed} 369193323Sed 370198090Srdivackyvoid MachineVerifier::markReachable(const MachineBasicBlock *MBB) { 371193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 372193323Sed if (!MInfo.reachable) { 373193323Sed MInfo.reachable = true; 374193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 375193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) 376193323Sed markReachable(*SuI); 377193323Sed } 378193323Sed} 379193323Sed 380198090Srdivackyvoid MachineVerifier::visitMachineFunctionBefore() { 381218893Sdim lastIndex = SlotIndex(); 382193323Sed regsReserved = TRI->getReservedRegs(*MF); 383198090Srdivacky 384198090Srdivacky // A sub-register of a reserved register is also reserved 385198090Srdivacky for (int Reg = regsReserved.find_first(); Reg>=0; 386198090Srdivacky Reg = regsReserved.find_next(Reg)) { 387235633Sdim for (const uint16_t *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) { 388198090Srdivacky // FIXME: This should probably be: 389198090Srdivacky // assert(regsReserved.test(*Sub) && "Non-reserved sub-register"); 390198090Srdivacky regsReserved.set(*Sub); 391198090Srdivacky } 392198090Srdivacky } 393235633Sdim 394235633Sdim regsAllocatable = TRI->getAllocatableSet(*MF); 395235633Sdim 396193323Sed markReachable(&MF->front()); 397193323Sed} 398193323Sed 399199481Srdivacky// Does iterator point to a and b as the first two elements? 400207618Srdivackystatic bool matchPair(MachineBasicBlock::const_succ_iterator i, 401207618Srdivacky const MachineBasicBlock *a, const MachineBasicBlock *b) { 402199481Srdivacky if (*i == a) 403199481Srdivacky return *++i == b; 404199481Srdivacky if (*i == b) 405199481Srdivacky return *++i == a; 406199481Srdivacky return false; 407199481Srdivacky} 408199481Srdivacky 409199481Srdivackyvoid 410199481SrdivackyMachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { 411226890Sdim FirstTerminator = 0; 412226890Sdim 413235633Sdim if (MRI->isSSA()) { 414235633Sdim // If this block has allocatable physical registers live-in, check that 415235633Sdim // it is an entry block or landing pad. 416235633Sdim for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 417235633Sdim LE = MBB->livein_end(); 418235633Sdim LI != LE; ++LI) { 419235633Sdim unsigned reg = *LI; 420235633Sdim if (isAllocatable(reg) && !MBB->isLandingPad() && 421235633Sdim MBB != MBB->getParent()->begin()) { 422235633Sdim report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB); 423235633Sdim } 424235633Sdim } 425235633Sdim } 426235633Sdim 427218893Sdim // Count the number of landing pad successors. 428218893Sdim SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs; 429218893Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 430218893Sdim E = MBB->succ_end(); I != E; ++I) { 431218893Sdim if ((*I)->isLandingPad()) 432218893Sdim LandingPadSuccs.insert(*I); 433218893Sdim } 434223017Sdim 435223017Sdim const MCAsmInfo *AsmInfo = TM->getMCAsmInfo(); 436223017Sdim const BasicBlock *BB = MBB->getBasicBlock(); 437223017Sdim if (LandingPadSuccs.size() > 1 && 438223017Sdim !(AsmInfo && 439223017Sdim AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj && 440223017Sdim BB && isa<SwitchInst>(BB->getTerminator()))) 441218893Sdim report("MBB has more than one landing pad successor", MBB); 442218893Sdim 443198090Srdivacky // Call AnalyzeBranch. If it succeeds, there several more conditions to check. 444198090Srdivacky MachineBasicBlock *TBB = 0, *FBB = 0; 445198090Srdivacky SmallVector<MachineOperand, 4> Cond; 446198090Srdivacky if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB), 447198090Srdivacky TBB, FBB, Cond)) { 448198090Srdivacky // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's 449198090Srdivacky // check whether its answers match up with reality. 450198090Srdivacky if (!TBB && !FBB) { 451198090Srdivacky // Block falls through to its successor. 452198090Srdivacky MachineFunction::const_iterator MBBI = MBB; 453198090Srdivacky ++MBBI; 454198090Srdivacky if (MBBI == MF->end()) { 455198090Srdivacky // It's possible that the block legitimately ends with a noreturn 456198090Srdivacky // call or an unreachable, in which case it won't actually fall 457198090Srdivacky // out the bottom of the function. 458218893Sdim } else if (MBB->succ_size() == LandingPadSuccs.size()) { 459198090Srdivacky // It's possible that the block legitimately ends with a noreturn 460198090Srdivacky // call or an unreachable, in which case it won't actuall fall 461198090Srdivacky // out of the block. 462218893Sdim } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 463198090Srdivacky report("MBB exits via unconditional fall-through but doesn't have " 464198090Srdivacky "exactly one CFG successor!", MBB); 465218893Sdim } else if (!MBB->isSuccessor(MBBI)) { 466198090Srdivacky report("MBB exits via unconditional fall-through but its successor " 467198090Srdivacky "differs from its CFG successor!", MBB); 468198090Srdivacky } 469235633Sdim if (!MBB->empty() && MBB->back().isBarrier() && 470210299Sed !TII->isPredicated(&MBB->back())) { 471198090Srdivacky report("MBB exits via unconditional fall-through but ends with a " 472198090Srdivacky "barrier instruction!", MBB); 473198090Srdivacky } 474198090Srdivacky if (!Cond.empty()) { 475198090Srdivacky report("MBB exits via unconditional fall-through but has a condition!", 476198090Srdivacky MBB); 477198090Srdivacky } 478198090Srdivacky } else if (TBB && !FBB && Cond.empty()) { 479198090Srdivacky // Block unconditionally branches somewhere. 480218893Sdim if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 481198090Srdivacky report("MBB exits via unconditional branch but doesn't have " 482198090Srdivacky "exactly one CFG successor!", MBB); 483218893Sdim } else if (!MBB->isSuccessor(TBB)) { 484198090Srdivacky report("MBB exits via unconditional branch but the CFG " 485198090Srdivacky "successor doesn't match the actual successor!", MBB); 486198090Srdivacky } 487198090Srdivacky if (MBB->empty()) { 488198090Srdivacky report("MBB exits via unconditional branch but doesn't contain " 489198090Srdivacky "any instructions!", MBB); 490235633Sdim } else if (!MBB->back().isBarrier()) { 491198090Srdivacky report("MBB exits via unconditional branch but doesn't end with a " 492198090Srdivacky "barrier instruction!", MBB); 493235633Sdim } else if (!MBB->back().isTerminator()) { 494198090Srdivacky report("MBB exits via unconditional branch but the branch isn't a " 495198090Srdivacky "terminator instruction!", MBB); 496198090Srdivacky } 497198090Srdivacky } else if (TBB && !FBB && !Cond.empty()) { 498198090Srdivacky // Block conditionally branches somewhere, otherwise falls through. 499198090Srdivacky MachineFunction::const_iterator MBBI = MBB; 500198090Srdivacky ++MBBI; 501198090Srdivacky if (MBBI == MF->end()) { 502198090Srdivacky report("MBB conditionally falls through out of function!", MBB); 503198090Srdivacky } if (MBB->succ_size() != 2) { 504198090Srdivacky report("MBB exits via conditional branch/fall-through but doesn't have " 505198090Srdivacky "exactly two CFG successors!", MBB); 506199481Srdivacky } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) { 507198090Srdivacky report("MBB exits via conditional branch/fall-through but the CFG " 508198090Srdivacky "successors don't match the actual successors!", MBB); 509198090Srdivacky } 510198090Srdivacky if (MBB->empty()) { 511198090Srdivacky report("MBB exits via conditional branch/fall-through but doesn't " 512198090Srdivacky "contain any instructions!", MBB); 513235633Sdim } else if (MBB->back().isBarrier()) { 514198090Srdivacky report("MBB exits via conditional branch/fall-through but ends with a " 515198090Srdivacky "barrier instruction!", MBB); 516235633Sdim } else if (!MBB->back().isTerminator()) { 517198090Srdivacky report("MBB exits via conditional branch/fall-through but the branch " 518198090Srdivacky "isn't a terminator instruction!", MBB); 519198090Srdivacky } 520198090Srdivacky } else if (TBB && FBB) { 521198090Srdivacky // Block conditionally branches somewhere, otherwise branches 522198090Srdivacky // somewhere else. 523198090Srdivacky if (MBB->succ_size() != 2) { 524198090Srdivacky report("MBB exits via conditional branch/branch but doesn't have " 525198090Srdivacky "exactly two CFG successors!", MBB); 526199481Srdivacky } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) { 527198090Srdivacky report("MBB exits via conditional branch/branch but the CFG " 528198090Srdivacky "successors don't match the actual successors!", MBB); 529198090Srdivacky } 530198090Srdivacky if (MBB->empty()) { 531198090Srdivacky report("MBB exits via conditional branch/branch but doesn't " 532198090Srdivacky "contain any instructions!", MBB); 533235633Sdim } else if (!MBB->back().isBarrier()) { 534198090Srdivacky report("MBB exits via conditional branch/branch but doesn't end with a " 535198090Srdivacky "barrier instruction!", MBB); 536235633Sdim } else if (!MBB->back().isTerminator()) { 537198090Srdivacky report("MBB exits via conditional branch/branch but the branch " 538198090Srdivacky "isn't a terminator instruction!", MBB); 539198090Srdivacky } 540198090Srdivacky if (Cond.empty()) { 541198090Srdivacky report("MBB exits via conditinal branch/branch but there's no " 542198090Srdivacky "condition!", MBB); 543198090Srdivacky } 544198090Srdivacky } else { 545198090Srdivacky report("AnalyzeBranch returned invalid data!", MBB); 546198090Srdivacky } 547198090Srdivacky } 548198090Srdivacky 549193323Sed regsLive.clear(); 550207618Srdivacky for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 551193323Sed E = MBB->livein_end(); I != E; ++I) { 552193323Sed if (!TargetRegisterInfo::isPhysicalRegister(*I)) { 553193323Sed report("MBB live-in list contains non-physical register", MBB); 554193323Sed continue; 555193323Sed } 556193323Sed regsLive.insert(*I); 557235633Sdim for (const uint16_t *R = TRI->getSubRegisters(*I); *R; R++) 558193323Sed regsLive.insert(*R); 559193323Sed } 560198090Srdivacky regsLiveInButUnused = regsLive; 561198090Srdivacky 562198090Srdivacky const MachineFrameInfo *MFI = MF->getFrameInfo(); 563198090Srdivacky assert(MFI && "Function has no frame info"); 564198090Srdivacky BitVector PR = MFI->getPristineRegs(MBB); 565198090Srdivacky for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { 566198090Srdivacky regsLive.insert(I); 567235633Sdim for (const uint16_t *R = TRI->getSubRegisters(I); *R; R++) 568198090Srdivacky regsLive.insert(*R); 569198090Srdivacky } 570198090Srdivacky 571193323Sed regsKilled.clear(); 572193323Sed regsDefined.clear(); 573218893Sdim 574218893Sdim if (Indexes) 575218893Sdim lastIndex = Indexes->getMBBStartIdx(MBB); 576193323Sed} 577193323Sed 578198090Srdivackyvoid MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { 579224145Sdim const MCInstrDesc &MCID = MI->getDesc(); 580224145Sdim if (MI->getNumOperands() < MCID.getNumOperands()) { 581193323Sed report("Too few operands", MI); 582224145Sdim *OS << MCID.getNumOperands() << " operands expected, but " 583193323Sed << MI->getNumExplicitOperands() << " given.\n"; 584193323Sed } 585198090Srdivacky 586198090Srdivacky // Check the MachineMemOperands for basic consistency. 587198090Srdivacky for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 588198090Srdivacky E = MI->memoperands_end(); I != E; ++I) { 589235633Sdim if ((*I)->isLoad() && !MI->mayLoad()) 590198090Srdivacky report("Missing mayLoad flag", MI); 591235633Sdim if ((*I)->isStore() && !MI->mayStore()) 592198090Srdivacky report("Missing mayStore flag", MI); 593193323Sed } 594212904Sdim 595212904Sdim // Debug values must not have a slot index. 596235633Sdim // Other instructions must have one, unless they are inside a bundle. 597212904Sdim if (LiveInts) { 598212904Sdim bool mapped = !LiveInts->isNotInMIMap(MI); 599212904Sdim if (MI->isDebugValue()) { 600212904Sdim if (mapped) 601212904Sdim report("Debug instruction has a slot index", MI); 602235633Sdim } else if (MI->isInsideBundle()) { 603235633Sdim if (mapped) 604235633Sdim report("Instruction inside bundle has a slot index", MI); 605212904Sdim } else { 606212904Sdim if (!mapped) 607212904Sdim report("Missing slot index", MI); 608212904Sdim } 609212904Sdim } 610212904Sdim 611226890Sdim // Ensure non-terminators don't follow terminators. 612235633Sdim // Ignore predicated terminators formed by if conversion. 613235633Sdim // FIXME: If conversion shouldn't need to violate this rule. 614235633Sdim if (MI->isTerminator() && !TII->isPredicated(MI)) { 615226890Sdim if (!FirstTerminator) 616226890Sdim FirstTerminator = MI; 617226890Sdim } else if (FirstTerminator) { 618226890Sdim report("Non-terminator instruction after the first terminator", MI); 619226890Sdim *OS << "First terminator was:\t" << *FirstTerminator; 620226890Sdim } 621226890Sdim 622226890Sdim StringRef ErrorInfo; 623226890Sdim if (!TII->verifyInstruction(MI, ErrorInfo)) 624226890Sdim report(ErrorInfo.data(), MI); 625193323Sed} 626193323Sed 627193323Sedvoid 628198090SrdivackyMachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { 629193323Sed const MachineInstr *MI = MO->getParent(); 630224145Sdim const MCInstrDesc &MCID = MI->getDesc(); 631224145Sdim const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 632193323Sed 633224145Sdim // The first MCID.NumDefs operands must be explicit register defines 634224145Sdim if (MONum < MCID.getNumDefs()) { 635193323Sed if (!MO->isReg()) 636193323Sed report("Explicit definition must be a register", MO, MONum); 637193323Sed else if (!MO->isDef()) 638193323Sed report("Explicit definition marked as use", MO, MONum); 639193323Sed else if (MO->isImplicit()) 640193323Sed report("Explicit definition marked as implicit", MO, MONum); 641224145Sdim } else if (MONum < MCID.getNumOperands()) { 642218893Sdim // Don't check if it's the last operand in a variadic instruction. See, 643218893Sdim // e.g., LDM_RET in the arm back end. 644224145Sdim if (MO->isReg() && 645235633Sdim !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { 646224145Sdim if (MO->isDef() && !MCOI.isOptionalDef()) 647218893Sdim report("Explicit operand marked as def", MO, MONum); 648198090Srdivacky if (MO->isImplicit()) 649198090Srdivacky report("Explicit operand marked as implicit", MO, MONum); 650198090Srdivacky } 651198090Srdivacky } else { 652201360Srdivacky // ARM adds %reg0 operands to indicate predicates. We'll allow that. 653235633Sdim if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg()) 654198090Srdivacky report("Extra explicit operand on non-variadic instruction", MO, MONum); 655193323Sed } 656193323Sed 657193323Sed switch (MO->getType()) { 658193323Sed case MachineOperand::MO_Register: { 659193323Sed const unsigned Reg = MO->getReg(); 660193323Sed if (!Reg) 661193323Sed return; 662235633Sdim if (MRI->tracksLiveness() && !MI->isDebugValue()) 663235633Sdim checkLiveness(MO, MONum); 664193323Sed 665198090Srdivacky 666193323Sed // Check register classes. 667224145Sdim if (MONum < MCID.getNumOperands() && !MO->isImplicit()) { 668193323Sed unsigned SubIdx = MO->getSubReg(); 669193323Sed 670193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 671193323Sed if (SubIdx) { 672226890Sdim report("Illegal subregister index for physical register", MO, MONum); 673226890Sdim return; 674193323Sed } 675224145Sdim if (const TargetRegisterClass *DRC = TII->getRegClass(MCID,MONum,TRI)) { 676226890Sdim if (!DRC->contains(Reg)) { 677193323Sed report("Illegal physical register for instruction", MO, MONum); 678226890Sdim *OS << TRI->getName(Reg) << " is not a " 679193323Sed << DRC->getName() << " register.\n"; 680193323Sed } 681193323Sed } 682193323Sed } else { 683193323Sed // Virtual register. 684193323Sed const TargetRegisterClass *RC = MRI->getRegClass(Reg); 685193323Sed if (SubIdx) { 686226890Sdim const TargetRegisterClass *SRC = 687226890Sdim TRI->getSubClassWithSubReg(RC, SubIdx); 688208599Srdivacky if (!SRC) { 689193323Sed report("Invalid subregister index for virtual register", MO, MONum); 690208599Srdivacky *OS << "Register class " << RC->getName() 691208599Srdivacky << " does not support subreg index " << SubIdx << "\n"; 692193323Sed return; 693193323Sed } 694226890Sdim if (RC != SRC) { 695226890Sdim report("Invalid register class for subregister index", MO, MONum); 696226890Sdim *OS << "Register class " << RC->getName() 697226890Sdim << " does not fully support subreg index " << SubIdx << "\n"; 698226890Sdim return; 699226890Sdim } 700193323Sed } 701224145Sdim if (const TargetRegisterClass *DRC = TII->getRegClass(MCID,MONum,TRI)) { 702226890Sdim if (SubIdx) { 703226890Sdim const TargetRegisterClass *SuperRC = 704226890Sdim TRI->getLargestLegalSuperClass(RC); 705226890Sdim if (!SuperRC) { 706226890Sdim report("No largest legal super class exists.", MO, MONum); 707226890Sdim return; 708226890Sdim } 709226890Sdim DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx); 710226890Sdim if (!DRC) { 711226890Sdim report("No matching super-reg register class.", MO, MONum); 712226890Sdim return; 713226890Sdim } 714226890Sdim } 715223017Sdim if (!RC->hasSuperClassEq(DRC)) { 716193323Sed report("Illegal virtual register for instruction", MO, MONum); 717193323Sed *OS << "Expected a " << DRC->getName() << " register, but got a " 718193323Sed << RC->getName() << " register\n"; 719193323Sed } 720193323Sed } 721193323Sed } 722193323Sed } 723193323Sed break; 724193323Sed } 725198090Srdivacky 726235633Sdim case MachineOperand::MO_RegisterMask: 727235633Sdim regMasks.push_back(MO->getRegMask()); 728235633Sdim break; 729235633Sdim 730198090Srdivacky case MachineOperand::MO_MachineBasicBlock: 731203954Srdivacky if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent())) 732203954Srdivacky report("PHI operand is not in the CFG", MO, MONum); 733198090Srdivacky break; 734198090Srdivacky 735218893Sdim case MachineOperand::MO_FrameIndex: 736218893Sdim if (LiveStks && LiveStks->hasInterval(MO->getIndex()) && 737218893Sdim LiveInts && !LiveInts->isNotInMIMap(MI)) { 738218893Sdim LiveInterval &LI = LiveStks->getInterval(MO->getIndex()); 739218893Sdim SlotIndex Idx = LiveInts->getInstructionIndex(MI); 740235633Sdim if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) { 741218893Sdim report("Instruction loads from dead spill slot", MO, MONum); 742218893Sdim *OS << "Live stack: " << LI << '\n'; 743218893Sdim } 744235633Sdim if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) { 745218893Sdim report("Instruction stores to dead spill slot", MO, MONum); 746218893Sdim *OS << "Live stack: " << LI << '\n'; 747218893Sdim } 748218893Sdim } 749218893Sdim break; 750218893Sdim 751193323Sed default: 752193323Sed break; 753193323Sed } 754193323Sed} 755193323Sed 756235633Sdimvoid MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { 757235633Sdim const MachineInstr *MI = MO->getParent(); 758235633Sdim const unsigned Reg = MO->getReg(); 759235633Sdim 760235633Sdim // Both use and def operands can read a register. 761235633Sdim if (MO->readsReg()) { 762235633Sdim regsLiveInButUnused.erase(Reg); 763235633Sdim 764235633Sdim bool isKill = false; 765235633Sdim unsigned defIdx; 766235633Sdim if (MI->isRegTiedToDefOperand(MONum, &defIdx)) { 767235633Sdim // A two-addr use counts as a kill if use and def are the same. 768235633Sdim unsigned DefReg = MI->getOperand(defIdx).getReg(); 769235633Sdim if (Reg == DefReg) 770235633Sdim isKill = true; 771235633Sdim else if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 772235633Sdim report("Two-address instruction operands must be identical", MO, MONum); 773235633Sdim } 774235633Sdim } else 775235633Sdim isKill = MO->isKill(); 776235633Sdim 777235633Sdim if (isKill) 778235633Sdim addRegWithSubRegs(regsKilled, Reg); 779235633Sdim 780235633Sdim // Check that LiveVars knows this kill. 781235633Sdim if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) && 782235633Sdim MO->isKill()) { 783235633Sdim LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 784235633Sdim if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end()) 785235633Sdim report("Kill missing from LiveVariables", MO, MONum); 786235633Sdim } 787235633Sdim 788235633Sdim // Check LiveInts liveness and kill. 789235633Sdim if (TargetRegisterInfo::isVirtualRegister(Reg) && 790235633Sdim LiveInts && !LiveInts->isNotInMIMap(MI)) { 791235633Sdim SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getRegSlot(true); 792235633Sdim if (LiveInts->hasInterval(Reg)) { 793235633Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 794235633Sdim if (!LI.liveAt(UseIdx)) { 795235633Sdim report("No live range at use", MO, MONum); 796235633Sdim *OS << UseIdx << " is not live in " << LI << '\n'; 797235633Sdim } 798235633Sdim // Check for extra kill flags. 799235633Sdim // Note that we allow missing kill flags for now. 800235633Sdim if (MO->isKill() && !LI.killedAt(UseIdx.getRegSlot())) { 801235633Sdim report("Live range continues after kill flag", MO, MONum); 802235633Sdim *OS << "Live range: " << LI << '\n'; 803235633Sdim } 804235633Sdim } else { 805235633Sdim report("Virtual register has no Live interval", MO, MONum); 806235633Sdim } 807235633Sdim } 808235633Sdim 809235633Sdim // Use of a dead register. 810235633Sdim if (!regsLive.count(Reg)) { 811235633Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 812235633Sdim // Reserved registers may be used even when 'dead'. 813235633Sdim if (!isReserved(Reg)) 814235633Sdim report("Using an undefined physical register", MO, MONum); 815235633Sdim } else { 816235633Sdim BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 817235633Sdim // We don't know which virtual registers are live in, so only complain 818235633Sdim // if vreg was killed in this MBB. Otherwise keep track of vregs that 819235633Sdim // must be live in. PHI instructions are handled separately. 820235633Sdim if (MInfo.regsKilled.count(Reg)) 821235633Sdim report("Using a killed virtual register", MO, MONum); 822235633Sdim else if (!MI->isPHI()) 823235633Sdim MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 824235633Sdim } 825235633Sdim } 826235633Sdim } 827235633Sdim 828235633Sdim if (MO->isDef()) { 829235633Sdim // Register defined. 830235633Sdim // TODO: verify that earlyclobber ops are not used. 831235633Sdim if (MO->isDead()) 832235633Sdim addRegWithSubRegs(regsDead, Reg); 833235633Sdim else 834235633Sdim addRegWithSubRegs(regsDefined, Reg); 835235633Sdim 836235633Sdim // Verify SSA form. 837235633Sdim if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) && 838235633Sdim llvm::next(MRI->def_begin(Reg)) != MRI->def_end()) 839235633Sdim report("Multiple virtual register defs in SSA form", MO, MONum); 840235633Sdim 841235633Sdim // Check LiveInts for a live range, but only for virtual registers. 842235633Sdim if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) && 843235633Sdim !LiveInts->isNotInMIMap(MI)) { 844235633Sdim SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getRegSlot(); 845235633Sdim if (LiveInts->hasInterval(Reg)) { 846235633Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 847235633Sdim if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) { 848235633Sdim assert(VNI && "NULL valno is not allowed"); 849235633Sdim if (VNI->def != DefIdx && !MO->isEarlyClobber()) { 850235633Sdim report("Inconsistent valno->def", MO, MONum); 851235633Sdim *OS << "Valno " << VNI->id << " is not defined at " 852235633Sdim << DefIdx << " in " << LI << '\n'; 853235633Sdim } 854235633Sdim } else { 855235633Sdim report("No live range at def", MO, MONum); 856235633Sdim *OS << DefIdx << " is not live in " << LI << '\n'; 857235633Sdim } 858235633Sdim } else { 859235633Sdim report("Virtual register has no Live interval", MO, MONum); 860235633Sdim } 861235633Sdim } 862235633Sdim } 863235633Sdim} 864235633Sdim 865198090Srdivackyvoid MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { 866193323Sed BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 867193323Sed set_union(MInfo.regsKilled, regsKilled); 868212904Sdim set_subtract(regsLive, regsKilled); regsKilled.clear(); 869235633Sdim // Kill any masked registers. 870235633Sdim while (!regMasks.empty()) { 871235633Sdim const uint32_t *Mask = regMasks.pop_back_val(); 872235633Sdim for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I) 873235633Sdim if (TargetRegisterInfo::isPhysicalRegister(*I) && 874235633Sdim MachineOperand::clobbersPhysReg(Mask, *I)) 875235633Sdim regsDead.push_back(*I); 876235633Sdim } 877212904Sdim set_subtract(regsLive, regsDead); regsDead.clear(); 878212904Sdim set_union(regsLive, regsDefined); regsDefined.clear(); 879218893Sdim 880218893Sdim if (Indexes && Indexes->hasIndex(MI)) { 881218893Sdim SlotIndex idx = Indexes->getInstructionIndex(MI); 882218893Sdim if (!(idx > lastIndex)) { 883218893Sdim report("Instruction index out of order", MI); 884218893Sdim *OS << "Last instruction was at " << lastIndex << '\n'; 885218893Sdim } 886218893Sdim lastIndex = idx; 887218893Sdim } 888193323Sed} 889193323Sed 890193323Sedvoid 891198090SrdivackyMachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { 892193323Sed MBBInfoMap[MBB].regsLiveOut = regsLive; 893193323Sed regsLive.clear(); 894218893Sdim 895218893Sdim if (Indexes) { 896218893Sdim SlotIndex stop = Indexes->getMBBEndIdx(MBB); 897218893Sdim if (!(stop > lastIndex)) { 898218893Sdim report("Block ends before last instruction index", MBB); 899218893Sdim *OS << "Block ends at " << stop 900218893Sdim << " last instruction was at " << lastIndex << '\n'; 901218893Sdim } 902218893Sdim lastIndex = stop; 903218893Sdim } 904193323Sed} 905193323Sed 906193323Sed// Calculate the largest possible vregsPassed sets. These are the registers that 907193323Sed// can pass through an MBB live, but may not be live every time. It is assumed 908193323Sed// that all vregsPassed sets are empty before the call. 909202375Srdivackyvoid MachineVerifier::calcRegsPassed() { 910193323Sed // First push live-out regs to successors' vregsPassed. Remember the MBBs that 911193323Sed // have any vregsPassed. 912235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> todo; 913193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 914193323Sed MFI != MFE; ++MFI) { 915193323Sed const MachineBasicBlock &MBB(*MFI); 916193323Sed BBInfo &MInfo = MBBInfoMap[&MBB]; 917193323Sed if (!MInfo.reachable) 918193323Sed continue; 919193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 920193323Sed SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 921193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 922193323Sed if (SInfo.addPassed(MInfo.regsLiveOut)) 923193323Sed todo.insert(*SuI); 924193323Sed } 925193323Sed } 926193323Sed 927193323Sed // Iteratively push vregsPassed to successors. This will converge to the same 928193323Sed // final state regardless of DenseSet iteration order. 929193323Sed while (!todo.empty()) { 930193323Sed const MachineBasicBlock *MBB = *todo.begin(); 931193323Sed todo.erase(MBB); 932193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 933193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 934193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 935193323Sed if (*SuI == MBB) 936193323Sed continue; 937193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 938193323Sed if (SInfo.addPassed(MInfo.vregsPassed)) 939193323Sed todo.insert(*SuI); 940193323Sed } 941193323Sed } 942193323Sed} 943193323Sed 944199511Srdivacky// Calculate the set of virtual registers that must be passed through each basic 945199511Srdivacky// block in order to satisfy the requirements of successor blocks. This is very 946202375Srdivacky// similar to calcRegsPassed, only backwards. 947199511Srdivackyvoid MachineVerifier::calcRegsRequired() { 948199511Srdivacky // First push live-in regs to predecessors' vregsRequired. 949235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> todo; 950199511Srdivacky for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 951199511Srdivacky MFI != MFE; ++MFI) { 952199511Srdivacky const MachineBasicBlock &MBB(*MFI); 953199511Srdivacky BBInfo &MInfo = MBBInfoMap[&MBB]; 954199511Srdivacky for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(), 955199511Srdivacky PrE = MBB.pred_end(); PrI != PrE; ++PrI) { 956199511Srdivacky BBInfo &PInfo = MBBInfoMap[*PrI]; 957199511Srdivacky if (PInfo.addRequired(MInfo.vregsLiveIn)) 958199511Srdivacky todo.insert(*PrI); 959199511Srdivacky } 960199511Srdivacky } 961199511Srdivacky 962199511Srdivacky // Iteratively push vregsRequired to predecessors. This will converge to the 963199511Srdivacky // same final state regardless of DenseSet iteration order. 964199511Srdivacky while (!todo.empty()) { 965199511Srdivacky const MachineBasicBlock *MBB = *todo.begin(); 966199511Srdivacky todo.erase(MBB); 967199511Srdivacky BBInfo &MInfo = MBBInfoMap[MBB]; 968199511Srdivacky for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 969199511Srdivacky PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 970199511Srdivacky if (*PrI == MBB) 971199511Srdivacky continue; 972199511Srdivacky BBInfo &SInfo = MBBInfoMap[*PrI]; 973199511Srdivacky if (SInfo.addRequired(MInfo.vregsRequired)) 974199511Srdivacky todo.insert(*PrI); 975199511Srdivacky } 976199511Srdivacky } 977199511Srdivacky} 978199511Srdivacky 979193323Sed// Check PHI instructions at the beginning of MBB. It is assumed that 980202375Srdivacky// calcRegsPassed has been run so BBInfo::isLiveOut is valid. 981198090Srdivackyvoid MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) { 982235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> seen; 983193323Sed for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 984203954Srdivacky BBI != BBE && BBI->isPHI(); ++BBI) { 985235633Sdim seen.clear(); 986193323Sed 987193323Sed for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 988193323Sed unsigned Reg = BBI->getOperand(i).getReg(); 989193323Sed const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB(); 990193323Sed if (!Pre->isSuccessor(MBB)) 991193323Sed continue; 992193323Sed seen.insert(Pre); 993193323Sed BBInfo &PrInfo = MBBInfoMap[Pre]; 994193323Sed if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 995193323Sed report("PHI operand is not live-out from predecessor", 996193323Sed &BBI->getOperand(i), i); 997193323Sed } 998193323Sed 999193323Sed // Did we see all predecessors? 1000193323Sed for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1001193323Sed PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1002193323Sed if (!seen.count(*PrI)) { 1003193323Sed report("Missing PHI operand", BBI); 1004198892Srdivacky *OS << "BB#" << (*PrI)->getNumber() 1005193323Sed << " is a predecessor according to the CFG.\n"; 1006193323Sed } 1007193323Sed } 1008193323Sed } 1009193323Sed} 1010193323Sed 1011198090Srdivackyvoid MachineVerifier::visitMachineFunctionAfter() { 1012202375Srdivacky calcRegsPassed(); 1013193323Sed 1014193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1015193323Sed MFI != MFE; ++MFI) { 1016193323Sed BBInfo &MInfo = MBBInfoMap[MFI]; 1017193323Sed 1018193323Sed // Skip unreachable MBBs. 1019193323Sed if (!MInfo.reachable) 1020193323Sed continue; 1021193323Sed 1022202375Srdivacky checkPHIOps(MFI); 1023193323Sed } 1024193323Sed 1025212904Sdim // Now check liveness info if available 1026235633Sdim calcRegsRequired(); 1027235633Sdim 1028235633Sdim if (MRI->isSSA() && !MF->empty()) { 1029235633Sdim BBInfo &MInfo = MBBInfoMap[&MF->front()]; 1030235633Sdim for (RegSet::iterator 1031235633Sdim I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1032235633Sdim ++I) 1033235633Sdim report("Virtual register def doesn't dominate all uses.", 1034235633Sdim MRI->getVRegDef(*I)); 1035235633Sdim } 1036235633Sdim 1037212904Sdim if (LiveVars) 1038199511Srdivacky verifyLiveVariables(); 1039212904Sdim if (LiveInts) 1040212904Sdim verifyLiveIntervals(); 1041193323Sed} 1042199511Srdivacky 1043199511Srdivackyvoid MachineVerifier::verifyLiveVariables() { 1044199511Srdivacky assert(LiveVars && "Don't call verifyLiveVariables without LiveVars"); 1045218893Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1046218893Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1047199511Srdivacky LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1048199511Srdivacky for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1049199511Srdivacky MFI != MFE; ++MFI) { 1050199511Srdivacky BBInfo &MInfo = MBBInfoMap[MFI]; 1051199511Srdivacky 1052199511Srdivacky // Our vregsRequired should be identical to LiveVariables' AliveBlocks 1053199511Srdivacky if (MInfo.vregsRequired.count(Reg)) { 1054199511Srdivacky if (!VI.AliveBlocks.test(MFI->getNumber())) { 1055199511Srdivacky report("LiveVariables: Block missing from AliveBlocks", MFI); 1056218893Sdim *OS << "Virtual register " << PrintReg(Reg) 1057199511Srdivacky << " must be live through the block.\n"; 1058199511Srdivacky } 1059199511Srdivacky } else { 1060199511Srdivacky if (VI.AliveBlocks.test(MFI->getNumber())) { 1061199511Srdivacky report("LiveVariables: Block should not be in AliveBlocks", MFI); 1062218893Sdim *OS << "Virtual register " << PrintReg(Reg) 1063199511Srdivacky << " is not needed live through the block.\n"; 1064199511Srdivacky } 1065199511Srdivacky } 1066199511Srdivacky } 1067199511Srdivacky } 1068199511Srdivacky} 1069199511Srdivacky 1070212904Sdimvoid MachineVerifier::verifyLiveIntervals() { 1071212904Sdim assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts"); 1072212904Sdim for (LiveIntervals::const_iterator LVI = LiveInts->begin(), 1073212904Sdim LVE = LiveInts->end(); LVI != LVE; ++LVI) { 1074212904Sdim const LiveInterval &LI = *LVI->second; 1075218893Sdim 1076218893Sdim // Spilling and splitting may leave unused registers around. Skip them. 1077218893Sdim if (MRI->use_empty(LI.reg)) 1078218893Sdim continue; 1079218893Sdim 1080218893Sdim // Physical registers have much weirdness going on, mostly from coalescing. 1081218893Sdim // We should probably fix it, but for now just ignore them. 1082218893Sdim if (TargetRegisterInfo::isPhysicalRegister(LI.reg)) 1083218893Sdim continue; 1084218893Sdim 1085212904Sdim assert(LVI->first == LI.reg && "Invalid reg to interval mapping"); 1086199511Srdivacky 1087212904Sdim for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 1088212904Sdim I!=E; ++I) { 1089212904Sdim VNInfo *VNI = *I; 1090218893Sdim const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def); 1091212904Sdim 1092218893Sdim if (!DefVNI) { 1093212904Sdim if (!VNI->isUnused()) { 1094212904Sdim report("Valno not live at def and not marked unused", MF); 1095212904Sdim *OS << "Valno #" << VNI->id << " in " << LI << '\n'; 1096212904Sdim } 1097212904Sdim continue; 1098212904Sdim } 1099212904Sdim 1100212904Sdim if (VNI->isUnused()) 1101212904Sdim continue; 1102212904Sdim 1103218893Sdim if (DefVNI != VNI) { 1104212904Sdim report("Live range at def has different valno", MF); 1105218893Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1106218893Sdim << " where valno #" << DefVNI->id << " is live in " << LI << '\n'; 1107218893Sdim continue; 1108212904Sdim } 1109212904Sdim 1110218893Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); 1111218893Sdim if (!MBB) { 1112218893Sdim report("Invalid definition index", MF); 1113218893Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1114218893Sdim << " in " << LI << '\n'; 1115218893Sdim continue; 1116218893Sdim } 1117218893Sdim 1118218893Sdim if (VNI->isPHIDef()) { 1119218893Sdim if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { 1120218893Sdim report("PHIDef value is not defined at MBB start", MF); 1121218893Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1122218893Sdim << ", not at the beginning of BB#" << MBB->getNumber() 1123218893Sdim << " in " << LI << '\n'; 1124218893Sdim } 1125218893Sdim } else { 1126218893Sdim // Non-PHI def. 1127218893Sdim const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); 1128218893Sdim if (!MI) { 1129218893Sdim report("No instruction at def index", MF); 1130218893Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1131218893Sdim << " in " << LI << '\n'; 1132235633Sdim continue; 1133218893Sdim } 1134218893Sdim 1135235633Sdim bool hasDef = false; 1136218893Sdim bool isEarlyClobber = false; 1137235633Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1138235633Sdim if (!MOI->isReg() || !MOI->isDef()) 1139235633Sdim continue; 1140235633Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1141235633Sdim if (MOI->getReg() != LI.reg) 1142235633Sdim continue; 1143235633Sdim } else { 1144235633Sdim if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || 1145235633Sdim !TRI->regsOverlap(LI.reg, MOI->getReg())) 1146235633Sdim continue; 1147218893Sdim } 1148235633Sdim hasDef = true; 1149235633Sdim if (MOI->isEarlyClobber()) 1150235633Sdim isEarlyClobber = true; 1151218893Sdim } 1152218893Sdim 1153235633Sdim if (!hasDef) { 1154235633Sdim report("Defining instruction does not modify register", MI); 1155235633Sdim *OS << "Valno #" << VNI->id << " in " << LI << '\n'; 1156235633Sdim } 1157235633Sdim 1158218893Sdim // Early clobber defs begin at USE slots, but other defs must begin at 1159218893Sdim // DEF slots. 1160218893Sdim if (isEarlyClobber) { 1161235633Sdim if (!VNI->def.isEarlyClobber()) { 1162235633Sdim report("Early clobber def must be at an early-clobber slot", MF); 1163218893Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1164218893Sdim << " in " << LI << '\n'; 1165218893Sdim } 1166235633Sdim } else if (!VNI->def.isRegister()) { 1167235633Sdim report("Non-PHI, non-early clobber def must be at a register slot", 1168235633Sdim MF); 1169218893Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1170218893Sdim << " in " << LI << '\n'; 1171218893Sdim } 1172218893Sdim } 1173212904Sdim } 1174212904Sdim 1175212904Sdim for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) { 1176218893Sdim const VNInfo *VNI = I->valno; 1177218893Sdim assert(VNI && "Live range has no valno"); 1178212904Sdim 1179218893Sdim if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) { 1180212904Sdim report("Foreign valno in live range", MF); 1181218893Sdim I->print(*OS); 1182212904Sdim *OS << " has a valno not in " << LI << '\n'; 1183212904Sdim } 1184212904Sdim 1185218893Sdim if (VNI->isUnused()) { 1186212904Sdim report("Live range valno is marked unused", MF); 1187218893Sdim I->print(*OS); 1188212904Sdim *OS << " in " << LI << '\n'; 1189212904Sdim } 1190212904Sdim 1191218893Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start); 1192218893Sdim if (!MBB) { 1193218893Sdim report("Bad start of live segment, no basic block", MF); 1194218893Sdim I->print(*OS); 1195218893Sdim *OS << " in " << LI << '\n'; 1196218893Sdim continue; 1197218893Sdim } 1198218893Sdim SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB); 1199218893Sdim if (I->start != MBBStartIdx && I->start != VNI->def) { 1200218893Sdim report("Live segment must begin at MBB entry or valno def", MBB); 1201218893Sdim I->print(*OS); 1202218893Sdim *OS << " in " << LI << '\n' << "Basic block starts at " 1203218893Sdim << MBBStartIdx << '\n'; 1204218893Sdim } 1205218893Sdim 1206218893Sdim const MachineBasicBlock *EndMBB = 1207218893Sdim LiveInts->getMBBFromIndex(I->end.getPrevSlot()); 1208218893Sdim if (!EndMBB) { 1209218893Sdim report("Bad end of live segment, no basic block", MF); 1210218893Sdim I->print(*OS); 1211218893Sdim *OS << " in " << LI << '\n'; 1212218893Sdim continue; 1213218893Sdim } 1214235633Sdim 1215235633Sdim // No more checks for live-out segments. 1216235633Sdim if (I->end == LiveInts->getMBBEndIdx(EndMBB)) 1217235633Sdim continue; 1218235633Sdim 1219235633Sdim // The live segment is ending inside EndMBB 1220235633Sdim const MachineInstr *MI = 1221235633Sdim LiveInts->getInstructionFromIndex(I->end.getPrevSlot()); 1222235633Sdim if (!MI) { 1223235633Sdim report("Live segment doesn't end at a valid instruction", EndMBB); 1224218893Sdim I->print(*OS); 1225218893Sdim *OS << " in " << LI << '\n' << "Basic block starts at " 1226235633Sdim << MBBStartIdx << '\n'; 1227235633Sdim continue; 1228235633Sdim } 1229218893Sdim 1230235633Sdim // The block slot must refer to a basic block boundary. 1231235633Sdim if (I->end.isBlock()) { 1232235633Sdim report("Live segment ends at B slot of an instruction", MI); 1233235633Sdim I->print(*OS); 1234235633Sdim *OS << " in " << LI << '\n'; 1235235633Sdim } 1236235633Sdim 1237235633Sdim if (I->end.isDead()) { 1238235633Sdim // Segment ends on the dead slot. 1239235633Sdim // That means there must be a dead def. 1240235633Sdim if (!SlotIndex::isSameInstr(I->start, I->end)) { 1241235633Sdim report("Live segment ending at dead slot spans instructions", MI); 1242235633Sdim I->print(*OS); 1243235633Sdim *OS << " in " << LI << '\n'; 1244235633Sdim } 1245235633Sdim } 1246235633Sdim 1247235633Sdim // A live segment can only end at an early-clobber slot if it is being 1248235633Sdim // redefined by an early-clobber def. 1249235633Sdim if (I->end.isEarlyClobber()) { 1250235633Sdim if (I+1 == E || (I+1)->start != I->end) { 1251235633Sdim report("Live segment ending at early clobber slot must be " 1252235633Sdim "redefined by an EC def in the same instruction", MI); 1253235633Sdim I->print(*OS); 1254235633Sdim *OS << " in " << LI << '\n'; 1255235633Sdim } 1256235633Sdim } 1257235633Sdim 1258235633Sdim // The following checks only apply to virtual registers. Physreg liveness 1259235633Sdim // is too weird to check. 1260235633Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1261235633Sdim // A live range can end with either a redefinition, a kill flag on a 1262235633Sdim // use, or a dead flag on a def. 1263235633Sdim bool hasRead = false; 1264235633Sdim bool hasDeadDef = false; 1265235633Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1266235633Sdim if (!MOI->isReg() || MOI->getReg() != LI.reg) 1267235633Sdim continue; 1268235633Sdim if (MOI->readsReg()) 1269235633Sdim hasRead = true; 1270235633Sdim if (MOI->isDef() && MOI->isDead()) 1271235633Sdim hasDeadDef = true; 1272235633Sdim } 1273235633Sdim 1274235633Sdim if (I->end.isDead()) { 1275218893Sdim if (!hasDeadDef) { 1276235633Sdim report("Instruction doesn't have a dead def operand", MI); 1277218893Sdim I->print(*OS); 1278218893Sdim *OS << " in " << LI << '\n'; 1279218893Sdim } 1280235633Sdim } else { 1281235633Sdim if (!hasRead) { 1282235633Sdim report("Instruction ending live range doesn't read the register", 1283235633Sdim MI); 1284235633Sdim I->print(*OS); 1285235633Sdim *OS << " in " << LI << '\n'; 1286235633Sdim } 1287218893Sdim } 1288218893Sdim } 1289218893Sdim 1290218893Sdim // Now check all the basic blocks in this live segment. 1291218893Sdim MachineFunction::const_iterator MFI = MBB; 1292218893Sdim // Is this live range the beginning of a non-PHIDef VN? 1293218893Sdim if (I->start == VNI->def && !VNI->isPHIDef()) { 1294218893Sdim // Not live-in to any blocks. 1295218893Sdim if (MBB == EndMBB) 1296218893Sdim continue; 1297218893Sdim // Skip this block. 1298218893Sdim ++MFI; 1299218893Sdim } 1300218893Sdim for (;;) { 1301218893Sdim assert(LiveInts->isLiveInToMBB(LI, MFI)); 1302218893Sdim // We don't know how to track physregs into a landing pad. 1303218893Sdim if (TargetRegisterInfo::isPhysicalRegister(LI.reg) && 1304218893Sdim MFI->isLandingPad()) { 1305218893Sdim if (&*MFI == EndMBB) 1306218893Sdim break; 1307218893Sdim ++MFI; 1308218893Sdim continue; 1309218893Sdim } 1310218893Sdim // Check that VNI is live-out of all predecessors. 1311218893Sdim for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(), 1312218893Sdim PE = MFI->pred_end(); PI != PE; ++PI) { 1313235633Sdim SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI); 1314235633Sdim const VNInfo *PVNI = LI.getVNInfoBefore(PEnd); 1315218893Sdim 1316226890Sdim if (VNI->isPHIDef() && VNI->def == LiveInts->getMBBStartIdx(MFI)) 1317218893Sdim continue; 1318218893Sdim 1319218893Sdim if (!PVNI) { 1320218893Sdim report("Register not marked live out of predecessor", *PI); 1321218893Sdim *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber() 1322235633Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before " 1323218893Sdim << PEnd << " in " << LI << '\n'; 1324218893Sdim continue; 1325218893Sdim } 1326218893Sdim 1327218893Sdim if (PVNI != VNI) { 1328218893Sdim report("Different value live out of predecessor", *PI); 1329218893Sdim *OS << "Valno #" << PVNI->id << " live out of BB#" 1330218893Sdim << (*PI)->getNumber() << '@' << PEnd 1331218893Sdim << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber() 1332218893Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << " in " << LI << '\n'; 1333218893Sdim } 1334218893Sdim } 1335218893Sdim if (&*MFI == EndMBB) 1336218893Sdim break; 1337218893Sdim ++MFI; 1338218893Sdim } 1339212904Sdim } 1340218893Sdim 1341218893Sdim // Check the LI only has one connected component. 1342218893Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1343218893Sdim ConnectedVNInfoEqClasses ConEQ(*LiveInts); 1344218893Sdim unsigned NumComp = ConEQ.Classify(&LI); 1345218893Sdim if (NumComp > 1) { 1346218893Sdim report("Multiple connected components in live interval", MF); 1347218893Sdim *OS << NumComp << " components in " << LI << '\n'; 1348218893Sdim for (unsigned comp = 0; comp != NumComp; ++comp) { 1349218893Sdim *OS << comp << ": valnos"; 1350218893Sdim for (LiveInterval::const_vni_iterator I = LI.vni_begin(), 1351218893Sdim E = LI.vni_end(); I!=E; ++I) 1352218893Sdim if (comp == ConEQ.getEqClass(*I)) 1353218893Sdim *OS << ' ' << (*I)->id; 1354218893Sdim *OS << '\n'; 1355218893Sdim } 1356218893Sdim } 1357218893Sdim } 1358212904Sdim } 1359212904Sdim} 1360212904Sdim 1361