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 26249423Sdim#include "llvm/CodeGen/Passes.h" 27249423Sdim#include "llvm/ADT/DenseSet.h" 28263508Sdim#include "llvm/ADT/DepthFirstIterator.h" 29249423Sdim#include "llvm/ADT/SetOperations.h" 30249423Sdim#include "llvm/ADT/SmallVector.h" 31212904Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 32249423Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 33193323Sed#include "llvm/CodeGen/LiveVariables.h" 34249423Sdim#include "llvm/CodeGen/MachineFrameInfo.h" 35249423Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 36234353Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 37198090Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 38193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 39249423Sdim#include "llvm/IR/BasicBlock.h" 40249423Sdim#include "llvm/IR/InlineAsm.h" 41249423Sdim#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" 46249423Sdim#include "llvm/Target/TargetInstrInfo.h" 47249423Sdim#include "llvm/Target/TargetMachine.h" 48249423Sdim#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; 75234353Sdim typedef SmallVector<const uint32_t*, 4> RegMaskVector; 76193323Sed typedef DenseSet<unsigned> RegSet; 77193323Sed typedef DenseMap<unsigned, const MachineInstr*> RegMap; 78243830Sdim typedef SmallPtrSet<const MachineBasicBlock*, 8> BlockSet; 79193323Sed 80226633Sdim const MachineInstr *FirstTerminator; 81243830Sdim BlockSet FunctionBlocks; 82226633Sdim 83193323Sed BitVector regsReserved; 84193323Sed RegSet regsLive; 85198090Srdivacky RegVector regsDefined, regsDead, regsKilled; 86234353Sdim 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)) 95239462Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 96239462Sdim 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 123243830Sdim // Set versions of block's predecessor and successor lists. 124243830Sdim BlockSet Preds, Succs; 125243830Sdim 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 188234353Sdim bool isAllocatable(unsigned Reg) { 189243830Sdim return Reg < TRI->getNumRegs() && MRI->isAllocatable(Reg); 190234353Sdim } 191234353Sdim 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); 200239462Sdim 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); 204239462Sdim 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); 212239462Sdim void report(const char *msg, const MachineFunction *MF, 213239462Sdim const LiveInterval &LI); 214239462Sdim void report(const char *msg, const MachineBasicBlock *MBB, 215239462Sdim const LiveInterval &LI); 216263508Sdim void report(const char *msg, const MachineFunction *MF, 217263508Sdim const LiveRange &LR); 218263508Sdim void report(const char *msg, const MachineBasicBlock *MBB, 219263508Sdim const LiveRange &LR); 220193323Sed 221243830Sdim void verifyInlineAsm(const MachineInstr *MI); 222243830Sdim 223234353Sdim 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(); 231239462Sdim void verifyLiveInterval(const LiveInterval&); 232263508Sdim void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned); 233263508Sdim void verifyLiveRangeSegment(const LiveRange&, 234263508Sdim const LiveRange::const_iterator I, unsigned); 235263508Sdim void verifyLiveRange(const LiveRange&, unsigned); 236263508Sdim 237263508Sdim 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; 279263508Sdim 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); 315239462Sdim // Keep track of the current bundle header. 316239462Sdim const MachineInstr *CurBundle = 0; 317249423Sdim // Do we expect the next instruction to be part of the same bundle? 318249423Sdim bool InBundle = false; 319249423Sdim 320234353Sdim for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), 321234353Sdim 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 } 327249423Sdim 328249423Sdim // Check for consistent bundle flags. 329249423Sdim if (InBundle && !MBBI->isBundledWithPred()) 330249423Sdim report("Missing BundledPred flag, " 331249423Sdim "BundledSucc was set on predecessor", MBBI); 332249423Sdim if (!InBundle && MBBI->isBundledWithPred()) 333249423Sdim report("BundledPred flag is set, " 334249423Sdim "but BundledSucc not set on predecessor", MBBI); 335249423Sdim 336239462Sdim // Is this a bundle header? 337239462Sdim if (!MBBI->isInsideBundle()) { 338239462Sdim if (CurBundle) 339239462Sdim visitMachineBundleAfter(CurBundle); 340239462Sdim CurBundle = MBBI; 341239462Sdim visitMachineBundleBefore(CurBundle); 342239462Sdim } else if (!CurBundle) 343239462Sdim 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); 348249423Sdim 349249423Sdim // Was this the last bundled instruction? 350249423Sdim InBundle = MBBI->isBundledWithSucc(); 351193323Sed } 352239462Sdim if (CurBundle) 353239462Sdim visitMachineBundleAfter(CurBundle); 354249423Sdim if (InBundle) 355249423Sdim 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(); 370234353Sdim 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" 386243830Sdim << "- function: " << MF->getName() << "\n"; 387193323Sed} 388193323Sed 389198090Srdivackyvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { 390193323Sed assert(MBB); 391193323Sed report(msg, MBB->getParent()); 392239462Sdim *OS << "- basic block: BB#" << MBB->getNumber() 393239462Sdim << ' ' << MBB->getName() 394243830Sdim << " (" << (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 419239462Sdimvoid MachineVerifier::report(const char *msg, const MachineFunction *MF, 420239462Sdim const LiveInterval &LI) { 421239462Sdim report(msg, MF); 422263508Sdim *OS << "- interval: " << LI << '\n'; 423239462Sdim} 424239462Sdim 425239462Sdimvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, 426239462Sdim const LiveInterval &LI) { 427239462Sdim report(msg, MBB); 428263508Sdim *OS << "- interval: " << LI << '\n'; 429239462Sdim} 430239462Sdim 431263508Sdimvoid MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, 432263508Sdim const LiveRange &LR) { 433263508Sdim report(msg, MBB); 434263508Sdim *OS << "- liverange: " << LR << "\n"; 435263508Sdim} 436263508Sdim 437263508Sdimvoid MachineVerifier::report(const char *msg, const MachineFunction *MF, 438263508Sdim const LiveRange &LR) { 439263508Sdim report(msg, MF); 440263508Sdim *OS << "- liverange: " << LR << "\n"; 441263508Sdim} 442263508Sdim 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(); 455243830Sdim 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)) { 460239462Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 461198090Srdivacky // FIXME: This should probably be: 462239462Sdim // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register"); 463239462Sdim regsReserved.set(*SubRegs); 464198090Srdivacky } 465198090Srdivacky } 466234353Sdim 467243830Sdim markReachable(&MF->front()); 468234353Sdim 469243830Sdim // Build a set of the basic blocks in the function. 470243830Sdim FunctionBlocks.clear(); 471243830Sdim for (MachineFunction::const_iterator 472243830Sdim I = MF->begin(), E = MF->end(); I != E; ++I) { 473243830Sdim FunctionBlocks.insert(I); 474243830Sdim BBInfo &MInfo = MBBInfoMap[I]; 475243830Sdim 476243830Sdim MInfo.Preds.insert(I->pred_begin(), I->pred_end()); 477243830Sdim if (MInfo.Preds.size() != I->pred_size()) 478243830Sdim report("MBB has duplicate entries in its predecessor list.", I); 479243830Sdim 480243830Sdim MInfo.Succs.insert(I->succ_begin(), I->succ_end()); 481243830Sdim if (MInfo.Succs.size() != I->succ_size()) 482243830Sdim report("MBB has duplicate entries in its successor list.", I); 483243830Sdim } 484251662Sdim 485251662Sdim // Check that the register use lists are sane. 486251662Sdim MRI->verifyUseLists(); 487263508Sdim 488263508Sdim 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) { 503226633Sdim FirstTerminator = 0; 504226633Sdim 505234353Sdim if (MRI->isSSA()) { 506234353Sdim // If this block has allocatable physical registers live-in, check that 507234353Sdim // it is an entry block or landing pad. 508234353Sdim for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 509234353Sdim LE = MBB->livein_end(); 510234353Sdim LI != LE; ++LI) { 511234353Sdim unsigned reg = *LI; 512234353Sdim if (isAllocatable(reg) && !MBB->isLandingPad() && 513234353Sdim MBB != MBB->getParent()->begin()) { 514234353Sdim report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB); 515234353Sdim } 516234353Sdim } 517234353Sdim } 518234353Sdim 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); 525243830Sdim if (!FunctionBlocks.count(*I)) 526243830Sdim report("MBB has successor that isn't part of the function.", MBB); 527243830Sdim if (!MBBInfoMap[*I].Preds.count(MBB)) { 528243830Sdim report("Inconsistent CFG", MBB); 529243830Sdim *OS << "MBB is not in the predecessor list of the successor BB#" 530243830Sdim << (*I)->getNumber() << ".\n"; 531243830Sdim } 532218893Sdim } 533223017Sdim 534243830Sdim // Check the predecessor list. 535243830Sdim for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 536243830Sdim E = MBB->pred_end(); I != E; ++I) { 537243830Sdim if (!FunctionBlocks.count(*I)) 538243830Sdim report("MBB has predecessor that isn't part of the function.", MBB); 539243830Sdim if (!MBBInfoMap[*I].Succs.count(MBB)) { 540243830Sdim report("Inconsistent CFG", MBB); 541243830Sdim *OS << "MBB is not in the successor list of the predecessor BB#" 542243830Sdim << (*I)->getNumber() << ".\n"; 543243830Sdim } 544243830Sdim } 545243830Sdim 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 } 580239462Sdim if (!MBB->empty() && getBundleStart(&MBB->back())->isBarrier() && 581239462Sdim !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); 601239462Sdim } else if (!getBundleStart(&MBB->back())->isBarrier()) { 602198090Srdivacky report("MBB exits via unconditional branch but doesn't end with a " 603198090Srdivacky "barrier instruction!", MBB); 604239462Sdim } 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); 614249423Sdim } else if (MBB->succ_size() == 1) { 615243830Sdim // A conditional branch with only one successor is weird, but allowed. 616243830Sdim if (&*MBBI != TBB) 617243830Sdim report("MBB exits via conditional branch/fall-through but only has " 618243830Sdim "one CFG successor!", MBB); 619243830Sdim else if (TBB != *MBB->succ_begin()) 620243830Sdim report("MBB exits via conditional branch/fall-through but the CFG " 621243830Sdim "successor don't match the actual successor!", MBB); 622243830Sdim } 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); 632239462Sdim } else if (getBundleStart(&MBB->back())->isBarrier()) { 633198090Srdivacky report("MBB exits via conditional branch/fall-through but ends with a " 634198090Srdivacky "barrier instruction!", MBB); 635239462Sdim } 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. 642243830Sdim if (MBB->succ_size() == 1) { 643243830Sdim // A conditional branch with only one successor is weird, but allowed. 644243830Sdim if (FBB != TBB) 645243830Sdim report("MBB exits via conditional branch/branch through but only has " 646243830Sdim "one CFG successor!", MBB); 647243830Sdim else if (TBB != *MBB->succ_begin()) 648243830Sdim report("MBB exits via conditional branch/branch through but the CFG " 649243830Sdim "successor don't match the actual successor!", MBB); 650243830Sdim } 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); 660239462Sdim } else if (!getBundleStart(&MBB->back())->isBarrier()) { 661198090Srdivacky report("MBB exits via conditional branch/branch but doesn't end with a " 662198090Srdivacky "barrier instruction!", MBB); 663239462Sdim } 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 } 683263508Sdim for (MCSubRegIterator SubRegs(*I, TRI, /*IncludeSelf=*/true); 684263508Sdim SubRegs.isValid(); ++SubRegs) 685239462Sdim 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)) { 693263508Sdim for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true); 694263508Sdim SubRegs.isValid(); ++SubRegs) 695239462Sdim regsLive.insert(*SubRegs); 696198090Srdivacky } 697198090Srdivacky 698193323Sed regsKilled.clear(); 699193323Sed regsDefined.clear(); 700218893Sdim 701218893Sdim if (Indexes) 702218893Sdim lastIndex = Indexes->getMBBStartIdx(MBB); 703193323Sed} 704193323Sed 705239462Sdim// This function gets called for all bundle headers, including normal 706239462Sdim// stand-alone unbundled instructions. 707239462Sdimvoid MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) { 708239462Sdim if (Indexes && Indexes->hasIndex(MI)) { 709239462Sdim SlotIndex idx = Indexes->getInstructionIndex(MI); 710239462Sdim if (!(idx > lastIndex)) { 711239462Sdim report("Instruction index out of order", MI); 712239462Sdim *OS << "Last instruction was at " << lastIndex << '\n'; 713239462Sdim } 714239462Sdim lastIndex = idx; 715239462Sdim } 716239462Sdim 717239462Sdim // Ensure non-terminators don't follow terminators. 718239462Sdim // Ignore predicated terminators formed by if conversion. 719239462Sdim // FIXME: If conversion shouldn't need to violate this rule. 720239462Sdim if (MI->isTerminator() && !TII->isPredicated(MI)) { 721239462Sdim if (!FirstTerminator) 722239462Sdim FirstTerminator = MI; 723239462Sdim } else if (FirstTerminator) { 724239462Sdim report("Non-terminator instruction after the first terminator", MI); 725239462Sdim *OS << "First terminator was:\t" << *FirstTerminator; 726239462Sdim } 727239462Sdim} 728239462Sdim 729243830Sdim// The operands on an INLINEASM instruction must follow a template. 730243830Sdim// Verify that the flag operands make sense. 731243830Sdimvoid MachineVerifier::verifyInlineAsm(const MachineInstr *MI) { 732243830Sdim // The first two operands on INLINEASM are the asm string and global flags. 733243830Sdim if (MI->getNumOperands() < 2) { 734243830Sdim report("Too few operands on inline asm", MI); 735243830Sdim return; 736243830Sdim } 737243830Sdim if (!MI->getOperand(0).isSymbol()) 738243830Sdim report("Asm string must be an external symbol", MI); 739243830Sdim if (!MI->getOperand(1).isImm()) 740243830Sdim report("Asm flags must be an immediate", MI); 741243830Sdim // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2, 742243830Sdim // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16. 743243830Sdim if (!isUInt<5>(MI->getOperand(1).getImm())) 744243830Sdim report("Unknown asm flags", &MI->getOperand(1), 1); 745243830Sdim 746243830Sdim assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed"); 747243830Sdim 748243830Sdim unsigned OpNo = InlineAsm::MIOp_FirstOperand; 749243830Sdim unsigned NumOps; 750243830Sdim for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) { 751243830Sdim const MachineOperand &MO = MI->getOperand(OpNo); 752243830Sdim // There may be implicit ops after the fixed operands. 753243830Sdim if (!MO.isImm()) 754243830Sdim break; 755243830Sdim NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm()); 756243830Sdim } 757243830Sdim 758243830Sdim if (OpNo > MI->getNumOperands()) 759243830Sdim report("Missing operands in last group", MI); 760243830Sdim 761243830Sdim // An optional MDNode follows the groups. 762243830Sdim if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata()) 763243830Sdim ++OpNo; 764243830Sdim 765243830Sdim // All trailing operands must be implicit registers. 766243830Sdim for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) { 767243830Sdim const MachineOperand &MO = MI->getOperand(OpNo); 768243830Sdim if (!MO.isReg() || !MO.isImplicit()) 769243830Sdim report("Expected implicit register after groups", &MO, OpNo); 770243830Sdim } 771243830Sdim} 772243830Sdim 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 " 778263508Sdim << MI->getNumOperands() << " given.\n"; 779193323Sed } 780198090Srdivacky 781243830Sdim // Check the tied operands. 782243830Sdim if (MI->isInlineAsm()) 783243830Sdim verifyInlineAsm(MI); 784243830Sdim 785198090Srdivacky // Check the MachineMemOperands for basic consistency. 786198090Srdivacky for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 787198090Srdivacky E = MI->memoperands_end(); I != E; ++I) { 788234353Sdim if ((*I)->isLoad() && !MI->mayLoad()) 789198090Srdivacky report("Missing mayLoad flag", MI); 790234353Sdim if ((*I)->isStore() && !MI->mayStore()) 791198090Srdivacky report("Missing mayStore flag", MI); 792193323Sed } 793212904Sdim 794212904Sdim // Debug values must not have a slot index. 795234353Sdim // 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); 801234353Sdim } else if (MI->isInsideBundle()) { 802234353Sdim if (mapped) 803234353Sdim report("Instruction inside bundle has a slot index", MI); 804212904Sdim } else { 805212904Sdim if (!mapped) 806212904Sdim report("Missing slot index", MI); 807212904Sdim } 808212904Sdim } 809212904Sdim 810226633Sdim StringRef ErrorInfo; 811226633Sdim if (!TII->verifyInstruction(MI, ErrorInfo)) 812226633Sdim 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()) { 822239462Sdim const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 823193323Sed if (!MO->isReg()) 824193323Sed report("Explicit definition must be a register", MO, MONum); 825239462Sdim 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()) { 830239462Sdim 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() && 834234353Sdim !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { 835224145Sdim if (MO->isDef() && !MCOI.isOptionalDef()) 836263508Sdim report("Explicit operand marked as def", MO, MONum); 837198090Srdivacky if (MO->isImplicit()) 838198090Srdivacky report("Explicit operand marked as implicit", MO, MONum); 839198090Srdivacky } 840243830Sdim 841243830Sdim int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO); 842243830Sdim if (TiedTo != -1) { 843243830Sdim if (!MO->isReg()) 844243830Sdim report("Tied use must be a register", MO, MONum); 845243830Sdim else if (!MO->isTied()) 846243830Sdim report("Operand should be tied", MO, MONum); 847243830Sdim else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum)) 848243830Sdim report("Tied def doesn't match MCInstrDesc", MO, MONum); 849243830Sdim } else if (MO->isReg() && MO->isTied()) 850243830Sdim report("Explicit operand should not be tied", MO, MONum); 851198090Srdivacky } else { 852201360Srdivacky // ARM adds %reg0 operands to indicate predicates. We'll allow that. 853234353Sdim 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; 862234353Sdim if (MRI->tracksLiveness() && !MI->isDebugValue()) 863234353Sdim checkLiveness(MO, MONum); 864193323Sed 865243830Sdim // Verify the consistency of tied operands. 866243830Sdim if (MO->isTied()) { 867243830Sdim unsigned OtherIdx = MI->findTiedOperandIdx(MONum); 868243830Sdim const MachineOperand &OtherMO = MI->getOperand(OtherIdx); 869243830Sdim if (!OtherMO.isReg()) 870243830Sdim report("Must be tied to a register", MO, MONum); 871243830Sdim if (!OtherMO.isTied()) 872243830Sdim report("Missing tie flags on tied operand", MO, MONum); 873243830Sdim if (MI->findTiedOperandIdx(OtherIdx) != MONum) 874243830Sdim report("Inconsistent tie links", MO, MONum); 875243830Sdim if (MONum < MCID.getNumDefs()) { 876243830Sdim if (OtherIdx < MCID.getNumOperands()) { 877243830Sdim if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO)) 878243830Sdim report("Explicit def tied to explicit use without tie constraint", 879243830Sdim MO, MONum); 880243830Sdim } else { 881243830Sdim if (!OtherMO.isImplicit()) 882243830Sdim report("Explicit def should be tied to implicit use", MO, MONum); 883243830Sdim } 884243830Sdim } 885243830Sdim } 886243830Sdim 887239462Sdim // Verify two-address constraints after leaving SSA form. 888239462Sdim unsigned DefIdx; 889239462Sdim if (!MRI->isSSA() && MO->isUse() && 890239462Sdim MI->isRegTiedToDefOperand(MONum, &DefIdx) && 891239462Sdim Reg != MI->getOperand(DefIdx).getReg()) 892239462Sdim report("Two-address instruction operands must be identical", MO, MONum); 893198090Srdivacky 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) { 900226633Sdim report("Illegal subregister index for physical register", MO, MONum); 901226633Sdim return; 902193323Sed } 903239462Sdim if (const TargetRegisterClass *DRC = 904239462Sdim TII->getRegClass(MCID, MONum, TRI, *MF)) { 905226633Sdim if (!DRC->contains(Reg)) { 906193323Sed report("Illegal physical register for instruction", MO, MONum); 907226633Sdim *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) { 915226633Sdim const TargetRegisterClass *SRC = 916226633Sdim 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 } 923226633Sdim if (RC != SRC) { 924226633Sdim report("Invalid register class for subregister index", MO, MONum); 925226633Sdim *OS << "Register class " << RC->getName() 926226633Sdim << " does not fully support subreg index " << SubIdx << "\n"; 927226633Sdim return; 928226633Sdim } 929193323Sed } 930239462Sdim if (const TargetRegisterClass *DRC = 931239462Sdim TII->getRegClass(MCID, MONum, TRI, *MF)) { 932226633Sdim if (SubIdx) { 933226633Sdim const TargetRegisterClass *SuperRC = 934226633Sdim TRI->getLargestLegalSuperClass(RC); 935226633Sdim if (!SuperRC) { 936226633Sdim report("No largest legal super class exists.", MO, MONum); 937226633Sdim return; 938226633Sdim } 939226633Sdim DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx); 940226633Sdim if (!DRC) { 941226633Sdim report("No matching super-reg register class.", MO, MONum); 942226633Sdim return; 943226633Sdim } 944226633Sdim } 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 956234353Sdim case MachineOperand::MO_RegisterMask: 957234353Sdim regMasks.push_back(MO->getRegMask()); 958234353Sdim break; 959234353Sdim 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); 970234353Sdim 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 } 974234353Sdim 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 986234353Sdimvoid MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { 987234353Sdim const MachineInstr *MI = MO->getParent(); 988234353Sdim const unsigned Reg = MO->getReg(); 989234353Sdim 990234353Sdim // Both use and def operands can read a register. 991234353Sdim if (MO->readsReg()) { 992234353Sdim regsLiveInButUnused.erase(Reg); 993234353Sdim 994239462Sdim if (MO->isKill()) 995234353Sdim addRegWithSubRegs(regsKilled, Reg); 996234353Sdim 997234353Sdim // Check that LiveVars knows this kill. 998234353Sdim if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) && 999234353Sdim MO->isKill()) { 1000234353Sdim LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1001234353Sdim if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end()) 1002234353Sdim report("Kill missing from LiveVariables", MO, MONum); 1003234353Sdim } 1004234353Sdim 1005234353Sdim // Check LiveInts liveness and kill. 1006239462Sdim if (LiveInts && !LiveInts->isNotInMIMap(MI)) { 1007239462Sdim SlotIndex UseIdx = LiveInts->getInstructionIndex(MI); 1008239462Sdim // Check the cached regunit intervals. 1009239462Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) { 1010239462Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 1011263508Sdim if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units)) { 1012263508Sdim LiveQueryResult LRQ = LR->Query(UseIdx); 1013239462Sdim if (!LRQ.valueIn()) { 1014263508Sdim report("No live segment at use", MO, MONum); 1015239462Sdim *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI) 1016263508Sdim << ' ' << *LR << '\n'; 1017239462Sdim } 1018239462Sdim if (MO->isKill() && !LRQ.isKill()) { 1019239462Sdim report("Live range continues after kill flag", MO, MONum); 1020263508Sdim *OS << PrintRegUnit(*Units, TRI) << ' ' << *LR << '\n'; 1021239462Sdim } 1022239462Sdim } 1023234353Sdim } 1024239462Sdim } 1025239462Sdim 1026239462Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1027239462Sdim if (LiveInts->hasInterval(Reg)) { 1028239462Sdim // This is a virtual register interval. 1029239462Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1030263508Sdim LiveQueryResult LRQ = LI.Query(UseIdx); 1031239462Sdim if (!LRQ.valueIn()) { 1032263508Sdim report("No live segment at use", MO, MONum); 1033239462Sdim *OS << UseIdx << " is not live in " << LI << '\n'; 1034239462Sdim } 1035239462Sdim // Check for extra kill flags. 1036239462Sdim // Note that we allow missing kill flags for now. 1037239462Sdim if (MO->isKill() && !LRQ.isKill()) { 1038239462Sdim report("Live range continues after kill flag", MO, MONum); 1039239462Sdim *OS << "Live range: " << LI << '\n'; 1040239462Sdim } 1041239462Sdim } else { 1042239462Sdim report("Virtual register has no live interval", MO, MONum); 1043234353Sdim } 1044234353Sdim } 1045234353Sdim } 1046234353Sdim 1047234353Sdim // Use of a dead register. 1048234353Sdim if (!regsLive.count(Reg)) { 1049234353Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 1050234353Sdim // Reserved registers may be used even when 'dead'. 1051234353Sdim if (!isReserved(Reg)) 1052234353Sdim report("Using an undefined physical register", MO, MONum); 1053239462Sdim } else if (MRI->def_empty(Reg)) { 1054239462Sdim report("Reading virtual register without a def", MO, MONum); 1055234353Sdim } else { 1056234353Sdim BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1057234353Sdim // We don't know which virtual registers are live in, so only complain 1058234353Sdim // if vreg was killed in this MBB. Otherwise keep track of vregs that 1059234353Sdim // must be live in. PHI instructions are handled separately. 1060234353Sdim if (MInfo.regsKilled.count(Reg)) 1061234353Sdim report("Using a killed virtual register", MO, MONum); 1062234353Sdim else if (!MI->isPHI()) 1063234353Sdim MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 1064234353Sdim } 1065234353Sdim } 1066234353Sdim } 1067234353Sdim 1068234353Sdim if (MO->isDef()) { 1069234353Sdim // Register defined. 1070234353Sdim // TODO: verify that earlyclobber ops are not used. 1071234353Sdim if (MO->isDead()) 1072234353Sdim addRegWithSubRegs(regsDead, Reg); 1073234353Sdim else 1074234353Sdim addRegWithSubRegs(regsDefined, Reg); 1075234353Sdim 1076234353Sdim // Verify SSA form. 1077234353Sdim if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) && 1078234353Sdim llvm::next(MRI->def_begin(Reg)) != MRI->def_end()) 1079234353Sdim report("Multiple virtual register defs in SSA form", MO, MONum); 1080234353Sdim 1081263508Sdim // Check LiveInts for a live segment, but only for virtual registers. 1082234353Sdim if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) && 1083234353Sdim !LiveInts->isNotInMIMap(MI)) { 1084239462Sdim SlotIndex DefIdx = LiveInts->getInstructionIndex(MI); 1085239462Sdim DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber()); 1086234353Sdim if (LiveInts->hasInterval(Reg)) { 1087234353Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1088234353Sdim if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) { 1089234353Sdim assert(VNI && "NULL valno is not allowed"); 1090239462Sdim if (VNI->def != DefIdx) { 1091234353Sdim report("Inconsistent valno->def", MO, MONum); 1092234353Sdim *OS << "Valno " << VNI->id << " is not defined at " 1093234353Sdim << DefIdx << " in " << LI << '\n'; 1094234353Sdim } 1095234353Sdim } else { 1096263508Sdim report("No live segment at def", MO, MONum); 1097234353Sdim *OS << DefIdx << " is not live in " << LI << '\n'; 1098234353Sdim } 1099263508Sdim // Check that, if the dead def flag is present, LiveInts agree. 1100263508Sdim if (MO->isDead()) { 1101263508Sdim LiveQueryResult LRQ = LI.Query(DefIdx); 1102263508Sdim if (!LRQ.isDeadDef()) { 1103263508Sdim report("Live range continues after dead def flag", MO, MONum); 1104263508Sdim *OS << "Live range: " << LI << '\n'; 1105263508Sdim } 1106263508Sdim } 1107234353Sdim } else { 1108234353Sdim report("Virtual register has no Live interval", MO, MONum); 1109234353Sdim } 1110234353Sdim } 1111234353Sdim } 1112234353Sdim} 1113234353Sdim 1114198090Srdivackyvoid MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { 1115239462Sdim} 1116239462Sdim 1117239462Sdim// This function gets called after visiting all instructions in a bundle. The 1118239462Sdim// argument points to the bundle header. 1119239462Sdim// Normal stand-alone instructions are also considered 'bundles', and this 1120239462Sdim// function is called for all of them. 1121239462Sdimvoid MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) { 1122193323Sed BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1123193323Sed set_union(MInfo.regsKilled, regsKilled); 1124212904Sdim set_subtract(regsLive, regsKilled); regsKilled.clear(); 1125234353Sdim // Kill any masked registers. 1126234353Sdim while (!regMasks.empty()) { 1127234353Sdim const uint32_t *Mask = regMasks.pop_back_val(); 1128234353Sdim for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I) 1129234353Sdim if (TargetRegisterInfo::isPhysicalRegister(*I) && 1130234353Sdim MachineOperand::clobbersPhysReg(Mask, *I)) 1131234353Sdim regsDead.push_back(*I); 1132234353Sdim } 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. 1159234353Sdim 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. 1196234353Sdim 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) { 1229234353Sdim SmallPtrSet<const MachineBasicBlock*, 8> seen; 1230193323Sed for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 1231203954Srdivacky BBI != BBE && BBI->isPHI(); ++BBI) { 1232234353Sdim 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 1273234353Sdim calcRegsRequired(); 1274234353Sdim 1275239462Sdim // Check for killed virtual registers that should be live out. 1276239462Sdim for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1277239462Sdim MFI != MFE; ++MFI) { 1278239462Sdim BBInfo &MInfo = MBBInfoMap[MFI]; 1279239462Sdim for (RegSet::iterator 1280239462Sdim I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1281239462Sdim ++I) 1282239462Sdim if (MInfo.regsKilled.count(*I)) { 1283239462Sdim report("Virtual register killed in block, but needed live out.", MFI); 1284239462Sdim *OS << "Virtual register " << PrintReg(*I) 1285239462Sdim << " is used after the block.\n"; 1286239462Sdim } 1287239462Sdim } 1288239462Sdim 1289239462Sdim if (!MF->empty()) { 1290234353Sdim BBInfo &MInfo = MBBInfoMap[&MF->front()]; 1291234353Sdim for (RegSet::iterator 1292234353Sdim I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1293234353Sdim ++I) 1294234353Sdim report("Virtual register def doesn't dominate all uses.", 1295234353Sdim MRI->getVRegDef(*I)); 1296234353Sdim } 1297234353Sdim 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"); 1333239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1334239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1335218893Sdim 1336218893Sdim // Spilling and splitting may leave unused registers around. Skip them. 1337239462Sdim if (MRI->reg_nodbg_empty(Reg)) 1338218893Sdim continue; 1339218893Sdim 1340239462Sdim if (!LiveInts->hasInterval(Reg)) { 1341239462Sdim report("Missing live interval for virtual register", MF); 1342239462Sdim *OS << PrintReg(Reg, TRI) << " still has defs or uses\n"; 1343218893Sdim continue; 1344239462Sdim } 1345218893Sdim 1346239462Sdim const LiveInterval &LI = LiveInts->getInterval(Reg); 1347239462Sdim assert(Reg == LI.reg && "Invalid reg to interval mapping"); 1348239462Sdim verifyLiveInterval(LI); 1349239462Sdim } 1350199511Srdivacky 1351239462Sdim // Verify all the cached regunit intervals. 1352239462Sdim for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 1353263508Sdim if (const LiveRange *LR = LiveInts->getCachedRegUnit(i)) 1354263508Sdim verifyLiveRange(*LR, i); 1355239462Sdim} 1356212904Sdim 1357263508Sdimvoid MachineVerifier::verifyLiveRangeValue(const LiveRange &LR, 1358263508Sdim const VNInfo *VNI, 1359263508Sdim unsigned Reg) { 1360239462Sdim if (VNI->isUnused()) 1361239462Sdim return; 1362212904Sdim 1363263508Sdim const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def); 1364212904Sdim 1365239462Sdim if (!DefVNI) { 1366263508Sdim report("Valno not live at def and not marked unused", MF, LR); 1367239462Sdim *OS << "Valno #" << VNI->id << '\n'; 1368239462Sdim return; 1369239462Sdim } 1370212904Sdim 1371239462Sdim if (DefVNI != VNI) { 1372263508Sdim report("Live segment at def has different valno", MF, LR); 1373239462Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1374239462Sdim << " where valno #" << DefVNI->id << " is live\n"; 1375239462Sdim return; 1376239462Sdim } 1377218893Sdim 1378239462Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); 1379239462Sdim if (!MBB) { 1380263508Sdim report("Invalid definition index", MF, LR); 1381239462Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1382263508Sdim << " in " << LR << '\n'; 1383239462Sdim return; 1384239462Sdim } 1385218893Sdim 1386239462Sdim if (VNI->isPHIDef()) { 1387239462Sdim if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { 1388263508Sdim report("PHIDef value is not defined at MBB start", MBB, LR); 1389239462Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1390239462Sdim << ", not at the beginning of BB#" << MBB->getNumber() << '\n'; 1391239462Sdim } 1392239462Sdim return; 1393239462Sdim } 1394218893Sdim 1395239462Sdim // Non-PHI def. 1396239462Sdim const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); 1397239462Sdim if (!MI) { 1398263508Sdim report("No instruction at def index", MBB, LR); 1399239462Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1400239462Sdim return; 1401239462Sdim } 1402234353Sdim 1403263508Sdim if (Reg != 0) { 1404263508Sdim bool hasDef = false; 1405263508Sdim bool isEarlyClobber = false; 1406263508Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1407263508Sdim if (!MOI->isReg() || !MOI->isDef()) 1408239462Sdim continue; 1409263508Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1410263508Sdim if (MOI->getReg() != Reg) 1411263508Sdim continue; 1412263508Sdim } else { 1413263508Sdim if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || 1414263508Sdim !TRI->hasRegUnit(MOI->getReg(), Reg)) 1415263508Sdim continue; 1416263508Sdim } 1417263508Sdim hasDef = true; 1418263508Sdim if (MOI->isEarlyClobber()) 1419263508Sdim isEarlyClobber = true; 1420212904Sdim } 1421212904Sdim 1422263508Sdim if (!hasDef) { 1423263508Sdim report("Defining instruction does not modify register", MI); 1424263508Sdim *OS << "Valno #" << VNI->id << " in " << LR << '\n'; 1425263508Sdim } 1426212904Sdim 1427263508Sdim // Early clobber defs begin at USE slots, but other defs must begin at 1428263508Sdim // DEF slots. 1429263508Sdim if (isEarlyClobber) { 1430263508Sdim if (!VNI->def.isEarlyClobber()) { 1431263508Sdim report("Early clobber def must be at an early-clobber slot", MBB, LR); 1432263508Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1433263508Sdim } 1434263508Sdim } else if (!VNI->def.isRegister()) { 1435263508Sdim report("Non-PHI, non-early clobber def must be at a register slot", 1436263508Sdim MBB, LR); 1437239462Sdim *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1438239462Sdim } 1439239462Sdim } 1440239462Sdim} 1441212904Sdim 1442263508Sdimvoid MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR, 1443263508Sdim const LiveRange::const_iterator I, 1444263508Sdim unsigned Reg) { 1445263508Sdim const LiveRange::Segment &S = *I; 1446263508Sdim const VNInfo *VNI = S.valno; 1447263508Sdim assert(VNI && "Live segment has no valno"); 1448212904Sdim 1449263508Sdim if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) { 1450263508Sdim report("Foreign valno in live segment", MF, LR); 1451263508Sdim *OS << S << " has a bad valno\n"; 1452239462Sdim } 1453218893Sdim 1454239462Sdim if (VNI->isUnused()) { 1455263508Sdim report("Live segment valno is marked unused", MF, LR); 1456263508Sdim *OS << S << '\n'; 1457239462Sdim } 1458234353Sdim 1459263508Sdim const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start); 1460239462Sdim if (!MBB) { 1461263508Sdim report("Bad start of live segment, no basic block", MF, LR); 1462263508Sdim *OS << S << '\n'; 1463239462Sdim return; 1464239462Sdim } 1465239462Sdim SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB); 1466263508Sdim if (S.start != MBBStartIdx && S.start != VNI->def) { 1467263508Sdim report("Live segment must begin at MBB entry or valno def", MBB, LR); 1468263508Sdim *OS << S << '\n'; 1469239462Sdim } 1470234353Sdim 1471239462Sdim const MachineBasicBlock *EndMBB = 1472263508Sdim LiveInts->getMBBFromIndex(S.end.getPrevSlot()); 1473239462Sdim if (!EndMBB) { 1474263508Sdim report("Bad end of live segment, no basic block", MF, LR); 1475263508Sdim *OS << S << '\n'; 1476239462Sdim return; 1477239462Sdim } 1478239462Sdim 1479239462Sdim // No more checks for live-out segments. 1480263508Sdim if (S.end == LiveInts->getMBBEndIdx(EndMBB)) 1481239462Sdim return; 1482239462Sdim 1483239462Sdim // RegUnit intervals are allowed dead phis. 1484263508Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() && 1485263508Sdim S.start == VNI->def && S.end == VNI->def.getDeadSlot()) 1486239462Sdim return; 1487239462Sdim 1488239462Sdim // The live segment is ending inside EndMBB 1489239462Sdim const MachineInstr *MI = 1490263508Sdim LiveInts->getInstructionFromIndex(S.end.getPrevSlot()); 1491239462Sdim if (!MI) { 1492263508Sdim report("Live segment doesn't end at a valid instruction", EndMBB, LR); 1493263508Sdim *OS << S << '\n'; 1494239462Sdim return; 1495239462Sdim } 1496239462Sdim 1497239462Sdim // The block slot must refer to a basic block boundary. 1498263508Sdim if (S.end.isBlock()) { 1499263508Sdim report("Live segment ends at B slot of an instruction", EndMBB, LR); 1500263508Sdim *OS << S << '\n'; 1501239462Sdim } 1502239462Sdim 1503263508Sdim if (S.end.isDead()) { 1504239462Sdim // Segment ends on the dead slot. 1505239462Sdim // That means there must be a dead def. 1506263508Sdim if (!SlotIndex::isSameInstr(S.start, S.end)) { 1507263508Sdim report("Live segment ending at dead slot spans instructions", EndMBB, LR); 1508263508Sdim *OS << S << '\n'; 1509239462Sdim } 1510239462Sdim } 1511239462Sdim 1512239462Sdim // A live segment can only end at an early-clobber slot if it is being 1513239462Sdim // redefined by an early-clobber def. 1514263508Sdim if (S.end.isEarlyClobber()) { 1515263508Sdim if (I+1 == LR.end() || (I+1)->start != S.end) { 1516239462Sdim report("Live segment ending at early clobber slot must be " 1517263508Sdim "redefined by an EC def in the same instruction", EndMBB, LR); 1518263508Sdim *OS << S << '\n'; 1519239462Sdim } 1520239462Sdim } 1521239462Sdim 1522239462Sdim // The following checks only apply to virtual registers. Physreg liveness 1523239462Sdim // is too weird to check. 1524263508Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1525263508Sdim // A live segment can end with either a redefinition, a kill flag on a 1526239462Sdim // use, or a dead flag on a def. 1527239462Sdim bool hasRead = false; 1528239462Sdim for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1529263508Sdim if (!MOI->isReg() || MOI->getReg() != Reg) 1530234353Sdim continue; 1531239462Sdim if (MOI->readsReg()) 1532239462Sdim hasRead = true; 1533239462Sdim } 1534263508Sdim if (!S.end.isDead()) { 1535239462Sdim if (!hasRead) { 1536263508Sdim report("Instruction ending live segment doesn't read the register", MI); 1537263508Sdim *OS << S << " in " << LR << '\n'; 1538234353Sdim } 1539239462Sdim } 1540239462Sdim } 1541234353Sdim 1542239462Sdim // Now check all the basic blocks in this live segment. 1543239462Sdim MachineFunction::const_iterator MFI = MBB; 1544263508Sdim // Is this live segment the beginning of a non-PHIDef VN? 1545263508Sdim if (S.start == VNI->def && !VNI->isPHIDef()) { 1546239462Sdim // Not live-in to any blocks. 1547239462Sdim if (MBB == EndMBB) 1548239462Sdim return; 1549239462Sdim // Skip this block. 1550239462Sdim ++MFI; 1551239462Sdim } 1552239462Sdim for (;;) { 1553263508Sdim assert(LiveInts->isLiveInToMBB(LR, MFI)); 1554239462Sdim // We don't know how to track physregs into a landing pad. 1555263508Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg) && 1556239462Sdim MFI->isLandingPad()) { 1557239462Sdim if (&*MFI == EndMBB) 1558239462Sdim break; 1559239462Sdim ++MFI; 1560239462Sdim continue; 1561239462Sdim } 1562234353Sdim 1563239462Sdim // Is VNI a PHI-def in the current block? 1564239462Sdim bool IsPHI = VNI->isPHIDef() && 1565239462Sdim VNI->def == LiveInts->getMBBStartIdx(MFI); 1566234353Sdim 1567239462Sdim // Check that VNI is live-out of all predecessors. 1568239462Sdim for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(), 1569239462Sdim PE = MFI->pred_end(); PI != PE; ++PI) { 1570239462Sdim SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI); 1571263508Sdim const VNInfo *PVNI = LR.getVNInfoBefore(PEnd); 1572239462Sdim 1573239462Sdim // All predecessors must have a live-out value. 1574239462Sdim if (!PVNI) { 1575263508Sdim report("Register not marked live out of predecessor", *PI, LR); 1576239462Sdim *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber() 1577239462Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before " 1578239462Sdim << PEnd << '\n'; 1579239462Sdim continue; 1580218893Sdim } 1581218893Sdim 1582239462Sdim // Only PHI-defs can take different predecessor values. 1583239462Sdim if (!IsPHI && PVNI != VNI) { 1584263508Sdim report("Different value live out of predecessor", *PI, LR); 1585239462Sdim *OS << "Valno #" << PVNI->id << " live out of BB#" 1586239462Sdim << (*PI)->getNumber() << '@' << PEnd 1587239462Sdim << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber() 1588239462Sdim << '@' << LiveInts->getMBBStartIdx(MFI) << '\n'; 1589218893Sdim } 1590239462Sdim } 1591239462Sdim if (&*MFI == EndMBB) 1592239462Sdim break; 1593239462Sdim ++MFI; 1594239462Sdim } 1595239462Sdim} 1596218893Sdim 1597263508Sdimvoid MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg) { 1598263508Sdim for (LiveRange::const_vni_iterator I = LR.vni_begin(), E = LR.vni_end(); 1599263508Sdim I != E; ++I) 1600263508Sdim verifyLiveRangeValue(LR, *I, Reg); 1601263508Sdim 1602263508Sdim for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I) 1603263508Sdim verifyLiveRangeSegment(LR, I, Reg); 1604263508Sdim} 1605263508Sdim 1606239462Sdimvoid MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { 1607263508Sdim verifyLiveRange(LI, LI.reg); 1608218893Sdim 1609239462Sdim // Check the LI only has one connected component. 1610239462Sdim if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1611239462Sdim ConnectedVNInfoEqClasses ConEQ(*LiveInts); 1612239462Sdim unsigned NumComp = ConEQ.Classify(&LI); 1613239462Sdim if (NumComp > 1) { 1614239462Sdim report("Multiple connected components in live interval", MF, LI); 1615239462Sdim for (unsigned comp = 0; comp != NumComp; ++comp) { 1616239462Sdim *OS << comp << ": valnos"; 1617239462Sdim for (LiveInterval::const_vni_iterator I = LI.vni_begin(), 1618239462Sdim E = LI.vni_end(); I!=E; ++I) 1619239462Sdim if (comp == ConEQ.getEqClass(*I)) 1620239462Sdim *OS << ' ' << (*I)->id; 1621239462Sdim *OS << '\n'; 1622218893Sdim } 1623212904Sdim } 1624212904Sdim } 1625212904Sdim} 1626263508Sdim 1627263508Sdimnamespace { 1628263508Sdim // FrameSetup and FrameDestroy can have zero adjustment, so using a single 1629263508Sdim // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the 1630263508Sdim // value is zero. 1631263508Sdim // We use a bool plus an integer to capture the stack state. 1632263508Sdim struct StackStateOfBB { 1633263508Sdim StackStateOfBB() : EntryValue(0), ExitValue(0), EntryIsSetup(false), 1634263508Sdim ExitIsSetup(false) { } 1635263508Sdim StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) : 1636263508Sdim EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup), 1637263508Sdim ExitIsSetup(ExitSetup) { } 1638263508Sdim // Can be negative, which means we are setting up a frame. 1639263508Sdim int EntryValue; 1640263508Sdim int ExitValue; 1641263508Sdim bool EntryIsSetup; 1642263508Sdim bool ExitIsSetup; 1643263508Sdim }; 1644263508Sdim} 1645263508Sdim 1646263508Sdim/// Make sure on every path through the CFG, a FrameSetup <n> is always followed 1647263508Sdim/// by a FrameDestroy <n>, stack adjustments are identical on all 1648263508Sdim/// CFG edges to a merge point, and frame is destroyed at end of a return block. 1649263508Sdimvoid MachineVerifier::verifyStackFrame() { 1650263508Sdim int FrameSetupOpcode = TII->getCallFrameSetupOpcode(); 1651263508Sdim int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode(); 1652263508Sdim 1653263508Sdim SmallVector<StackStateOfBB, 8> SPState; 1654263508Sdim SPState.resize(MF->getNumBlockIDs()); 1655263508Sdim SmallPtrSet<const MachineBasicBlock*, 8> Reachable; 1656263508Sdim 1657263508Sdim // Visit the MBBs in DFS order. 1658263508Sdim for (df_ext_iterator<const MachineFunction*, 1659263508Sdim SmallPtrSet<const MachineBasicBlock*, 8> > 1660263508Sdim DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable); 1661263508Sdim DFI != DFE; ++DFI) { 1662263508Sdim const MachineBasicBlock *MBB = *DFI; 1663263508Sdim 1664263508Sdim StackStateOfBB BBState; 1665263508Sdim // Check the exit state of the DFS stack predecessor. 1666263508Sdim if (DFI.getPathLength() >= 2) { 1667263508Sdim const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); 1668263508Sdim assert(Reachable.count(StackPred) && 1669263508Sdim "DFS stack predecessor is already visited.\n"); 1670263508Sdim BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue; 1671263508Sdim BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup; 1672263508Sdim BBState.ExitValue = BBState.EntryValue; 1673263508Sdim BBState.ExitIsSetup = BBState.EntryIsSetup; 1674263508Sdim } 1675263508Sdim 1676263508Sdim // Update stack state by checking contents of MBB. 1677263508Sdim for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 1678263508Sdim I != E; ++I) { 1679263508Sdim if (I->getOpcode() == FrameSetupOpcode) { 1680263508Sdim // The first operand of a FrameOpcode should be i32. 1681263508Sdim int Size = I->getOperand(0).getImm(); 1682263508Sdim assert(Size >= 0 && 1683263508Sdim "Value should be non-negative in FrameSetup and FrameDestroy.\n"); 1684263508Sdim 1685263508Sdim if (BBState.ExitIsSetup) 1686263508Sdim report("FrameSetup is after another FrameSetup", I); 1687263508Sdim BBState.ExitValue -= Size; 1688263508Sdim BBState.ExitIsSetup = true; 1689263508Sdim } 1690263508Sdim 1691263508Sdim if (I->getOpcode() == FrameDestroyOpcode) { 1692263508Sdim // The first operand of a FrameOpcode should be i32. 1693263508Sdim int Size = I->getOperand(0).getImm(); 1694263508Sdim assert(Size >= 0 && 1695263508Sdim "Value should be non-negative in FrameSetup and FrameDestroy.\n"); 1696263508Sdim 1697263508Sdim if (!BBState.ExitIsSetup) 1698263508Sdim report("FrameDestroy is not after a FrameSetup", I); 1699263508Sdim int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue : 1700263508Sdim BBState.ExitValue; 1701263508Sdim if (BBState.ExitIsSetup && AbsSPAdj != Size) { 1702263508Sdim report("FrameDestroy <n> is after FrameSetup <m>", I); 1703263508Sdim *OS << "FrameDestroy <" << Size << "> is after FrameSetup <" 1704263508Sdim << AbsSPAdj << ">.\n"; 1705263508Sdim } 1706263508Sdim BBState.ExitValue += Size; 1707263508Sdim BBState.ExitIsSetup = false; 1708263508Sdim } 1709263508Sdim } 1710263508Sdim SPState[MBB->getNumber()] = BBState; 1711263508Sdim 1712263508Sdim // Make sure the exit state of any predecessor is consistent with the entry 1713263508Sdim // state. 1714263508Sdim for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 1715263508Sdim E = MBB->pred_end(); I != E; ++I) { 1716263508Sdim if (Reachable.count(*I) && 1717263508Sdim (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue || 1718263508Sdim SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) { 1719263508Sdim report("The exit stack state of a predecessor is inconsistent.", MBB); 1720263508Sdim *OS << "Predecessor BB#" << (*I)->getNumber() << " has exit state (" 1721263508Sdim << SPState[(*I)->getNumber()].ExitValue << ", " 1722263508Sdim << SPState[(*I)->getNumber()].ExitIsSetup 1723263508Sdim << "), while BB#" << MBB->getNumber() << " has entry state (" 1724263508Sdim << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n"; 1725263508Sdim } 1726263508Sdim } 1727263508Sdim 1728263508Sdim // Make sure the entry state of any successor is consistent with the exit 1729263508Sdim // state. 1730263508Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 1731263508Sdim E = MBB->succ_end(); I != E; ++I) { 1732263508Sdim if (Reachable.count(*I) && 1733263508Sdim (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue || 1734263508Sdim SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) { 1735263508Sdim report("The entry stack state of a successor is inconsistent.", MBB); 1736263508Sdim *OS << "Successor BB#" << (*I)->getNumber() << " has entry state (" 1737263508Sdim << SPState[(*I)->getNumber()].EntryValue << ", " 1738263508Sdim << SPState[(*I)->getNumber()].EntryIsSetup 1739263508Sdim << "), while BB#" << MBB->getNumber() << " has exit state (" 1740263508Sdim << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n"; 1741263508Sdim } 1742263508Sdim } 1743263508Sdim 1744263508Sdim // Make sure a basic block with return ends with zero stack adjustment. 1745263508Sdim if (!MBB->empty() && MBB->back().isReturn()) { 1746263508Sdim if (BBState.ExitIsSetup) 1747263508Sdim report("A return block ends with a FrameSetup.", MBB); 1748263508Sdim if (BBState.ExitValue) 1749263508Sdim report("A return block ends with a nonzero stack adjustment.", MBB); 1750263508Sdim } 1751263508Sdim } 1752263508Sdim} 1753