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 26252723Sdim#include "llvm/CodeGen/Passes.h" 27252723Sdim#include "llvm/ADT/DenseSet.h" 28263509Sdim#include "llvm/ADT/DepthFirstIterator.h" 29252723Sdim#include "llvm/ADT/SetOperations.h" 30252723Sdim#include "llvm/ADT/SmallVector.h" 31212904Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 32252723Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 33193323Sed#include "llvm/CodeGen/LiveVariables.h" 34252723Sdim#include "llvm/CodeGen/MachineFrameInfo.h" 35252723Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 36235633Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 37198090Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 38193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 39252723Sdim#include "llvm/IR/BasicBlock.h" 40252723Sdim#include "llvm/IR/InlineAsm.h" 41252723Sdim#include "llvm/IR/Instructions.h" 42223017Sdim#include "llvm/MC/MCAsmInfo.h" 43193323Sed#include "llvm/Support/Debug.h" 44198090Srdivacky#include "llvm/Support/ErrorHandling.h" 45198090Srdivacky#include "llvm/Support/raw_ostream.h" 46252723Sdim#include "llvm/Target/TargetInstrInfo.h" 47252723Sdim#include "llvm/Target/TargetMachine.h" 48252723Sdim#include "llvm/Target/TargetRegisterInfo.h" 49193323Sedusing namespace llvm; 50193323Sed 51193323Sednamespace { 52199511Srdivacky struct MachineVerifier { 53193323Sed 54218893Sdim MachineVerifier(Pass *pass, const char *b) : 55199511Srdivacky PASS(pass), 56218893Sdim Banner(b), 57193323Sed OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) 58199511Srdivacky {} 59193323Sed 60193323Sed bool runOnMachineFunction(MachineFunction &MF); 61193323Sed 62199511Srdivacky Pass *const PASS; 63218893Sdim const char *Banner; 64193323Sed const char *const OutFileName; 65198090Srdivacky raw_ostream *OS; 66193323Sed const MachineFunction *MF; 67193323Sed const TargetMachine *TM; 68224145Sdim const TargetInstrInfo *TII; 69193323Sed const TargetRegisterInfo *TRI; 70193323Sed const MachineRegisterInfo *MRI; 71193323Sed 72193323Sed unsigned foundErrors; 73193323Sed 74193323Sed typedef SmallVector<unsigned, 16> RegVector; 75235633Sdim typedef SmallVector<const uint32_t*, 4> RegMaskVector; 76193323Sed typedef DenseSet<unsigned> RegSet; 77193323Sed typedef DenseMap<unsigned, const MachineInstr*> RegMap; 78245431Sdim typedef SmallPtrSet<const MachineBasicBlock*, 8> BlockSet; 79193323Sed 80226890Sdim const MachineInstr *FirstTerminator; 81245431Sdim BlockSet FunctionBlocks; 82226890Sdim 83193323Sed BitVector regsReserved; 84193323Sed RegSet regsLive; 85198090Srdivacky RegVector regsDefined, regsDead, regsKilled; 86235633Sdim RegMaskVector regMasks; 87198090Srdivacky RegSet regsLiveInButUnused; 88193323Sed 89218893Sdim SlotIndex lastIndex; 90218893Sdim 91193323Sed // Add Reg and any sub-registers to RV 92193323Sed void addRegWithSubRegs(RegVector &RV, unsigned Reg) { 93193323Sed RV.push_back(Reg); 94193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) 95245431Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 96245431Sdim RV.push_back(*SubRegs); 97193323Sed } 98193323Sed 99193323Sed struct BBInfo { 100193323Sed // Is this MBB reachable from the MF entry point? 101193323Sed bool reachable; 102193323Sed 103193323Sed // Vregs that must be live in because they are used without being 104193323Sed // defined. Map value is the user. 105193323Sed RegMap vregsLiveIn; 106193323Sed 107193323Sed // Regs killed in MBB. They may be defined again, and will then be in both 108193323Sed // regsKilled and regsLiveOut. 109193323Sed RegSet regsKilled; 110193323Sed 111193323Sed // Regs defined in MBB and live out. Note that vregs passing through may 112193323Sed // be live out without being mentioned here. 113193323Sed RegSet regsLiveOut; 114193323Sed 115193323Sed // Vregs that pass through MBB untouched. This set is disjoint from 116193323Sed // regsKilled and regsLiveOut. 117193323Sed RegSet vregsPassed; 118193323Sed 119199511Srdivacky // Vregs that must pass through MBB because they are needed by a successor 120199511Srdivacky // block. This set is disjoint from regsLiveOut. 121199511Srdivacky RegSet vregsRequired; 122199511Srdivacky 123245431Sdim // Set versions of block's predecessor and successor lists. 124245431Sdim BlockSet Preds, Succs; 125245431Sdim 126193323Sed BBInfo() : reachable(false) {} 127193323Sed 128193323Sed // Add register to vregsPassed if it belongs there. Return true if 129193323Sed // anything changed. 130193323Sed bool addPassed(unsigned Reg) { 131193323Sed if (!TargetRegisterInfo::isVirtualRegister(Reg)) 132193323Sed return false; 133193323Sed if (regsKilled.count(Reg) || regsLiveOut.count(Reg)) 134193323Sed return false; 135193323Sed return vregsPassed.insert(Reg).second; 136193323Sed } 137193323Sed 138193323Sed // Same for a full set. 139193323Sed bool addPassed(const RegSet &RS) { 140193323Sed bool changed = false; 141193323Sed for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 142193323Sed if (addPassed(*I)) 143193323Sed changed = true; 144193323Sed return changed; 145193323Sed } 146193323Sed 147199511Srdivacky // Add register to vregsRequired if it belongs there. Return true if 148199511Srdivacky // anything changed. 149199511Srdivacky bool addRequired(unsigned Reg) { 150199511Srdivacky if (!TargetRegisterInfo::isVirtualRegister(Reg)) 151199511Srdivacky return false; 152199511Srdivacky if (regsLiveOut.count(Reg)) 153199511Srdivacky return false; 154199511Srdivacky return vregsRequired.insert(Reg).second; 155199511Srdivacky } 156199511Srdivacky 157199511Srdivacky // Same for a full set. 158199511Srdivacky bool addRequired(const RegSet &RS) { 159199511Srdivacky bool changed = false; 160199511Srdivacky for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 161199511Srdivacky if (addRequired(*I)) 162199511Srdivacky changed = true; 163199511Srdivacky return changed; 164199511Srdivacky } 165199511Srdivacky 166199511Srdivacky // Same for a full map. 167199511Srdivacky bool addRequired(const RegMap &RM) { 168199511Srdivacky bool changed = false; 169199511Srdivacky for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I) 170199511Srdivacky if (addRequired(I->first)) 171199511Srdivacky changed = true; 172199511Srdivacky return changed; 173199511Srdivacky } 174199511Srdivacky 175193323Sed // Live-out registers are either in regsLiveOut or vregsPassed. 176193323Sed bool isLiveOut(unsigned Reg) const { 177193323Sed return regsLiveOut.count(Reg) || vregsPassed.count(Reg); 178193323Sed } 179193323Sed }; 180193323Sed 181193323Sed // Extra register info per MBB. 182193323Sed DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap; 183193323Sed 184193323Sed bool isReserved(unsigned Reg) { 185198090Srdivacky return Reg < regsReserved.size() && regsReserved.test(Reg); 186193323Sed } 187193323Sed 188235633Sdim bool isAllocatable(unsigned Reg) { 189245431Sdim return Reg < TRI->getNumRegs() && MRI->isAllocatable(Reg); 190235633Sdim } 191235633Sdim 192199511Srdivacky // Analysis information if available 193199511Srdivacky LiveVariables *LiveVars; 194218893Sdim LiveIntervals *LiveInts; 195218893Sdim LiveStacks *LiveStks; 196218893Sdim SlotIndexes *Indexes; 197199511Srdivacky 198193323Sed void visitMachineFunctionBefore(); 199193323Sed void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); 200245431Sdim void visitMachineBundleBefore(const MachineInstr *MI); 201193323Sed void visitMachineInstrBefore(const MachineInstr *MI); 202193323Sed void visitMachineOperand(const MachineOperand *MO, unsigned MONum); 203193323Sed void visitMachineInstrAfter(const MachineInstr *MI); 204245431Sdim void visitMachineBundleAfter(const MachineInstr *MI); 205193323Sed void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB); 206193323Sed void visitMachineFunctionAfter(); 207193323Sed 208193323Sed void report(const char *msg, const MachineFunction *MF); 209193323Sed void report(const char *msg, const MachineBasicBlock *MBB); 210193323Sed void report(const char *msg, const MachineInstr *MI); 211193323Sed void report(const char *msg, const MachineOperand *MO, unsigned MONum); 212245431Sdim void report(const char *msg, const MachineFunction *MF, 213245431Sdim const LiveInterval &LI); 214245431Sdim void report(const char *msg, const MachineBasicBlock *MBB, 215245431Sdim const LiveInterval &LI); 216263509Sdim void report(const char *msg, const MachineFunction *MF, 217263509Sdim const LiveRange &LR); 218263509Sdim void report(const char *msg, const MachineBasicBlock *MBB, 219263509Sdim const LiveRange &LR); 220193323Sed 221245431Sdim void verifyInlineAsm(const MachineInstr *MI); 222245431Sdim 223235633Sdim void checkLiveness(const MachineOperand *MO, unsigned MONum); 224193323Sed void markReachable(const MachineBasicBlock *MBB); 225202375Srdivacky void calcRegsPassed(); 226193323Sed void checkPHIOps(const MachineBasicBlock *MBB); 227199511Srdivacky 228199511Srdivacky void calcRegsRequired(); 229199511Srdivacky void verifyLiveVariables(); 230212904Sdim void verifyLiveIntervals(); 231245431Sdim void verifyLiveInterval(const LiveInterval&); 232263509Sdim void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned); 233263509Sdim void verifyLiveRangeSegment(const LiveRange&, 234263509Sdim const LiveRange::const_iterator I, unsigned); 235263509Sdim void verifyLiveRange(const LiveRange&, unsigned); 236263509Sdim 237263509Sdim void verifyStackFrame(); 238193323Sed }; 239199511Srdivacky 240199511Srdivacky struct MachineVerifierPass : public MachineFunctionPass { 241199511Srdivacky static char ID; // Pass ID, replacement for typeid 242218893Sdim const char *const Banner; 243199511Srdivacky 244218893Sdim MachineVerifierPass(const char *b = 0) 245218893Sdim : MachineFunctionPass(ID), Banner(b) { 246218893Sdim initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry()); 247218893Sdim } 248199511Srdivacky 249199511Srdivacky void getAnalysisUsage(AnalysisUsage &AU) const { 250199511Srdivacky AU.setPreservesAll(); 251199511Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 252199511Srdivacky } 253199511Srdivacky 254199511Srdivacky bool runOnMachineFunction(MachineFunction &MF) { 255218893Sdim MF.verify(this, Banner); 256199511Srdivacky return false; 257199511Srdivacky } 258199511Srdivacky }; 259199511Srdivacky 260193323Sed} 261193323Sed 262199511Srdivackychar MachineVerifierPass::ID = 0; 263212904SdimINITIALIZE_PASS(MachineVerifierPass, "machineverifier", 264218893Sdim "Verify generated machine code", false, false) 265193323Sed 266218893SdimFunctionPass *llvm::createMachineVerifierPass(const char *Banner) { 267218893Sdim return new MachineVerifierPass(Banner); 268193323Sed} 269193323Sed 270218893Sdimvoid MachineFunction::verify(Pass *p, const char *Banner) const { 271218893Sdim MachineVerifier(p, Banner) 272218893Sdim .runOnMachineFunction(const_cast<MachineFunction&>(*this)); 273199481Srdivacky} 274199481Srdivacky 275198090Srdivackybool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { 276198090Srdivacky raw_ostream *OutFile = 0; 277193323Sed if (OutFileName) { 278198090Srdivacky std::string ErrorInfo; 279263509Sdim OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, sys::fs::F_Append); 280198090Srdivacky if (!ErrorInfo.empty()) { 281198090Srdivacky errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n'; 282198090Srdivacky exit(1); 283198090Srdivacky } 284198090Srdivacky 285198090Srdivacky OS = OutFile; 286193323Sed } else { 287198090Srdivacky OS = &errs(); 288193323Sed } 289193323Sed 290193323Sed foundErrors = 0; 291193323Sed 292193323Sed this->MF = &MF; 293193323Sed TM = &MF.getTarget(); 294224145Sdim TII = TM->getInstrInfo(); 295193323Sed TRI = TM->getRegisterInfo(); 296193323Sed MRI = &MF.getRegInfo(); 297193323Sed 298212904Sdim LiveVars = NULL; 299212904Sdim LiveInts = NULL; 300218893Sdim LiveStks = NULL; 301218893Sdim Indexes = NULL; 302199511Srdivacky if (PASS) { 303212904Sdim LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>(); 304212904Sdim // We don't want to verify LiveVariables if LiveIntervals is available. 305212904Sdim if (!LiveInts) 306212904Sdim LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>(); 307218893Sdim LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>(); 308218893Sdim Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>(); 309199511Srdivacky } 310199511Srdivacky 311193323Sed visitMachineFunctionBefore(); 312193323Sed for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 313193323Sed MFI!=MFE; ++MFI) { 314193323Sed visitMachineBasicBlockBefore(MFI); 315245431Sdim // Keep track of the current bundle header. 316245431Sdim const MachineInstr *CurBundle = 0; 317252723Sdim // Do we expect the next instruction to be part of the same bundle? 318252723Sdim bool InBundle = false; 319252723Sdim 320235633Sdim for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), 321235633Sdim MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) { 322218893Sdim if (MBBI->getParent() != MFI) { 323218893Sdim report("Bad instruction parent pointer", MFI); 324218893Sdim *OS << "Instruction: " << *MBBI; 325218893Sdim continue; 326218893Sdim } 327252723Sdim 328252723Sdim // Check for consistent bundle flags. 329252723Sdim if (InBundle && !MBBI->isBundledWithPred()) 330252723Sdim report("Missing BundledPred flag, " 331252723Sdim "BundledSucc was set on predecessor", MBBI); 332252723Sdim if (!InBundle && MBBI->isBundledWithPred()) 333252723Sdim report("BundledPred flag is set, " 334252723Sdim "but BundledSucc not set on predecessor", MBBI); 335252723Sdim 336245431Sdim // Is this a bundle header? 337245431Sdim if (!MBBI->isInsideBundle()) { 338245431Sdim if (CurBundle) 339245431Sdim visitMachineBundleAfter(CurBundle); 340245431Sdim CurBundle = MBBI; 341245431Sdim visitMachineBundleBefore(CurBundle); 342245431Sdim } else if (!CurBundle) 343245431Sdim report("No bundle header", MBBI); 344193323Sed visitMachineInstrBefore(MBBI); 345193323Sed for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) 346193323Sed visitMachineOperand(&MBBI->getOperand(I), I); 347193323Sed visitMachineInstrAfter(MBBI); 348252723Sdim 349252723Sdim // Was this the last bundled instruction? 350252723Sdim InBundle = MBBI->isBundledWithSucc(); 351193323Sed } 352245431Sdim if (CurBundle) 353245431Sdim visitMachineBundleAfter(CurBundle); 354252723Sdim if (InBundle) 355252723Sdim report("BundledSucc flag set on last instruction in block", &MFI->back()); 356193323Sed visitMachineBasicBlockAfter(MFI); 357193323Sed } 358193323Sed visitMachineFunctionAfter(); 359193323Sed 360198090Srdivacky if (OutFile) 361198090Srdivacky delete OutFile; 362198090Srdivacky else if (foundErrors) 363207618Srdivacky report_fatal_error("Found "+Twine(foundErrors)+" machine code errors."); 364193323Sed 365198090Srdivacky // Clean up. 366198090Srdivacky regsLive.clear(); 367198090Srdivacky regsDefined.clear(); 368198090Srdivacky regsDead.clear(); 369198090Srdivacky regsKilled.clear(); 370235633Sdim regMasks.clear(); 371198090Srdivacky regsLiveInButUnused.clear(); 372198090Srdivacky MBBInfoMap.clear(); 373193323Sed 374193323Sed return false; // no changes 375193323Sed} 376193323Sed 377198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineFunction *MF) { 378193323Sed assert(MF); 379198090Srdivacky *OS << '\n'; 380218893Sdim if (!foundErrors++) { 381218893Sdim if (Banner) 382218893Sdim *OS << "# " << Banner << '\n'; 383218893Sdim MF->print(*OS, Indexes); 384218893Sdim } 385193323Sed *OS << "*** Bad machine code: " << msg << " ***\n" 386245431Sdim << "- function: " << MF->getName() << "\n"; 387193323Sed} 388193323Sed 389198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { 390193323Sed assert(MBB); 391193323Sed report(msg, MBB->getParent()); 392245431Sdim *OS << "- basic block: BB#" << MBB->getNumber() 393245431Sdim << ' ' << MBB->getName() 394245431Sdim << " (" << (const void*)MBB << ')'; 395218893Sdim if (Indexes) 396218893Sdim *OS << " [" << Indexes->getMBBStartIdx(MBB) 397218893Sdim << ';' << Indexes->getMBBEndIdx(MBB) << ')'; 398218893Sdim *OS << '\n'; 399193323Sed} 400193323Sed 401198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineInstr *MI) { 402193323Sed assert(MI); 403193323Sed report(msg, MI->getParent()); 404193323Sed *OS << "- instruction: "; 405218893Sdim if (Indexes && Indexes->hasIndex(MI)) 406218893Sdim *OS << Indexes->getInstructionIndex(MI) << '\t'; 407198090Srdivacky MI->print(*OS, TM); 408193323Sed} 409193323Sed 410198090Srdivackyvoid MachineVerifier::report(const char *msg, 411198090Srdivacky const MachineOperand *MO, unsigned MONum) { 412193323Sed assert(MO); 413193323Sed report(msg, MO->getParent()); 414193323Sed *OS << "- operand " << MONum << ": "; 415193323Sed MO->print(*OS, TM); 416193323Sed *OS << "\n"; 417193323Sed} 418193323Sed 419245431Sdimvoid MachineVerifier::report(const char *msg, const MachineFunction *MF, 420245431Sdim const LiveInterval &LI) { 421245431Sdim report(msg, MF); 422263509Sdim *OS << "- interval: " << LI << '\n'; 423245431Sdim} 424245431Sdim 425245431Sdimvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, 426245431Sdim const LiveInterval &LI) { 427245431Sdim report(msg, MBB); 428263509Sdim *OS << "- interval: " << LI << '\n'; 429245431Sdim} 430245431Sdim 431263509Sdimvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, 432263509Sdim const LiveRange &LR) { 433263509Sdim report(msg, MBB); 434263509Sdim *OS << "- liverange: " << LR << "\n"; 435263509Sdim} 436263509Sdim 437263509Sdimvoid MachineVerifier::report(const char *msg, const MachineFunction *MF, 438263509Sdim const LiveRange &LR) { 439263509Sdim report(msg, MF); 440263509Sdim *OS << "- liverange: " << LR << "\n"; 441263509Sdim} 442263509Sdim 443198090Srdivackyvoid MachineVerifier::markReachable(const MachineBasicBlock *MBB) { 444193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 445193323Sed if (!MInfo.reachable) { 446193323Sed MInfo.reachable = true; 447193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 448193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) 449193323Sed markReachable(*SuI); 450193323Sed } 451193323Sed} 452193323Sed 453198090Srdivackyvoid MachineVerifier::visitMachineFunctionBefore() { 454218893Sdim lastIndex = SlotIndex(); 455245431Sdim regsReserved = MRI->getReservedRegs(); 456198090Srdivacky 457198090Srdivacky // A sub-register of a reserved register is also reserved 458198090Srdivacky for (int Reg = regsReserved.find_first(); Reg>=0; 459198090Srdivacky Reg = regsReserved.find_next(Reg)) { 460245431Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 461198090Srdivacky // FIXME: This should probably be: 462245431Sdim // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register"); 463245431Sdim regsReserved.set(*SubRegs); 464198090Srdivacky } 465198090Srdivacky } 466235633Sdim 467245431Sdim markReachable(&MF->front()); 468235633Sdim 469245431Sdim // Build a set of the basic blocks in the function. 470245431Sdim FunctionBlocks.clear(); 471245431Sdim for (MachineFunction::const_iterator 472245431Sdim I = MF->begin(), E = MF->end(); I != E; ++I) { 473245431Sdim FunctionBlocks.insert(I); 474245431Sdim BBInfo &MInfo = MBBInfoMap[I]; 475245431Sdim 476245431Sdim MInfo.Preds.insert(I->pred_begin(), I->pred_end()); 477245431Sdim if (MInfo.Preds.size() != I->pred_size()) 478245431Sdim report("MBB has duplicate entries in its predecessor list.", I); 479245431Sdim 480245431Sdim MInfo.Succs.insert(I->succ_begin(), I->succ_end()); 481245431Sdim if (MInfo.Succs.size() != I->succ_size()) 482245431Sdim report("MBB has duplicate entries in its successor list.", I); 483245431Sdim } 484252723Sdim 485252723Sdim // Check that the register use lists are sane. 486252723Sdim MRI->verifyUseLists(); 487263509Sdim 488263509Sdim verifyStackFrame(); 489193323Sed} 490193323Sed 491199481Srdivacky// Does iterator point to a and b as the first two elements? 492207618Srdivackystatic bool matchPair(MachineBasicBlock::const_succ_iterator i, 493207618Srdivacky const MachineBasicBlock *a, const MachineBasicBlock *b) { 494199481Srdivacky if (*i == a) 495199481Srdivacky return *++i == b; 496199481Srdivacky if (*i == b) 497199481Srdivacky return *++i == a; 498199481Srdivacky return false; 499199481Srdivacky} 500199481Srdivacky 501199481Srdivackyvoid 502199481SrdivackyMachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { 503226890Sdim FirstTerminator = 0; 504226890Sdim 505235633Sdim if (MRI->isSSA()) { 506235633Sdim // If this block has allocatable physical registers live-in, check that 507235633Sdim // it is an entry block or landing pad. 508235633Sdim for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 509235633Sdim LE = MBB->livein_end(); 510235633Sdim LI != LE; ++LI) { 511235633Sdim unsigned reg = *LI; 512235633Sdim if (isAllocatable(reg) && !MBB->isLandingPad() && 513235633Sdim MBB != MBB->getParent()->begin()) { 514235633Sdim report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB); 515235633Sdim } 516235633Sdim } 517235633Sdim } 518235633Sdim 519218893Sdim // Count the number of landing pad successors. 520218893Sdim SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs; 521218893Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 522218893Sdim E = MBB->succ_end(); I != E; ++I) { 523218893Sdim if ((*I)->isLandingPad()) 524218893Sdim LandingPadSuccs.insert(*I); 525245431Sdim if (!FunctionBlocks.count(*I)) 526245431Sdim report("MBB has successor that isn't part of the function.", MBB); 527245431Sdim if (!MBBInfoMap[*I].Preds.count(MBB)) { 528245431Sdim report("Inconsistent CFG", MBB); 529245431Sdim *OS << "MBB is not in the predecessor list of the successor BB#" 530245431Sdim << (*I)->getNumber() << ".\n"; 531245431Sdim } 532218893Sdim } 533223017Sdim 534245431Sdim // Check the predecessor list. 535245431Sdim for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 536245431Sdim E = MBB->pred_end(); I != E; ++I) { 537245431Sdim if (!FunctionBlocks.count(*I)) 538245431Sdim report("MBB has predecessor that isn't part of the function.", MBB); 539245431Sdim if (!MBBInfoMap[*I].Succs.count(MBB)) { 540245431Sdim report("Inconsistent CFG", MBB); 541245431Sdim *OS << "MBB is not in the successor list of the predecessor BB#" 542245431Sdim << (*I)->getNumber() << ".\n"; 543245431Sdim } 544245431Sdim } 545245431Sdim 546223017Sdim const MCAsmInfo *AsmInfo = TM->getMCAsmInfo(); 547223017Sdim const BasicBlock *BB = MBB->getBasicBlock(); 548223017Sdim if (LandingPadSuccs.size() > 1 && 549223017Sdim !(AsmInfo && 550223017Sdim AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj && 551223017Sdim BB && isa<SwitchInst>(BB->getTerminator()))) 552218893Sdim report("MBB has more than one landing pad successor", MBB); 553218893Sdim 554198090Srdivacky // Call AnalyzeBranch. If it succeeds, there several more conditions to check. 555198090Srdivacky MachineBasicBlock *TBB = 0, *FBB = 0; 556198090Srdivacky SmallVector<MachineOperand, 4> Cond; 557198090Srdivacky if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB), 558198090Srdivacky TBB, FBB, Cond)) { 559198090Srdivacky // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's 560198090Srdivacky // check whether its answers match up with reality. 561198090Srdivacky if (!TBB && !FBB) { 562198090Srdivacky // Block falls through to its successor. 563198090Srdivacky MachineFunction::const_iterator MBBI = MBB; 564198090Srdivacky ++MBBI; 565198090Srdivacky if (MBBI == MF->end()) { 566198090Srdivacky // It's possible that the block legitimately ends with a noreturn 567198090Srdivacky // call or an unreachable, in which case it won't actually fall 568198090Srdivacky // out the bottom of the function. 569218893Sdim } else if (MBB->succ_size() == LandingPadSuccs.size()) { 570198090Srdivacky // It's possible that the block legitimately ends with a noreturn 571198090Srdivacky // call or an unreachable, in which case it won't actuall fall 572198090Srdivacky // out of the block. 573218893Sdim } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 574198090Srdivacky report("MBB exits via unconditional fall-through but doesn't have " 575198090Srdivacky "exactly one CFG successor!", MBB); 576218893Sdim } else if (!MBB->isSuccessor(MBBI)) { 577198090Srdivacky report("MBB exits via unconditional fall-through but its successor " 578198090Srdivacky "differs from its CFG successor!", MBB); 579198090Srdivacky } 580245431Sdim if (!MBB->empty() && getBundleStart(&MBB->back())->isBarrier() && 581245431Sdim !TII->isPredicated(getBundleStart(&MBB->back()))) { 582198090Srdivacky report("MBB exits via unconditional fall-through but ends with a " 583198090Srdivacky "barrier instruction!", MBB); 584198090Srdivacky } 585198090Srdivacky if (!Cond.empty()) { 586198090Srdivacky report("MBB exits via unconditional fall-through but has a condition!", 587198090Srdivacky MBB); 588198090Srdivacky } 589198090Srdivacky } else if (TBB && !FBB && Cond.empty()) { 590198090Srdivacky // Block unconditionally branches somewhere. 591218893Sdim if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 592198090Srdivacky report("MBB exits via unconditional branch but doesn't have " 593198090Srdivacky "exactly one CFG successor!", MBB); 594218893Sdim } else if (!MBB->isSuccessor(TBB)) { 595198090Srdivacky report("MBB exits via unconditional branch but the CFG " 596198090Srdivacky "successor doesn't match the actual successor!", MBB); 597198090Srdivacky } 598198090Srdivacky if (MBB->empty()) { 599198090Srdivacky report("MBB exits via unconditional branch but doesn't contain " 600198090Srdivacky "any instructions!", MBB); 601245431Sdim } else if (!getBundleStart(&MBB->back())->isBarrier()) { 602198090Srdivacky report("MBB exits via unconditional branch but doesn't end with a " 603198090Srdivacky "barrier instruction!", MBB); 604245431Sdim } else if (!getBundleStart(&MBB->back())->isTerminator()) { 605198090Srdivacky report("MBB exits via unconditional branch but the branch isn't a " 606198090Srdivacky "terminator instruction!", MBB); 607198090Srdivacky } 608198090Srdivacky } else if (TBB && !FBB && !Cond.empty()) { 609198090Srdivacky // Block conditionally branches somewhere, otherwise falls through. 610198090Srdivacky MachineFunction::const_iterator MBBI = MBB; 611198090Srdivacky ++MBBI; 612198090Srdivacky if (MBBI == MF->end()) { 613198090Srdivacky report("MBB conditionally falls through out of function!", MBB); 614252723Sdim } else if (MBB->succ_size() == 1) { 615245431Sdim // A conditional branch with only one successor is weird, but allowed. 616245431Sdim if (&*MBBI != TBB) 617245431Sdim report("MBB exits via conditional branch/fall-through but only has " 618245431Sdim "one CFG successor!", MBB); 619245431Sdim else if (TBB != *MBB->succ_begin()) 620245431Sdim report("MBB exits via conditional branch/fall-through but the CFG " 621245431Sdim "successor don't match the actual successor!", MBB); 622245431Sdim } else if (MBB->succ_size() != 2) { 623198090Srdivacky report("MBB exits via conditional branch/fall-through but doesn't have " 624198090Srdivacky "exactly two CFG successors!", MBB); 625199481Srdivacky } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) { 626198090Srdivacky report("MBB exits via conditional branch/fall-through but the CFG " 627198090Srdivacky "successors don't match the actual successors!", MBB); 628198090Srdivacky } 629198090Srdivacky if (MBB->empty()) { 630198090Srdivacky report("MBB exits via conditional branch/fall-through but doesn't " 631198090Srdivacky "contain any instructions!", MBB); 632245431Sdim } else if (getBundleStart(&MBB->back())->isBarrier()) { 633198090Srdivacky report("MBB exits via conditional branch/fall-through but ends with a " 634198090Srdivacky "barrier instruction!", MBB); 635245431Sdim } else if (!getBundleStart(&MBB->back())->isTerminator()) { 636198090Srdivacky report("MBB exits via conditional branch/fall-through but the branch " 637198090Srdivacky "isn't a terminator instruction!", MBB); 638198090Srdivacky } 639198090Srdivacky } else if (TBB && FBB) { 640198090Srdivacky // Block conditionally branches somewhere, otherwise branches 641198090Srdivacky // somewhere else. 642245431Sdim if (MBB->succ_size() == 1) { 643245431Sdim // A conditional branch with only one successor is weird, but allowed. 644245431Sdim if (FBB != TBB) 645245431Sdim report("MBB exits via conditional branch/branch through but only has " 646245431Sdim "one CFG successor!", MBB); 647245431Sdim else if (TBB != *MBB->succ_begin()) 648245431Sdim report("MBB exits via conditional branch/branch through but the CFG " 649245431Sdim "successor don't match the actual successor!", MBB); 650245431Sdim } else if (MBB->succ_size() != 2) { 651198090Srdivacky report("MBB exits via conditional branch/branch but doesn't have " 652198090Srdivacky "exactly two CFG successors!", MBB); 653199481Srdivacky } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) { 654198090Srdivacky report("MBB exits via conditional branch/branch but the CFG " 655198090Srdivacky "successors don't match the actual successors!", MBB); 656198090Srdivacky } 657198090Srdivacky if (MBB->empty()) { 658198090Srdivacky report("MBB exits via conditional branch/branch but doesn't " 659198090Srdivacky "contain any instructions!", MBB); 660245431Sdim } else if (!getBundleStart(&MBB->back())->isBarrier()) { 661198090Srdivacky report("MBB exits via conditional branch/branch but doesn't end with a " 662198090Srdivacky "barrier instruction!", MBB); 663245431Sdim } else if (!getBundleStart(&MBB->back())->isTerminator()) { 664198090Srdivacky report("MBB exits via conditional branch/branch but the branch " 665198090Srdivacky "isn't a terminator instruction!", MBB); 666198090Srdivacky } 667198090Srdivacky if (Cond.empty()) { 668198090Srdivacky report("MBB exits via conditinal branch/branch but there's no " 669198090Srdivacky "condition!", MBB); 670198090Srdivacky } 671198090Srdivacky } else { 672198090Srdivacky report("AnalyzeBranch returned invalid data!", MBB); 673198090Srdivacky } 674198090Srdivacky } 675198090Srdivacky 676193323Sed regsLive.clear(); 677207618Srdivacky for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 678193323Sed E = MBB->livein_end(); I != E; ++I) { 679193323Sed if (!TargetRegisterInfo::isPhysicalRegister(*I)) { 680193323Sed report("MBB live-in list contains non-physical register", MBB); 681193323Sed continue; 682193323Sed } 683263509Sdim for (MCSubRegIterator SubRegs(*I, TRI, /*IncludeSelf=*/true); 684263509Sdim SubRegs.isValid(); ++SubRegs) 685245431Sdim regsLive.insert(*SubRegs); 686193323Sed } 687198090Srdivacky regsLiveInButUnused = regsLive; 688198090Srdivacky 689198090Srdivacky const MachineFrameInfo *MFI = MF->getFrameInfo(); 690198090Srdivacky assert(MFI && "Function has no frame info"); 691198090Srdivacky BitVector PR = MFI->getPristineRegs(MBB); 692198090Srdivacky for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { 693263509Sdim for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true); 694263509Sdim SubRegs.isValid(); ++SubRegs) 695245431Sdim regsLive.insert(*SubRegs); 696198090Srdivacky } 697198090Srdivacky 698193323Sed regsKilled.clear(); 699193323Sed regsDefined.clear(); 700218893Sdim 701218893Sdim if (Indexes) 702218893Sdim lastIndex = Indexes->getMBBStartIdx(MBB); 703193323Sed} 704193323Sed 705245431Sdim// This function gets called for all bundle headers, including normal 706245431Sdim// stand-alone unbundled instructions. 707245431Sdimvoid MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) { 708245431Sdim if (Indexes && Indexes->hasIndex(MI)) { 709245431Sdim SlotIndex idx = Indexes->getInstructionIndex(MI); 710245431Sdim if (!(idx > lastIndex)) { 711245431Sdim report("Instruction index out of order", MI); 712245431Sdim *OS << "Last instruction was at " << lastIndex << '\n'; 713245431Sdim } 714245431Sdim lastIndex = idx; 715245431Sdim } 716245431Sdim 717245431Sdim // Ensure non-terminators don't follow terminators. 718245431Sdim // Ignore predicated terminators formed by if conversion. 719245431Sdim // FIXME: If conversion shouldn't need to violate this rule. 720245431Sdim if (MI->isTerminator() && !TII->isPredicated(MI)) { 721245431Sdim if (!FirstTerminator) 722245431Sdim FirstTerminator = MI; 723245431Sdim } else if (FirstTerminator) { 724245431Sdim report("Non-terminator instruction after the first terminator", MI); 725245431Sdim *OS << "First terminator was:\t" << *FirstTerminator; 726245431Sdim } 727245431Sdim} 728245431Sdim 729245431Sdim// The operands on an INLINEASM instruction must follow a template. 730245431Sdim// Verify that the flag operands make sense. 731245431Sdimvoid MachineVerifier::verifyInlineAsm(const MachineInstr *MI) { 732245431Sdim // The first two operands on INLINEASM are the asm string and global flags. 733245431Sdim if (MI->getNumOperands() < 2) { 734245431Sdim report("Too few operands on inline asm", MI); 735245431Sdim return; 736245431Sdim } 737245431Sdim if (!MI->getOperand(0).isSymbol()) 738245431Sdim report("Asm string must be an external symbol", MI); 739245431Sdim if (!MI->getOperand(1).isImm()) 740245431Sdim report("Asm flags must be an immediate", MI); 741245431Sdim // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2, 742245431Sdim // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16. 743245431Sdim if (!isUInt<5>(MI->getOperand(1).getImm())) 744245431Sdim report("Unknown asm flags", &MI->getOperand(1), 1); 745245431Sdim 746245431Sdim assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed"); 747245431Sdim 748245431Sdim unsigned OpNo = InlineAsm::MIOp_FirstOperand; 749245431Sdim unsigned NumOps; 750245431Sdim for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) { 751245431Sdim const MachineOperand &MO = MI->getOperand(OpNo); 752245431Sdim // There may be implicit ops after the fixed operands. 753245431Sdim if (!MO.isImm()) 754245431Sdim break; 755245431Sdim NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm()); 756245431Sdim } 757245431Sdim 758245431Sdim if (OpNo > MI->getNumOperands()) 759245431Sdim report("Missing operands in last group", MI); 760245431Sdim 761245431Sdim // An optional MDNode follows the groups. 762245431Sdim if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata()) 763245431Sdim ++OpNo; 764245431Sdim 765245431Sdim // All trailing operands must be implicit registers. 766245431Sdim for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) { 767245431Sdim const MachineOperand &MO = MI->getOperand(OpNo); 768245431Sdim if (!MO.isReg() || !MO.isImplicit()) 769245431Sdim report("Expected implicit register after groups", &MO, OpNo); 770245431Sdim } 771245431Sdim} 772245431Sdim 773198090Srdivackyvoid MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { 774224145Sdim const MCInstrDesc &MCID = MI->getDesc(); 775224145Sdim if (MI->getNumOperands() < MCID.getNumOperands()) { 776193323Sed report("Too few operands", MI); 777224145Sdim *OS << MCID.getNumOperands() << " operands expected, but " 778263509Sdim << MI->getNumOperands() << " given.\n"; 779193323Sed } 780198090Srdivacky 781245431Sdim // Check the tied operands. 782245431Sdim if (MI->isInlineAsm()) 783245431Sdim verifyInlineAsm(MI); 784245431Sdim 785198090Srdivacky // Check the MachineMemOperands for basic consistency. 786198090Srdivacky for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 787198090Srdivacky E = MI->memoperands_end(); I != E; ++I) { 788235633Sdim if ((*I)->isLoad() && !MI->mayLoad()) 789198090Srdivacky report("Missing mayLoad flag", MI); 790235633Sdim if ((*I)->isStore() && !MI->mayStore()) 791198090Srdivacky report("Missing mayStore flag", MI); 792193323Sed } 793212904Sdim 794212904Sdim // Debug values must not have a slot index. 795235633Sdim // Other instructions must have one, unless they are inside a bundle. 796212904Sdim if (LiveInts) { 797212904Sdim bool mapped = !LiveInts->isNotInMIMap(MI); 798212904Sdim if (MI->isDebugValue()) { 799212904Sdim if (mapped) 800212904Sdim report("Debug instruction has a slot index", MI); 801235633Sdim } else if (MI->isInsideBundle()) { 802235633Sdim if (mapped) 803235633Sdim report("Instruction inside bundle has a slot index", MI); 804212904Sdim } else { 805212904Sdim if (!mapped) 806212904Sdim report("Missing slot index", MI); 807212904Sdim } 808212904Sdim } 809212904Sdim 810226890Sdim StringRef ErrorInfo; 811226890Sdim if (!TII->verifyInstruction(MI, ErrorInfo)) 812226890Sdim report(ErrorInfo.data(), MI); 813193323Sed} 814193323Sed 815193323Sedvoid 816198090SrdivackyMachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { 817193323Sed const MachineInstr *MI = MO->getParent(); 818224145Sdim const MCInstrDesc &MCID = MI->getDesc(); 819193323Sed 820224145Sdim // The first MCID.NumDefs operands must be explicit register defines 821224145Sdim if (MONum < MCID.getNumDefs()) { 822245431Sdim const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 823193323Sed if (!MO->isReg()) 824193323Sed report("Explicit definition must be a register", MO, MONum); 825245431Sdim else if (!MO->isDef() && !MCOI.isOptionalDef()) 826193323Sed report("Explicit definition marked as use", MO, MONum); 827193323Sed else if (MO->isImplicit()) 828193323Sed report("Explicit definition marked as implicit", MO, MONum); 829224145Sdim } else if (MONum < MCID.getNumOperands()) { 830245431Sdim const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 831218893Sdim // Don't check if it's the last operand in a variadic instruction. See, 832218893Sdim // e.g., LDM_RET in the arm back end. 833224145Sdim if (MO->isReg() && 834235633Sdim !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { 835224145Sdim if (MO->isDef() && !MCOI.isOptionalDef()) 836263509Sdim report("Explicit operand marked as def", MO, MONum); 837198090Srdivacky if (MO->isImplicit()) 838198090Srdivacky report("Explicit operand marked as implicit", MO, MONum); 839198090Srdivacky } 840245431Sdim 841245431Sdim int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO); 842245431Sdim if (TiedTo != -1) { 843245431Sdim if (!MO->isReg()) 844245431Sdim report("Tied use must be a register", MO, MONum); 845245431Sdim else if (!MO->isTied()) 846245431Sdim report("Operand should be tied", MO, MONum); 847245431Sdim else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum)) 848245431Sdim report("Tied def doesn't match MCInstrDesc", MO, MONum); 849245431Sdim } else if (MO->isReg() && MO->isTied()) 850245431Sdim report("Explicit operand should not be tied", MO, MONum); 851198090Srdivacky } else { 852201360Srdivacky // ARM adds %reg0 operands to indicate predicates. We'll allow that. 853235633Sdim if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg()) 854198090Srdivacky report("Extra explicit operand on non-variadic instruction", MO, MONum); 855193323Sed } 856193323Sed 857193323Sed switch (MO->getType()) { 858193323Sed case MachineOperand::MO_Register: { 859193323Sed const unsigned Reg = MO->getReg(); 860193323Sed if (!Reg) 861193323Sed return; 862235633Sdim if (MRI->tracksLiveness() && !MI->isDebugValue()) 863235633Sdim checkLiveness(MO, MONum); 864193323Sed 865245431Sdim // Verify the consistency of tied operands. 866245431Sdim if (MO->isTied()) { 867245431Sdim unsigned OtherIdx = MI->findTiedOperandIdx(MONum); 868245431Sdim const MachineOperand &OtherMO = MI->getOperand(OtherIdx); 869245431Sdim if (!OtherMO.isReg()) 870245431Sdim report("Must be tied to a register", MO, MONum); 871245431Sdim if (!OtherMO.isTied()) 872245431Sdim report("Missing tie flags on tied operand", MO, MONum); 873245431Sdim if (MI->findTiedOperandIdx(OtherIdx) != MONum) 874245431Sdim report("Inconsistent tie links", MO, MONum); 875245431Sdim if (MONum < MCID.getNumDefs()) { 876245431Sdim if (OtherIdx < MCID.getNumOperands()) { 877245431Sdim if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO)) 878245431Sdim report("Explicit def tied to explicit use without tie constraint", 879245431Sdim MO, MONum); 880245431Sdim } else { 881245431Sdim if (!OtherMO.isImplicit()) 882245431Sdim report("Explicit def should be tied to implicit use", MO, MONum); 883245431Sdim } 884245431Sdim } 885245431Sdim } 886198090Srdivacky 887245431Sdim // Verify two-address constraints after leaving SSA form. 888245431Sdim unsigned DefIdx; 889245431Sdim if (!MRI->isSSA() && MO->isUse() && 890245431Sdim MI->isRegTiedToDefOperand(MONum, &DefIdx) && 891245431Sdim Reg != MI->getOperand(DefIdx).getReg()) 892245431Sdim report("Two-address instruction operands must be identical", MO, MONum); 893245431Sdim 894193323Sed // Check register classes. 895224145Sdim if (MONum < MCID.getNumOperands() && !MO->isImplicit()) { 896193323Sed unsigned SubIdx = MO->getSubReg(); 897193323Sed 898193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 899193323Sed if (SubIdx) { 900226890Sdim report("Illegal subregister index for physical register", MO, MONum); 901226890Sdim return; 902193323Sed } 903245431Sdim if (const TargetRegisterClass *DRC = 904245431Sdim TII->getRegClass(MCID, MONum, TRI, *MF)) { 905226890Sdim if (!DRC->contains(Reg)) { 906193323Sed report("Illegal physical register for instruction", MO, MONum); 907226890Sdim *OS << TRI->getName(Reg) << " is not a " 908193323Sed << DRC->getName() << " register.\n"; 909193323Sed } 910193323Sed } 911193323Sed } else { 912193323Sed // Virtual register. 913193323Sed const TargetRegisterClass *RC = MRI->getRegClass(Reg); 914193323Sed if (SubIdx) { 915226890Sdim const TargetRegisterClass *SRC = 916226890Sdim TRI->getSubClassWithSubReg(RC, SubIdx); 917208599Srdivacky if (!SRC) { 918193323Sed report("Invalid subregister index for virtual register", MO, MONum); 919208599Srdivacky *OS << "Register class " << RC->getName() 920208599Srdivacky << " does not support subreg index " << SubIdx << "\n"; 921193323Sed return; 922193323Sed } 923226890Sdim if (RC != SRC) { 924226890Sdim report("Invalid register class for subregister index", MO, MONum); 925226890Sdim *OS << "Register class " << RC->getName() 926226890Sdim << " does not fully support subreg index " << SubIdx << "\n"; 927226890Sdim return; 928226890Sdim } 929193323Sed } 930245431Sdim if (const TargetRegisterClass *DRC = 931245431Sdim TII->getRegClass(MCID, MONum, TRI, *MF)) { 932226890Sdim if (SubIdx) { 933226890Sdim const TargetRegisterClass *SuperRC = 934226890Sdim TRI->getLargestLegalSuperClass(RC); 935226890Sdim if (!SuperRC) { 936226890Sdim report("No largest legal super class exists.", MO, MONum); 937226890Sdim return; 938226890Sdim } 939226890Sdim DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx); 940226890Sdim if (!DRC) { 941226890Sdim report("No matching super-reg register class.", MO, MONum); 942226890Sdim return; 943226890Sdim } 944226890Sdim } 945223017Sdim if (!RC->hasSuperClassEq(DRC)) { 946193323Sed report("Illegal virtual register for instruction", MO, MONum); 947193323Sed *OS << "Expected a " << DRC->getName() << " register, but got a " 948193323Sed << RC->getName() << " register\n"; 949193323Sed } 950193323Sed } 951193323Sed } 952193323Sed } 953193323Sed break; 954193323Sed } 955198090Srdivacky 956235633Sdim case MachineOperand::MO_RegisterMask: 957235633Sdim regMasks.push_back(MO->getRegMask()); 958235633Sdim break; 959235633Sdim 960198090Srdivacky case MachineOperand::MO_MachineBasicBlock: 961203954Srdivacky if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent())) 962203954Srdivacky report("PHI operand is not in the CFG", MO, MONum); 963198090Srdivacky break; 964198090Srdivacky 965218893Sdim case MachineOperand::MO_FrameIndex: 966218893Sdim if (LiveStks && LiveStks->hasInterval(MO->getIndex()) && 967218893Sdim LiveInts && !LiveInts->isNotInMIMap(MI)) { 968218893Sdim LiveInterval &LI = LiveStks->getInterval(MO->getIndex()); 969218893Sdim SlotIndex Idx = LiveInts->getInstructionIndex(MI); 970235633Sdim if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) { 971218893Sdim report("Instruction loads from dead spill slot", MO, MONum); 972218893Sdim *OS << "Live stack: " << LI << '\n'; 973218893Sdim } 974235633Sdim if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) { 975218893Sdim report("Instruction stores to dead spill slot", MO, MONum); 976218893Sdim *OS << "Live stack: " << LI << '\n'; 977218893Sdim } 978218893Sdim } 979218893Sdim break; 980218893Sdim 981193323Sed default: 982193323Sed break; 983193323Sed } 984193323Sed} 985193323Sed 986235633Sdimvoid MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { 987235633Sdim const MachineInstr *MI = MO->getParent(); 988235633Sdim const unsigned Reg = MO->getReg(); 989235633Sdim 990235633Sdim // Both use and def operands can read a register. 991235633Sdim if (MO->readsReg()) { 992235633Sdim regsLiveInButUnused.erase(Reg); 993235633Sdim 994245431Sdim if (MO->isKill()) 995235633Sdim addRegWithSubRegs(regsKilled, Reg); 996235633Sdim 997235633Sdim // Check that LiveVars knows this kill. 998235633Sdim if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) && 999235633Sdim MO->isKill()) { 1000235633Sdim LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1001235633Sdim if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end()) 1002235633Sdim report("Kill missing from LiveVariables", MO, MONum); 1003235633Sdim } 1004235633Sdim 1005235633Sdim // Check LiveInts liveness and kill. 1006245431Sdim if (LiveInts && !LiveInts->isNotInMIMap(MI)) { 1007245431Sdim SlotIndex UseIdx = LiveInts->getInstructionIndex(MI); 1008245431Sdim // Check the cached regunit intervals. 1009245431Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) { 1010245431Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 1011263509Sdim if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units)) { 1012263509Sdim LiveQueryResult LRQ = LR->Query(UseIdx); 1013245431Sdim if (!LRQ.valueIn()) { 1014263509Sdim report("No live segment at use", MO, MONum); 1015245431Sdim *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI) 1016263509Sdim << ' ' << *LR << '\n'; 1017245431Sdim } 1018245431Sdim if (MO->isKill() && !LRQ.isKill()) { 1019245431Sdim report("Live range continues after kill flag", MO, MONum); 1020263509Sdim *OS << PrintRegUnit(*Units, TRI) << ' ' << *LR << '\n'; 1021245431Sdim } 1022245431Sdim } 1023235633Sdim } 1024245431Sdim } 1025245431Sdim 1026245431Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1027245431Sdim if (LiveInts->hasInterval(Reg)) { 1028245431Sdim // This is a virtual register interval. 1029245431Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1030263509Sdim LiveQueryResult LRQ = LI.Query(UseIdx); 1031245431Sdim if (!LRQ.valueIn()) { 1032263509Sdim report("No live segment at use", MO, MONum); 1033245431Sdim *OS << UseIdx << " is not live in " << LI << '\n'; 1034245431Sdim } 1035245431Sdim // Check for extra kill flags. 1036245431Sdim // Note that we allow missing kill flags for now. 1037245431Sdim if (MO->isKill() && !LRQ.isKill()) { 1038245431Sdim report("Live range continues after kill flag", MO, MONum); 1039245431Sdim *OS << "Live range: " << LI << '\n'; 1040245431Sdim } 1041245431Sdim } else { 1042245431Sdim report("Virtual register has no live interval", MO, MONum); 1043235633Sdim } 1044235633Sdim } 1045235633Sdim } 1046235633Sdim 1047235633Sdim // Use of a dead register. 1048235633Sdim if (!regsLive.count(Reg)) { 1049235633Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 1050235633Sdim // Reserved registers may be used even when 'dead'. 1051235633Sdim if (!isReserved(Reg)) 1052235633Sdim report("Using an undefined physical register", MO, MONum); 1053245431Sdim } else if (MRI->def_empty(Reg)) { 1054245431Sdim report("Reading virtual register without a def", MO, MONum); 1055235633Sdim } else { 1056235633Sdim BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1057235633Sdim // We don't know which virtual registers are live in, so only complain 1058235633Sdim // if vreg was killed in this MBB. Otherwise keep track of vregs that 1059235633Sdim // must be live in. PHI instructions are handled separately. 1060235633Sdim if (MInfo.regsKilled.count(Reg)) 1061235633Sdim report("Using a killed virtual register", MO, MONum); 1062235633Sdim else if (!MI->isPHI()) 1063235633Sdim MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 1064235633Sdim } 1065235633Sdim } 1066235633Sdim } 1067235633Sdim 1068235633Sdim if (MO->isDef()) { 1069235633Sdim // Register defined. 1070235633Sdim // TODO: verify that earlyclobber ops are not used. 1071235633Sdim if (MO->isDead()) 1072235633Sdim addRegWithSubRegs(regsDead, Reg); 1073235633Sdim else 1074235633Sdim addRegWithSubRegs(regsDefined, Reg); 1075235633Sdim 1076235633Sdim // Verify SSA form. 1077235633Sdim if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) && 1078235633Sdim llvm::next(MRI->def_begin(Reg)) != MRI->def_end()) 1079235633Sdim report("Multiple virtual register defs in SSA form", MO, MONum); 1080235633Sdim 1081263509Sdim // Check LiveInts for a live segment, but only for virtual registers. 1082235633Sdim if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) && 1083235633Sdim !LiveInts->isNotInMIMap(MI)) { 1084245431Sdim SlotIndex DefIdx = LiveInts->getInstructionIndex(MI); 1085245431Sdim DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber()); 1086235633Sdim if (LiveInts->hasInterval(Reg)) { 1087235633Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1088235633Sdim if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) { 1089235633Sdim assert(VNI && "NULL valno is not allowed"); 1090245431Sdim if (VNI->def != DefIdx) { 1091235633Sdim report("Inconsistent valno->def", MO, MONum); 1092235633Sdim *OS << "Valno " << VNI->id << " is not defined at " 1093235633Sdim << DefIdx << " in " << LI << '\n'; 1094235633Sdim } 1095235633Sdim } else { 1096263509Sdim report("No live segment at def", MO, MONum); 1097235633Sdim *OS << DefIdx << " is not live in " << LI << '\n'; 1098235633Sdim } 1099263509Sdim // Check that, if the dead def flag is present, LiveInts agree. 1100263509Sdim if (MO->isDead()) { 1101263509Sdim LiveQueryResult LRQ = LI.Query(DefIdx); 1102263509Sdim if (!LRQ.isDeadDef()) { 1103263509Sdim report("Live range continues after dead def flag", MO, MONum); 1104263509Sdim *OS << "Live range: " << LI << '\n'; 1105263509Sdim } 1106263509Sdim } 1107235633Sdim } else { 1108235633Sdim report("Virtual register has no Live interval", MO, MONum); 1109235633Sdim } 1110235633Sdim } 1111235633Sdim } 1112235633Sdim} 1113235633Sdim 1114198090Srdivackyvoid MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { 1115245431Sdim} 1116245431Sdim 1117245431Sdim// This function gets called after visiting all instructions in a bundle. The 1118245431Sdim// argument points to the bundle header. 1119245431Sdim// Normal stand-alone instructions are also considered 'bundles', and this 1120245431Sdim// function is called for all of them. 1121245431Sdimvoid MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) { 1122193323Sed BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1123193323Sed set_union(MInfo.regsKilled, regsKilled); 1124212904Sdim set_subtract(regsLive, regsKilled); regsKilled.clear(); 1125235633Sdim // Kill any masked registers. 1126235633Sdim while (!regMasks.empty()) { 1127235633Sdim const uint32_t *Mask = regMasks.pop_back_val(); 1128235633Sdim for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I) 1129235633Sdim if (TargetRegisterInfo::isPhysicalRegister(*I) && 1130235633Sdim MachineOperand::clobbersPhysReg(Mask, *I)) 1131235633Sdim regsDead.push_back(*I); 1132235633Sdim } 1133212904Sdim set_subtract(regsLive, regsDead); regsDead.clear(); 1134212904Sdim set_union(regsLive, regsDefined); regsDefined.clear(); 1135193323Sed} 1136193323Sed 1137193323Sedvoid 1138198090SrdivackyMachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { 1139193323Sed MBBInfoMap[MBB].regsLiveOut = regsLive; 1140193323Sed regsLive.clear(); 1141218893Sdim 1142218893Sdim if (Indexes) { 1143218893Sdim SlotIndex stop = Indexes->getMBBEndIdx(MBB); 1144218893Sdim if (!(stop > lastIndex)) { 1145218893Sdim report("Block ends before last instruction index", MBB); 1146218893Sdim *OS << "Block ends at " << stop 1147218893Sdim << " last instruction was at " << lastIndex << '\n'; 1148218893Sdim } 1149218893Sdim lastIndex = stop; 1150218893Sdim } 1151193323Sed} 1152193323Sed 1153193323Sed// Calculate the largest possible vregsPassed sets. These are the registers that 1154193323Sed// can pass through an MBB live, but may not be live every time. It is assumed 1155193323Sed// that all vregsPassed sets are empty before the call. 1156202375Srdivackyvoid MachineVerifier::calcRegsPassed() { 1157193323Sed // First push live-out regs to successors' vregsPassed. Remember the MBBs that 1158193323Sed // have any vregsPassed. 1159235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> todo; 1160193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1161193323Sed MFI != MFE; ++MFI) { 1162193323Sed const MachineBasicBlock &MBB(*MFI); 1163193323Sed BBInfo &MInfo = MBBInfoMap[&MBB]; 1164193323Sed if (!MInfo.reachable) 1165193323Sed continue; 1166193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 1167193323Sed SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 1168193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 1169193323Sed if (SInfo.addPassed(MInfo.regsLiveOut)) 1170193323Sed todo.insert(*SuI); 1171193323Sed } 1172193323Sed } 1173193323Sed 1174193323Sed // Iteratively push vregsPassed to successors. This will converge to the same 1175193323Sed // final state regardless of DenseSet iteration order. 1176193323Sed while (!todo.empty()) { 1177193323Sed const MachineBasicBlock *MBB = *todo.begin(); 1178193323Sed todo.erase(MBB); 1179193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 1180193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 1181193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 1182193323Sed if (*SuI == MBB) 1183193323Sed continue; 1184193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 1185193323Sed if (SInfo.addPassed(MInfo.vregsPassed)) 1186193323Sed todo.insert(*SuI); 1187193323Sed } 1188193323Sed } 1189193323Sed} 1190193323Sed 1191199511Srdivacky// Calculate the set of virtual registers that must be passed through each basic 1192199511Srdivacky// block in order to satisfy the requirements of successor blocks. This is very 1193202375Srdivacky// similar to calcRegsPassed, only backwards. 1194199511Srdivackyvoid MachineVerifier::calcRegsRequired() { 1195199511Srdivacky // First push live-in regs to predecessors' vregsRequired. 1196235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> todo; 1197199511Srdivacky for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1198199511Srdivacky MFI != MFE; ++MFI) { 1199199511Srdivacky const MachineBasicBlock &MBB(*MFI); 1200199511Srdivacky BBInfo &MInfo = MBBInfoMap[&MBB]; 1201199511Srdivacky for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(), 1202199511Srdivacky PrE = MBB.pred_end(); PrI != PrE; ++PrI) { 1203199511Srdivacky BBInfo &PInfo = MBBInfoMap[*PrI]; 1204199511Srdivacky if (PInfo.addRequired(MInfo.vregsLiveIn)) 1205199511Srdivacky todo.insert(*PrI); 1206199511Srdivacky } 1207199511Srdivacky } 1208199511Srdivacky 1209199511Srdivacky // Iteratively push vregsRequired to predecessors. This will converge to the 1210199511Srdivacky // same final state regardless of DenseSet iteration order. 1211199511Srdivacky while (!todo.empty()) { 1212199511Srdivacky const MachineBasicBlock *MBB = *todo.begin(); 1213199511Srdivacky todo.erase(MBB); 1214199511Srdivacky BBInfo &MInfo = MBBInfoMap[MBB]; 1215199511Srdivacky for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1216199511Srdivacky PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1217199511Srdivacky if (*PrI == MBB) 1218199511Srdivacky continue; 1219199511Srdivacky BBInfo &SInfo = MBBInfoMap[*PrI]; 1220199511Srdivacky if (SInfo.addRequired(MInfo.vregsRequired)) 1221199511Srdivacky todo.insert(*PrI); 1222199511Srdivacky } 1223199511Srdivacky } 1224199511Srdivacky} 1225199511Srdivacky 1226193323Sed// Check PHI instructions at the beginning of MBB. It is assumed that 1227202375Srdivacky// calcRegsPassed has been run so BBInfo::isLiveOut is valid. 1228198090Srdivackyvoid MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) { 1229235633Sdim SmallPtrSet<const MachineBasicBlock*, 8> seen; 1230193323Sed for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 1231203954Srdivacky BBI != BBE && BBI->isPHI(); ++BBI) { 1232235633Sdim seen.clear(); 1233193323Sed 1234193323Sed for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 1235193323Sed unsigned Reg = BBI->getOperand(i).getReg(); 1236193323Sed const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB(); 1237193323Sed if (!Pre->isSuccessor(MBB)) 1238193323Sed continue; 1239193323Sed seen.insert(Pre); 1240193323Sed BBInfo &PrInfo = MBBInfoMap[Pre]; 1241193323Sed if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 1242193323Sed report("PHI operand is not live-out from predecessor", 1243193323Sed &BBI->getOperand(i), i); 1244193323Sed } 1245193323Sed 1246193323Sed // Did we see all predecessors? 1247193323Sed for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1248193323Sed PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1249193323Sed if (!seen.count(*PrI)) { 1250193323Sed report("Missing PHI operand", BBI); 1251198892Srdivacky *OS << "BB#" << (*PrI)->getNumber() 1252193323Sed << " is a predecessor according to the CFG.\n"; 1253193323Sed } 1254193323Sed } 1255193323Sed } 1256193323Sed} 1257193323Sed 1258198090Srdivackyvoid MachineVerifier::visitMachineFunctionAfter() { 1259202375Srdivacky calcRegsPassed(); 1260193323Sed 1261193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1262193323Sed MFI != MFE; ++MFI) { 1263193323Sed BBInfo &MInfo = MBBInfoMap[MFI]; 1264193323Sed 1265193323Sed // Skip unreachable MBBs. 1266193323Sed if (!MInfo.reachable) 1267193323Sed continue; 1268193323Sed 1269202375Srdivacky checkPHIOps(MFI); 1270193323Sed } 1271193323Sed 1272212904Sdim // Now check liveness info if available 1273235633Sdim calcRegsRequired(); 1274235633Sdim 1275245431Sdim // Check for killed virtual registers that should be live out. 1276245431Sdim for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1277245431Sdim MFI != MFE; ++MFI) { 1278245431Sdim BBInfo &MInfo = MBBInfoMap[MFI]; 1279245431Sdim for (RegSet::iterator 1280245431Sdim I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1281245431Sdim ++I) 1282245431Sdim if (MInfo.regsKilled.count(*I)) { 1283245431Sdim report("Virtual register killed in block, but needed live out.", MFI); 1284245431Sdim *OS << "Virtual register " << PrintReg(*I) 1285245431Sdim << " is used after the block.\n"; 1286245431Sdim } 1287245431Sdim } 1288245431Sdim 1289245431Sdim if (!MF->empty()) { 1290235633Sdim BBInfo &MInfo = MBBInfoMap[&MF->front()]; 1291235633Sdim for (RegSet::iterator 1292235633Sdim I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1293235633Sdim ++I) 1294235633Sdim report("Virtual register def doesn't dominate all uses.", 1295235633Sdim MRI->getVRegDef(*I)); 1296235633Sdim } 1297235633Sdim 1298212904Sdim if (LiveVars) 1299199511Srdivacky verifyLiveVariables(); 1300212904Sdim if (LiveInts) 1301212904Sdim verifyLiveIntervals(); 1302193323Sed} 1303199511Srdivacky 1304199511Srdivackyvoid MachineVerifier::verifyLiveVariables() { 1305199511Srdivacky assert(LiveVars && "Don't call verifyLiveVariables without LiveVars"); 1306218893Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1307218893Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1308199511Srdivacky LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1309199511Srdivacky for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1310199511Srdivacky MFI != MFE; ++MFI) { 1311199511Srdivacky BBInfo &MInfo = MBBInfoMap[MFI]; 1312199511Srdivacky 1313199511Srdivacky // Our vregsRequired should be identical to LiveVariables' AliveBlocks 1314199511Srdivacky if (MInfo.vregsRequired.count(Reg)) { 1315199511Srdivacky if (!VI.AliveBlocks.test(MFI->getNumber())) { 1316199511Srdivacky report("LiveVariables: Block missing from AliveBlocks", MFI); 1317218893Sdim *OS << "Virtual register " << PrintReg(Reg) 1318199511Srdivacky << " must be live through the block.\n"; 1319199511Srdivacky } 1320199511Srdivacky } else { 1321199511Srdivacky if (VI.AliveBlocks.test(MFI->getNumber())) { 1322199511Srdivacky report("LiveVariables: Block should not be in AliveBlocks", MFI); 1323218893Sdim *OS << "Virtual register " << PrintReg(Reg) 1324199511Srdivacky << " is not needed live through the block.\n"; 1325199511Srdivacky } 1326199511Srdivacky } 1327199511Srdivacky } 1328199511Srdivacky } 1329199511Srdivacky} 1330199511Srdivacky 1331212904Sdimvoid MachineVerifier::verifyLiveIntervals() { 1332212904Sdim assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts"); 1333245431Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1334245431Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1335218893Sdim 1336218893Sdim // Spilling and splitting may leave unused registers around. Skip them. 1337245431Sdim if (MRI->reg_nodbg_empty(Reg)) 1338218893Sdim continue; 1339218893Sdim 1340245431Sdim if (!LiveInts->hasInterval(Reg)) { 1341245431Sdim report("Missing live interval for virtual register", MF); 1342245431Sdim *OS << PrintReg(Reg, TRI) << " still has defs or uses\n"; 1343218893Sdim continue; 1344245431Sdim } 1345218893Sdim 1346245431Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1347245431Sdim assert(Reg == LI.reg && "Invalid reg to interval mapping"); 1348245431Sdim verifyLiveInterval(LI); 1349245431Sdim } 1350199511Srdivacky 1351245431Sdim // Verify all the cached regunit intervals. 1352245431Sdim for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 1353263509Sdim if (const LiveRange *LR = LiveInts->getCachedRegUnit(i)) 1354263509Sdim verifyLiveRange(*LR, i); 1355245431Sdim} 1356212904Sdim 1357263509Sdimvoid MachineVerifier::verifyLiveRangeValue(const LiveRange &LR, 1358263509Sdim const VNInfo *VNI, 1359263509Sdim unsigned Reg) { 1360245431Sdim if (VNI->isUnused()) 1361245431Sdim return; 1362212904Sdim 1363263509Sdim const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def); 1364212904Sdim 1365245431Sdim if (!DefVNI) { 1366263509Sdim report("Valno not live at def and not marked unused", MF, LR); 1367245431Sdim *OS << "Valno #" << VNI->id << '\n'; 1368245431Sdim return; 1369245431Sdim } 1370212904Sdim 1371245431Sdim if (DefVNI != VNI) { 1372263509Sdim report("Live segment at def has different valno", MF, LR); 1373245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1374245431Sdim << " where valno #" << DefVNI->id << " is live\n"; 1375245431Sdim return; 1376245431Sdim } 1377218893Sdim 1378245431Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); 1379245431Sdim if (!MBB) { 1380263509Sdim report("Invalid definition index", MF, LR); 1381245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1382263509Sdim << " in " << LR << '\n'; 1383245431Sdim return; 1384245431Sdim } 1385218893Sdim 1386245431Sdim if (VNI->isPHIDef()) { 1387245431Sdim if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { 1388263509Sdim report("PHIDef value is not defined at MBB start", MBB, LR); 1389245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1390245431Sdim << ", not at the beginning of BB#" << MBB->getNumber() << '\n'; 1391245431Sdim } 1392245431Sdim return; 1393245431Sdim } 1394218893Sdim 1395245431Sdim // Non-PHI def. 1396245431Sdim const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); 1397245431Sdim if (!MI) { 1398263509Sdim report("No instruction at def index", MBB, LR); 1399245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1400245431Sdim return; 1401245431Sdim } 1402235633Sdim 1403263509Sdim if (Reg != 0) { 1404263509Sdim bool hasDef = false; 1405263509Sdim bool isEarlyClobber = false; 1406263509Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1407263509Sdim if (!MOI->isReg() || !MOI->isDef()) 1408245431Sdim continue; 1409263509Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1410263509Sdim if (MOI->getReg() != Reg) 1411263509Sdim continue; 1412263509Sdim } else { 1413263509Sdim if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || 1414263509Sdim !TRI->hasRegUnit(MOI->getReg(), Reg)) 1415263509Sdim continue; 1416263509Sdim } 1417263509Sdim hasDef = true; 1418263509Sdim if (MOI->isEarlyClobber()) 1419263509Sdim isEarlyClobber = true; 1420212904Sdim } 1421212904Sdim 1422263509Sdim if (!hasDef) { 1423263509Sdim report("Defining instruction does not modify register", MI); 1424263509Sdim *OS << "Valno #" << VNI->id << " in " << LR << '\n'; 1425263509Sdim } 1426212904Sdim 1427263509Sdim // Early clobber defs begin at USE slots, but other defs must begin at 1428263509Sdim // DEF slots. 1429263509Sdim if (isEarlyClobber) { 1430263509Sdim if (!VNI->def.isEarlyClobber()) { 1431263509Sdim report("Early clobber def must be at an early-clobber slot", MBB, LR); 1432263509Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1433263509Sdim } 1434263509Sdim } else if (!VNI->def.isRegister()) { 1435263509Sdim report("Non-PHI, non-early clobber def must be at a register slot", 1436263509Sdim MBB, LR); 1437245431Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1438245431Sdim } 1439245431Sdim } 1440245431Sdim} 1441212904Sdim 1442263509Sdimvoid MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR, 1443263509Sdim const LiveRange::const_iterator I, 1444263509Sdim unsigned Reg) { 1445263509Sdim const LiveRange::Segment &S = *I; 1446263509Sdim const VNInfo *VNI = S.valno; 1447263509Sdim assert(VNI && "Live segment has no valno"); 1448212904Sdim 1449263509Sdim if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) { 1450263509Sdim report("Foreign valno in live segment", MF, LR); 1451263509Sdim *OS << S << " has a bad valno\n"; 1452245431Sdim } 1453218893Sdim 1454245431Sdim if (VNI->isUnused()) { 1455263509Sdim report("Live segment valno is marked unused", MF, LR); 1456263509Sdim *OS << S << '\n'; 1457245431Sdim } 1458235633Sdim 1459263509Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start); 1460245431Sdim if (!MBB) { 1461263509Sdim report("Bad start of live segment, no basic block", MF, LR); 1462263509Sdim *OS << S << '\n'; 1463245431Sdim return; 1464245431Sdim } 1465245431Sdim SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB); 1466263509Sdim if (S.start != MBBStartIdx && S.start != VNI->def) { 1467263509Sdim report("Live segment must begin at MBB entry or valno def", MBB, LR); 1468263509Sdim *OS << S << '\n'; 1469245431Sdim } 1470235633Sdim 1471245431Sdim const MachineBasicBlock *EndMBB = 1472263509Sdim LiveInts->getMBBFromIndex(S.end.getPrevSlot()); 1473245431Sdim if (!EndMBB) { 1474263509Sdim report("Bad end of live segment, no basic block", MF, LR); 1475263509Sdim *OS << S << '\n'; 1476245431Sdim return; 1477245431Sdim } 1478245431Sdim 1479245431Sdim // No more checks for live-out segments. 1480263509Sdim if (S.end == LiveInts->getMBBEndIdx(EndMBB)) 1481245431Sdim return; 1482245431Sdim 1483245431Sdim // RegUnit intervals are allowed dead phis. 1484263509Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() && 1485263509Sdim S.start == VNI->def && S.end == VNI->def.getDeadSlot()) 1486245431Sdim return; 1487245431Sdim 1488245431Sdim // The live segment is ending inside EndMBB 1489245431Sdim const MachineInstr *MI = 1490263509Sdim LiveInts->getInstructionFromIndex(S.end.getPrevSlot()); 1491245431Sdim if (!MI) { 1492263509Sdim report("Live segment doesn't end at a valid instruction", EndMBB, LR); 1493263509Sdim *OS << S << '\n'; 1494245431Sdim return; 1495245431Sdim } 1496245431Sdim 1497245431Sdim // The block slot must refer to a basic block boundary. 1498263509Sdim if (S.end.isBlock()) { 1499263509Sdim report("Live segment ends at B slot of an instruction", EndMBB, LR); 1500263509Sdim *OS << S << '\n'; 1501245431Sdim } 1502245431Sdim 1503263509Sdim if (S.end.isDead()) { 1504245431Sdim // Segment ends on the dead slot. 1505245431Sdim // That means there must be a dead def. 1506263509Sdim if (!SlotIndex::isSameInstr(S.start, S.end)) { 1507263509Sdim report("Live segment ending at dead slot spans instructions", EndMBB, LR); 1508263509Sdim *OS << S << '\n'; 1509245431Sdim } 1510245431Sdim } 1511245431Sdim 1512245431Sdim // A live segment can only end at an early-clobber slot if it is being 1513245431Sdim // redefined by an early-clobber def. 1514263509Sdim if (S.end.isEarlyClobber()) { 1515263509Sdim if (I+1 == LR.end() || (I+1)->start != S.end) { 1516245431Sdim report("Live segment ending at early clobber slot must be " 1517263509Sdim "redefined by an EC def in the same instruction", EndMBB, LR); 1518263509Sdim *OS << S << '\n'; 1519245431Sdim } 1520245431Sdim } 1521245431Sdim 1522245431Sdim // The following checks only apply to virtual registers. Physreg liveness 1523245431Sdim // is too weird to check. 1524263509Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1525263509Sdim // A live segment can end with either a redefinition, a kill flag on a 1526245431Sdim // use, or a dead flag on a def. 1527245431Sdim bool hasRead = false; 1528245431Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1529263509Sdim if (!MOI->isReg() || MOI->getReg() != Reg) 1530235633Sdim continue; 1531245431Sdim if (MOI->readsReg()) 1532245431Sdim hasRead = true; 1533245431Sdim } 1534263509Sdim if (!S.end.isDead()) { 1535245431Sdim if (!hasRead) { 1536263509Sdim report("Instruction ending live segment doesn't read the register", MI); 1537263509Sdim *OS << S << " in " << LR << '\n'; 1538235633Sdim } 1539245431Sdim } 1540245431Sdim } 1541235633Sdim 1542245431Sdim // Now check all the basic blocks in this live segment. 1543245431Sdim MachineFunction::const_iterator MFI = MBB; 1544263509Sdim // Is this live segment the beginning of a non-PHIDef VN? 1545263509Sdim if (S.start == VNI->def && !VNI->isPHIDef()) { 1546245431Sdim // Not live-in to any blocks. 1547245431Sdim if (MBB == EndMBB) 1548245431Sdim return; 1549245431Sdim // Skip this block. 1550245431Sdim ++MFI; 1551245431Sdim } 1552245431Sdim for (;;) { 1553263509Sdim assert(LiveInts->isLiveInToMBB(LR, MFI)); 1554245431Sdim // We don't know how to track physregs into a landing pad. 1555263509Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg) && 1556245431Sdim MFI->isLandingPad()) { 1557245431Sdim if (&*MFI == EndMBB) 1558245431Sdim break; 1559245431Sdim ++MFI; 1560245431Sdim continue; 1561245431Sdim } 1562235633Sdim 1563245431Sdim // Is VNI a PHI-def in the current block? 1564245431Sdim bool IsPHI = VNI->isPHIDef() && 1565245431Sdim VNI->def == LiveInts->getMBBStartIdx(MFI); 1566235633Sdim 1567245431Sdim // Check that VNI is live-out of all predecessors. 1568245431Sdim for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(), 1569245431Sdim PE = MFI->pred_end(); PI != PE; ++PI) { 1570245431Sdim SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI); 1571263509Sdim const VNInfo *PVNI = LR.getVNInfoBefore(PEnd); 1572245431Sdim 1573245431Sdim // All predecessors must have a live-out value. 1574245431Sdim if (!PVNI) { 1575263509Sdim report("Register not marked live out of predecessor", *PI, LR); 1576245431Sdim *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber() 1577245431Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before " 1578245431Sdim << PEnd << '\n'; 1579245431Sdim continue; 1580218893Sdim } 1581218893Sdim 1582245431Sdim // Only PHI-defs can take different predecessor values. 1583245431Sdim if (!IsPHI && PVNI != VNI) { 1584263509Sdim report("Different value live out of predecessor", *PI, LR); 1585245431Sdim *OS << "Valno #" << PVNI->id << " live out of BB#" 1586245431Sdim << (*PI)->getNumber() << '@' << PEnd 1587245431Sdim << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber() 1588245431Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << '\n'; 1589218893Sdim } 1590245431Sdim } 1591245431Sdim if (&*MFI == EndMBB) 1592245431Sdim break; 1593245431Sdim ++MFI; 1594245431Sdim } 1595245431Sdim} 1596218893Sdim 1597263509Sdimvoid MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg) { 1598263509Sdim for (LiveRange::const_vni_iterator I = LR.vni_begin(), E = LR.vni_end(); 1599263509Sdim I != E; ++I) 1600263509Sdim verifyLiveRangeValue(LR, *I, Reg); 1601263509Sdim 1602263509Sdim for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I) 1603263509Sdim verifyLiveRangeSegment(LR, I, Reg); 1604263509Sdim} 1605263509Sdim 1606245431Sdimvoid MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { 1607263509Sdim verifyLiveRange(LI, LI.reg); 1608218893Sdim 1609245431Sdim // Check the LI only has one connected component. 1610245431Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1611245431Sdim ConnectedVNInfoEqClasses ConEQ(*LiveInts); 1612245431Sdim unsigned NumComp = ConEQ.Classify(&LI); 1613245431Sdim if (NumComp > 1) { 1614245431Sdim report("Multiple connected components in live interval", MF, LI); 1615245431Sdim for (unsigned comp = 0; comp != NumComp; ++comp) { 1616245431Sdim *OS << comp << ": valnos"; 1617245431Sdim for (LiveInterval::const_vni_iterator I = LI.vni_begin(), 1618245431Sdim E = LI.vni_end(); I!=E; ++I) 1619245431Sdim if (comp == ConEQ.getEqClass(*I)) 1620245431Sdim *OS << ' ' << (*I)->id; 1621245431Sdim *OS << '\n'; 1622218893Sdim } 1623212904Sdim } 1624212904Sdim } 1625212904Sdim} 1626263509Sdim 1627263509Sdimnamespace { 1628263509Sdim // FrameSetup and FrameDestroy can have zero adjustment, so using a single 1629263509Sdim // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the 1630263509Sdim // value is zero. 1631263509Sdim // We use a bool plus an integer to capture the stack state. 1632263509Sdim struct StackStateOfBB { 1633263509Sdim StackStateOfBB() : EntryValue(0), ExitValue(0), EntryIsSetup(false), 1634263509Sdim ExitIsSetup(false) { } 1635263509Sdim StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) : 1636263509Sdim EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup), 1637263509Sdim ExitIsSetup(ExitSetup) { } 1638263509Sdim // Can be negative, which means we are setting up a frame. 1639263509Sdim int EntryValue; 1640263509Sdim int ExitValue; 1641263509Sdim bool EntryIsSetup; 1642263509Sdim bool ExitIsSetup; 1643263509Sdim }; 1644263509Sdim} 1645263509Sdim 1646263509Sdim/// Make sure on every path through the CFG, a FrameSetup <n> is always followed 1647263509Sdim/// by a FrameDestroy <n>, stack adjustments are identical on all 1648263509Sdim/// CFG edges to a merge point, and frame is destroyed at end of a return block. 1649263509Sdimvoid MachineVerifier::verifyStackFrame() { 1650263509Sdim int FrameSetupOpcode = TII->getCallFrameSetupOpcode(); 1651263509Sdim int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode(); 1652263509Sdim 1653263509Sdim SmallVector<StackStateOfBB, 8> SPState; 1654263509Sdim SPState.resize(MF->getNumBlockIDs()); 1655263509Sdim SmallPtrSet<const MachineBasicBlock*, 8> Reachable; 1656263509Sdim 1657263509Sdim // Visit the MBBs in DFS order. 1658263509Sdim for (df_ext_iterator<const MachineFunction*, 1659263509Sdim SmallPtrSet<const MachineBasicBlock*, 8> > 1660263509Sdim DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable); 1661263509Sdim DFI != DFE; ++DFI) { 1662263509Sdim const MachineBasicBlock *MBB = *DFI; 1663263509Sdim 1664263509Sdim StackStateOfBB BBState; 1665263509Sdim // Check the exit state of the DFS stack predecessor. 1666263509Sdim if (DFI.getPathLength() >= 2) { 1667263509Sdim const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); 1668263509Sdim assert(Reachable.count(StackPred) && 1669263509Sdim "DFS stack predecessor is already visited.\n"); 1670263509Sdim BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue; 1671263509Sdim BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup; 1672263509Sdim BBState.ExitValue = BBState.EntryValue; 1673263509Sdim BBState.ExitIsSetup = BBState.EntryIsSetup; 1674263509Sdim } 1675263509Sdim 1676263509Sdim // Update stack state by checking contents of MBB. 1677263509Sdim for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 1678263509Sdim I != E; ++I) { 1679263509Sdim if (I->getOpcode() == FrameSetupOpcode) { 1680263509Sdim // The first operand of a FrameOpcode should be i32. 1681263509Sdim int Size = I->getOperand(0).getImm(); 1682263509Sdim assert(Size >= 0 && 1683263509Sdim "Value should be non-negative in FrameSetup and FrameDestroy.\n"); 1684263509Sdim 1685263509Sdim if (BBState.ExitIsSetup) 1686263509Sdim report("FrameSetup is after another FrameSetup", I); 1687263509Sdim BBState.ExitValue -= Size; 1688263509Sdim BBState.ExitIsSetup = true; 1689263509Sdim } 1690263509Sdim 1691263509Sdim if (I->getOpcode() == FrameDestroyOpcode) { 1692263509Sdim // The first operand of a FrameOpcode should be i32. 1693263509Sdim int Size = I->getOperand(0).getImm(); 1694263509Sdim assert(Size >= 0 && 1695263509Sdim "Value should be non-negative in FrameSetup and FrameDestroy.\n"); 1696263509Sdim 1697263509Sdim if (!BBState.ExitIsSetup) 1698263509Sdim report("FrameDestroy is not after a FrameSetup", I); 1699263509Sdim int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue : 1700263509Sdim BBState.ExitValue; 1701263509Sdim if (BBState.ExitIsSetup && AbsSPAdj != Size) { 1702263509Sdim report("FrameDestroy <n> is after FrameSetup <m>", I); 1703263509Sdim *OS << "FrameDestroy <" << Size << "> is after FrameSetup <" 1704263509Sdim << AbsSPAdj << ">.\n"; 1705263509Sdim } 1706263509Sdim BBState.ExitValue += Size; 1707263509Sdim BBState.ExitIsSetup = false; 1708263509Sdim } 1709263509Sdim } 1710263509Sdim SPState[MBB->getNumber()] = BBState; 1711263509Sdim 1712263509Sdim // Make sure the exit state of any predecessor is consistent with the entry 1713263509Sdim // state. 1714263509Sdim for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 1715263509Sdim E = MBB->pred_end(); I != E; ++I) { 1716263509Sdim if (Reachable.count(*I) && 1717263509Sdim (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue || 1718263509Sdim SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) { 1719263509Sdim report("The exit stack state of a predecessor is inconsistent.", MBB); 1720263509Sdim *OS << "Predecessor BB#" << (*I)->getNumber() << " has exit state (" 1721263509Sdim << SPState[(*I)->getNumber()].ExitValue << ", " 1722263509Sdim << SPState[(*I)->getNumber()].ExitIsSetup 1723263509Sdim << "), while BB#" << MBB->getNumber() << " has entry state (" 1724263509Sdim << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n"; 1725263509Sdim } 1726263509Sdim } 1727263509Sdim 1728263509Sdim // Make sure the entry state of any successor is consistent with the exit 1729263509Sdim // state. 1730263509Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 1731263509Sdim E = MBB->succ_end(); I != E; ++I) { 1732263509Sdim if (Reachable.count(*I) && 1733263509Sdim (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue || 1734263509Sdim SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) { 1735263509Sdim report("The entry stack state of a successor is inconsistent.", MBB); 1736263509Sdim *OS << "Successor BB#" << (*I)->getNumber() << " has entry state (" 1737263509Sdim << SPState[(*I)->getNumber()].EntryValue << ", " 1738263509Sdim << SPState[(*I)->getNumber()].EntryIsSetup 1739263509Sdim << "), while BB#" << MBB->getNumber() << " has exit state (" 1740263509Sdim << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n"; 1741263509Sdim } 1742263509Sdim } 1743263509Sdim 1744263509Sdim // Make sure a basic block with return ends with zero stack adjustment. 1745263509Sdim if (!MBB->empty() && MBB->back().isReturn()) { 1746263509Sdim if (BBState.ExitIsSetup) 1747263509Sdim report("A return block ends with a FrameSetup.", MBB); 1748263509Sdim if (BBState.ExitValue) 1749263509Sdim report("A return block ends with a nonzero stack adjustment.", MBB); 1750263509Sdim } 1751263509Sdim } 1752263509Sdim} 1753