MachineVerifier.cpp revision 193323
1193323Sed//===-- MachineVerifier.cpp - Machine Code Verifier -------------*- C++ -*-===// 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 26193323Sed#include "llvm/ADT/DenseSet.h" 27193323Sed#include "llvm/ADT/SetOperations.h" 28193323Sed#include "llvm/ADT/SmallVector.h" 29193323Sed#include "llvm/Function.h" 30193323Sed#include "llvm/CodeGen/LiveVariables.h" 31193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 32193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 33193323Sed#include "llvm/CodeGen/Passes.h" 34193323Sed#include "llvm/Target/TargetMachine.h" 35193323Sed#include "llvm/Target/TargetRegisterInfo.h" 36193323Sed#include "llvm/Target/TargetInstrInfo.h" 37193323Sed#include "llvm/Support/Compiler.h" 38193323Sed#include "llvm/Support/Debug.h" 39193323Sed#include <fstream> 40193323Sed 41193323Sedusing namespace llvm; 42193323Sed 43193323Sednamespace { 44193323Sed struct VISIBILITY_HIDDEN MachineVerifier : public MachineFunctionPass { 45193323Sed static char ID; // Pass ID, replacement for typeid 46193323Sed 47193323Sed MachineVerifier(bool allowDoubleDefs = false) : 48193323Sed MachineFunctionPass(&ID), 49193323Sed allowVirtDoubleDefs(allowDoubleDefs), 50193323Sed allowPhysDoubleDefs(allowDoubleDefs), 51193323Sed OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) 52193323Sed {} 53193323Sed 54193323Sed void getAnalysisUsage(AnalysisUsage &AU) const { 55193323Sed AU.setPreservesAll(); 56193323Sed } 57193323Sed 58193323Sed bool runOnMachineFunction(MachineFunction &MF); 59193323Sed 60193323Sed const bool allowVirtDoubleDefs; 61193323Sed const bool allowPhysDoubleDefs; 62193323Sed 63193323Sed const char *const OutFileName; 64193323Sed std::ostream *OS; 65193323Sed const MachineFunction *MF; 66193323Sed const TargetMachine *TM; 67193323Sed const TargetRegisterInfo *TRI; 68193323Sed const MachineRegisterInfo *MRI; 69193323Sed 70193323Sed unsigned foundErrors; 71193323Sed 72193323Sed typedef SmallVector<unsigned, 16> RegVector; 73193323Sed typedef DenseSet<unsigned> RegSet; 74193323Sed typedef DenseMap<unsigned, const MachineInstr*> RegMap; 75193323Sed 76193323Sed BitVector regsReserved; 77193323Sed RegSet regsLive; 78193323Sed RegVector regsDefined, regsImpDefined, regsDead, regsKilled; 79193323Sed 80193323Sed // Add Reg and any sub-registers to RV 81193323Sed void addRegWithSubRegs(RegVector &RV, unsigned Reg) { 82193323Sed RV.push_back(Reg); 83193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) 84193323Sed for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 85193323Sed RV.push_back(*R); 86193323Sed } 87193323Sed 88193323Sed // Does RS contain any super-registers of Reg? 89193323Sed bool anySuperRegisters(const RegSet &RS, unsigned Reg) { 90193323Sed for (const unsigned *R = TRI->getSuperRegisters(Reg); *R; R++) 91193323Sed if (RS.count(*R)) 92193323Sed return true; 93193323Sed return false; 94193323Sed } 95193323Sed 96193323Sed struct BBInfo { 97193323Sed // Is this MBB reachable from the MF entry point? 98193323Sed bool reachable; 99193323Sed 100193323Sed // Vregs that must be live in because they are used without being 101193323Sed // defined. Map value is the user. 102193323Sed RegMap vregsLiveIn; 103193323Sed 104193323Sed // Vregs that must be dead in because they are defined without being 105193323Sed // killed first. Map value is the defining instruction. 106193323Sed RegMap vregsDeadIn; 107193323Sed 108193323Sed // Regs killed in MBB. They may be defined again, and will then be in both 109193323Sed // regsKilled and regsLiveOut. 110193323Sed RegSet regsKilled; 111193323Sed 112193323Sed // Regs defined in MBB and live out. Note that vregs passing through may 113193323Sed // be live out without being mentioned here. 114193323Sed RegSet regsLiveOut; 115193323Sed 116193323Sed // Vregs that pass through MBB untouched. This set is disjoint from 117193323Sed // regsKilled and regsLiveOut. 118193323Sed RegSet vregsPassed; 119193323Sed 120193323Sed BBInfo() : reachable(false) {} 121193323Sed 122193323Sed // Add register to vregsPassed if it belongs there. Return true if 123193323Sed // anything changed. 124193323Sed bool addPassed(unsigned Reg) { 125193323Sed if (!TargetRegisterInfo::isVirtualRegister(Reg)) 126193323Sed return false; 127193323Sed if (regsKilled.count(Reg) || regsLiveOut.count(Reg)) 128193323Sed return false; 129193323Sed return vregsPassed.insert(Reg).second; 130193323Sed } 131193323Sed 132193323Sed // Same for a full set. 133193323Sed bool addPassed(const RegSet &RS) { 134193323Sed bool changed = false; 135193323Sed for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 136193323Sed if (addPassed(*I)) 137193323Sed changed = true; 138193323Sed return changed; 139193323Sed } 140193323Sed 141193323Sed // Live-out registers are either in regsLiveOut or vregsPassed. 142193323Sed bool isLiveOut(unsigned Reg) const { 143193323Sed return regsLiveOut.count(Reg) || vregsPassed.count(Reg); 144193323Sed } 145193323Sed }; 146193323Sed 147193323Sed // Extra register info per MBB. 148193323Sed DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap; 149193323Sed 150193323Sed bool isReserved(unsigned Reg) { 151193323Sed return Reg < regsReserved.size() && regsReserved[Reg]; 152193323Sed } 153193323Sed 154193323Sed void visitMachineFunctionBefore(); 155193323Sed void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); 156193323Sed void visitMachineInstrBefore(const MachineInstr *MI); 157193323Sed void visitMachineOperand(const MachineOperand *MO, unsigned MONum); 158193323Sed void visitMachineInstrAfter(const MachineInstr *MI); 159193323Sed void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB); 160193323Sed void visitMachineFunctionAfter(); 161193323Sed 162193323Sed void report(const char *msg, const MachineFunction *MF); 163193323Sed void report(const char *msg, const MachineBasicBlock *MBB); 164193323Sed void report(const char *msg, const MachineInstr *MI); 165193323Sed void report(const char *msg, const MachineOperand *MO, unsigned MONum); 166193323Sed 167193323Sed void markReachable(const MachineBasicBlock *MBB); 168193323Sed void calcMaxRegsPassed(); 169193323Sed void calcMinRegsPassed(); 170193323Sed void checkPHIOps(const MachineBasicBlock *MBB); 171193323Sed }; 172193323Sed} 173193323Sed 174193323Sedchar MachineVerifier::ID = 0; 175193323Sedstatic RegisterPass<MachineVerifier> 176193323SedMachineVer("machineverifier", "Verify generated machine code"); 177193323Sedstatic const PassInfo *const MachineVerifyID = &MachineVer; 178193323Sed 179193323SedFunctionPass * 180193323Sedllvm::createMachineVerifierPass(bool allowPhysDoubleDefs) 181193323Sed{ 182193323Sed return new MachineVerifier(allowPhysDoubleDefs); 183193323Sed} 184193323Sed 185193323Sedbool 186193323SedMachineVerifier::runOnMachineFunction(MachineFunction &MF) 187193323Sed{ 188193323Sed std::ofstream OutFile; 189193323Sed if (OutFileName) { 190193323Sed OutFile.open(OutFileName, std::ios::out | std::ios::app); 191193323Sed OS = &OutFile; 192193323Sed } else { 193193323Sed OS = cerr.stream(); 194193323Sed } 195193323Sed 196193323Sed foundErrors = 0; 197193323Sed 198193323Sed this->MF = &MF; 199193323Sed TM = &MF.getTarget(); 200193323Sed TRI = TM->getRegisterInfo(); 201193323Sed MRI = &MF.getRegInfo(); 202193323Sed 203193323Sed visitMachineFunctionBefore(); 204193323Sed for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 205193323Sed MFI!=MFE; ++MFI) { 206193323Sed visitMachineBasicBlockBefore(MFI); 207193323Sed for (MachineBasicBlock::const_iterator MBBI = MFI->begin(), 208193323Sed MBBE = MFI->end(); MBBI != MBBE; ++MBBI) { 209193323Sed visitMachineInstrBefore(MBBI); 210193323Sed for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) 211193323Sed visitMachineOperand(&MBBI->getOperand(I), I); 212193323Sed visitMachineInstrAfter(MBBI); 213193323Sed } 214193323Sed visitMachineBasicBlockAfter(MFI); 215193323Sed } 216193323Sed visitMachineFunctionAfter(); 217193323Sed 218193323Sed if (OutFileName) 219193323Sed OutFile.close(); 220193323Sed 221193323Sed if (foundErrors) { 222193323Sed cerr << "\nStopping with " << foundErrors << " machine code errors.\n"; 223193323Sed exit(1); 224193323Sed } 225193323Sed 226193323Sed return false; // no changes 227193323Sed} 228193323Sed 229193323Sedvoid 230193323SedMachineVerifier::report(const char *msg, const MachineFunction *MF) 231193323Sed{ 232193323Sed assert(MF); 233193323Sed *OS << "\n"; 234193323Sed if (!foundErrors++) 235193323Sed MF->print(OS); 236193323Sed *OS << "*** Bad machine code: " << msg << " ***\n" 237193323Sed << "- function: " << MF->getFunction()->getName() << "\n"; 238193323Sed} 239193323Sed 240193323Sedvoid 241193323SedMachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) 242193323Sed{ 243193323Sed assert(MBB); 244193323Sed report(msg, MBB->getParent()); 245193323Sed *OS << "- basic block: " << MBB->getBasicBlock()->getName() 246193323Sed << " " << (void*)MBB 247193323Sed << " (#" << MBB->getNumber() << ")\n"; 248193323Sed} 249193323Sed 250193323Sedvoid 251193323SedMachineVerifier::report(const char *msg, const MachineInstr *MI) 252193323Sed{ 253193323Sed assert(MI); 254193323Sed report(msg, MI->getParent()); 255193323Sed *OS << "- instruction: "; 256193323Sed MI->print(OS, TM); 257193323Sed} 258193323Sed 259193323Sedvoid 260193323SedMachineVerifier::report(const char *msg, 261193323Sed const MachineOperand *MO, unsigned MONum) 262193323Sed{ 263193323Sed assert(MO); 264193323Sed report(msg, MO->getParent()); 265193323Sed *OS << "- operand " << MONum << ": "; 266193323Sed MO->print(*OS, TM); 267193323Sed *OS << "\n"; 268193323Sed} 269193323Sed 270193323Sedvoid 271193323SedMachineVerifier::markReachable(const MachineBasicBlock *MBB) 272193323Sed{ 273193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 274193323Sed if (!MInfo.reachable) { 275193323Sed MInfo.reachable = true; 276193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 277193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) 278193323Sed markReachable(*SuI); 279193323Sed } 280193323Sed} 281193323Sed 282193323Sedvoid 283193323SedMachineVerifier::visitMachineFunctionBefore() 284193323Sed{ 285193323Sed regsReserved = TRI->getReservedRegs(*MF); 286193323Sed markReachable(&MF->front()); 287193323Sed} 288193323Sed 289193323Sedvoid 290193323SedMachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) 291193323Sed{ 292193323Sed regsLive.clear(); 293193323Sed for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 294193323Sed E = MBB->livein_end(); I != E; ++I) { 295193323Sed if (!TargetRegisterInfo::isPhysicalRegister(*I)) { 296193323Sed report("MBB live-in list contains non-physical register", MBB); 297193323Sed continue; 298193323Sed } 299193323Sed regsLive.insert(*I); 300193323Sed for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++) 301193323Sed regsLive.insert(*R); 302193323Sed } 303193323Sed regsKilled.clear(); 304193323Sed regsDefined.clear(); 305193323Sed regsImpDefined.clear(); 306193323Sed} 307193323Sed 308193323Sedvoid 309193323SedMachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) 310193323Sed{ 311193323Sed const TargetInstrDesc &TI = MI->getDesc(); 312193323Sed if (MI->getNumExplicitOperands() < TI.getNumOperands()) { 313193323Sed report("Too few operands", MI); 314193323Sed *OS << TI.getNumOperands() << " operands expected, but " 315193323Sed << MI->getNumExplicitOperands() << " given.\n"; 316193323Sed } 317193323Sed if (!TI.isVariadic()) { 318193323Sed if (MI->getNumExplicitOperands() > TI.getNumOperands()) { 319193323Sed report("Too many operands", MI); 320193323Sed *OS << TI.getNumOperands() << " operands expected, but " 321193323Sed << MI->getNumExplicitOperands() << " given.\n"; 322193323Sed } 323193323Sed } 324193323Sed} 325193323Sed 326193323Sedvoid 327193323SedMachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) 328193323Sed{ 329193323Sed const MachineInstr *MI = MO->getParent(); 330193323Sed const TargetInstrDesc &TI = MI->getDesc(); 331193323Sed 332193323Sed // The first TI.NumDefs operands must be explicit register defines 333193323Sed if (MONum < TI.getNumDefs()) { 334193323Sed if (!MO->isReg()) 335193323Sed report("Explicit definition must be a register", MO, MONum); 336193323Sed else if (!MO->isDef()) 337193323Sed report("Explicit definition marked as use", MO, MONum); 338193323Sed else if (MO->isImplicit()) 339193323Sed report("Explicit definition marked as implicit", MO, MONum); 340193323Sed } 341193323Sed 342193323Sed switch (MO->getType()) { 343193323Sed case MachineOperand::MO_Register: { 344193323Sed const unsigned Reg = MO->getReg(); 345193323Sed if (!Reg) 346193323Sed return; 347193323Sed 348193323Sed // Check Live Variables. 349193323Sed if (MO->isUse()) { 350193323Sed if (MO->isKill()) { 351193323Sed addRegWithSubRegs(regsKilled, Reg); 352193323Sed } else { 353193323Sed // TwoAddress instr modyfying a reg is treated as kill+def. 354193323Sed unsigned defIdx; 355193323Sed if (MI->isRegTiedToDefOperand(MONum, &defIdx) && 356193323Sed MI->getOperand(defIdx).getReg() == Reg) 357193323Sed addRegWithSubRegs(regsKilled, Reg); 358193323Sed } 359193323Sed // Explicit use of a dead register. 360193323Sed if (!MO->isImplicit() && !regsLive.count(Reg)) { 361193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 362193323Sed // Reserved registers may be used even when 'dead'. 363193323Sed if (!isReserved(Reg)) 364193323Sed report("Using an undefined physical register", MO, MONum); 365193323Sed } else { 366193323Sed BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 367193323Sed // We don't know which virtual registers are live in, so only complain 368193323Sed // if vreg was killed in this MBB. Otherwise keep track of vregs that 369193323Sed // must be live in. PHI instructions are handled separately. 370193323Sed if (MInfo.regsKilled.count(Reg)) 371193323Sed report("Using a killed virtual register", MO, MONum); 372193323Sed else if (MI->getOpcode() != TargetInstrInfo::PHI) 373193323Sed MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 374193323Sed } 375193323Sed } 376193323Sed } else { 377193323Sed // Register defined. 378193323Sed // TODO: verify that earlyclobber ops are not used. 379193323Sed if (MO->isImplicit()) 380193323Sed addRegWithSubRegs(regsImpDefined, Reg); 381193323Sed else 382193323Sed addRegWithSubRegs(regsDefined, Reg); 383193323Sed 384193323Sed if (MO->isDead()) 385193323Sed addRegWithSubRegs(regsDead, Reg); 386193323Sed } 387193323Sed 388193323Sed // Check register classes. 389193323Sed if (MONum < TI.getNumOperands() && !MO->isImplicit()) { 390193323Sed const TargetOperandInfo &TOI = TI.OpInfo[MONum]; 391193323Sed unsigned SubIdx = MO->getSubReg(); 392193323Sed 393193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 394193323Sed unsigned sr = Reg; 395193323Sed if (SubIdx) { 396193323Sed unsigned s = TRI->getSubReg(Reg, SubIdx); 397193323Sed if (!s) { 398193323Sed report("Invalid subregister index for physical register", 399193323Sed MO, MONum); 400193323Sed return; 401193323Sed } 402193323Sed sr = s; 403193323Sed } 404193323Sed if (TOI.RegClass) { 405193323Sed const TargetRegisterClass *DRC = TRI->getRegClass(TOI.RegClass); 406193323Sed if (!DRC->contains(sr)) { 407193323Sed report("Illegal physical register for instruction", MO, MONum); 408193323Sed *OS << TRI->getName(sr) << " is not a " 409193323Sed << DRC->getName() << " register.\n"; 410193323Sed } 411193323Sed } 412193323Sed } else { 413193323Sed // Virtual register. 414193323Sed const TargetRegisterClass *RC = MRI->getRegClass(Reg); 415193323Sed if (SubIdx) { 416193323Sed if (RC->subregclasses_begin()+SubIdx >= RC->subregclasses_end()) { 417193323Sed report("Invalid subregister index for virtual register", MO, MONum); 418193323Sed return; 419193323Sed } 420193323Sed RC = *(RC->subregclasses_begin()+SubIdx); 421193323Sed } 422193323Sed if (TOI.RegClass) { 423193323Sed const TargetRegisterClass *DRC = TRI->getRegClass(TOI.RegClass); 424193323Sed if (RC != DRC && !RC->hasSuperClass(DRC)) { 425193323Sed report("Illegal virtual register for instruction", MO, MONum); 426193323Sed *OS << "Expected a " << DRC->getName() << " register, but got a " 427193323Sed << RC->getName() << " register\n"; 428193323Sed } 429193323Sed } 430193323Sed } 431193323Sed } 432193323Sed break; 433193323Sed } 434193323Sed // Can PHI instrs refer to MBBs not in the CFG? X86 and ARM do. 435193323Sed // case MachineOperand::MO_MachineBasicBlock: 436193323Sed // if (MI->getOpcode() == TargetInstrInfo::PHI) { 437193323Sed // if (!MO->getMBB()->isSuccessor(MI->getParent())) 438193323Sed // report("PHI operand is not in the CFG", MO, MONum); 439193323Sed // } 440193323Sed // break; 441193323Sed default: 442193323Sed break; 443193323Sed } 444193323Sed} 445193323Sed 446193323Sedvoid 447193323SedMachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) 448193323Sed{ 449193323Sed BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 450193323Sed set_union(MInfo.regsKilled, regsKilled); 451193323Sed set_subtract(regsLive, regsKilled); 452193323Sed regsKilled.clear(); 453193323Sed 454193323Sed for (RegVector::const_iterator I = regsDefined.begin(), 455193323Sed E = regsDefined.end(); I != E; ++I) { 456193323Sed if (regsLive.count(*I)) { 457193323Sed if (TargetRegisterInfo::isPhysicalRegister(*I)) { 458193323Sed // We allow double defines to physical registers with live 459193323Sed // super-registers. 460193323Sed if (!allowPhysDoubleDefs && !isReserved(*I) && 461193323Sed !anySuperRegisters(regsLive, *I)) { 462193323Sed report("Redefining a live physical register", MI); 463193323Sed *OS << "Register " << TRI->getName(*I) 464193323Sed << " was defined but already live.\n"; 465193323Sed } 466193323Sed } else { 467193323Sed if (!allowVirtDoubleDefs) { 468193323Sed report("Redefining a live virtual register", MI); 469193323Sed *OS << "Virtual register %reg" << *I 470193323Sed << " was defined but already live.\n"; 471193323Sed } 472193323Sed } 473193323Sed } else if (TargetRegisterInfo::isVirtualRegister(*I) && 474193323Sed !MInfo.regsKilled.count(*I)) { 475193323Sed // Virtual register defined without being killed first must be dead on 476193323Sed // entry. 477193323Sed MInfo.vregsDeadIn.insert(std::make_pair(*I, MI)); 478193323Sed } 479193323Sed } 480193323Sed 481193323Sed set_union(regsLive, regsDefined); regsDefined.clear(); 482193323Sed set_union(regsLive, regsImpDefined); regsImpDefined.clear(); 483193323Sed set_subtract(regsLive, regsDead); regsDead.clear(); 484193323Sed} 485193323Sed 486193323Sedvoid 487193323SedMachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) 488193323Sed{ 489193323Sed MBBInfoMap[MBB].regsLiveOut = regsLive; 490193323Sed regsLive.clear(); 491193323Sed} 492193323Sed 493193323Sed// Calculate the largest possible vregsPassed sets. These are the registers that 494193323Sed// can pass through an MBB live, but may not be live every time. It is assumed 495193323Sed// that all vregsPassed sets are empty before the call. 496193323Sedvoid 497193323SedMachineVerifier::calcMaxRegsPassed() 498193323Sed{ 499193323Sed // First push live-out regs to successors' vregsPassed. Remember the MBBs that 500193323Sed // have any vregsPassed. 501193323Sed DenseSet<const MachineBasicBlock*> todo; 502193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 503193323Sed MFI != MFE; ++MFI) { 504193323Sed const MachineBasicBlock &MBB(*MFI); 505193323Sed BBInfo &MInfo = MBBInfoMap[&MBB]; 506193323Sed if (!MInfo.reachable) 507193323Sed continue; 508193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 509193323Sed SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 510193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 511193323Sed if (SInfo.addPassed(MInfo.regsLiveOut)) 512193323Sed todo.insert(*SuI); 513193323Sed } 514193323Sed } 515193323Sed 516193323Sed // Iteratively push vregsPassed to successors. This will converge to the same 517193323Sed // final state regardless of DenseSet iteration order. 518193323Sed while (!todo.empty()) { 519193323Sed const MachineBasicBlock *MBB = *todo.begin(); 520193323Sed todo.erase(MBB); 521193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 522193323Sed for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 523193323Sed SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 524193323Sed if (*SuI == MBB) 525193323Sed continue; 526193323Sed BBInfo &SInfo = MBBInfoMap[*SuI]; 527193323Sed if (SInfo.addPassed(MInfo.vregsPassed)) 528193323Sed todo.insert(*SuI); 529193323Sed } 530193323Sed } 531193323Sed} 532193323Sed 533193323Sed// Calculate the minimum vregsPassed set. These are the registers that always 534193323Sed// pass live through an MBB. The calculation assumes that calcMaxRegsPassed has 535193323Sed// been called earlier. 536193323Sedvoid 537193323SedMachineVerifier::calcMinRegsPassed() 538193323Sed{ 539193323Sed DenseSet<const MachineBasicBlock*> todo; 540193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 541193323Sed MFI != MFE; ++MFI) 542193323Sed todo.insert(MFI); 543193323Sed 544193323Sed while (!todo.empty()) { 545193323Sed const MachineBasicBlock *MBB = *todo.begin(); 546193323Sed todo.erase(MBB); 547193323Sed BBInfo &MInfo = MBBInfoMap[MBB]; 548193323Sed 549193323Sed // Remove entries from vRegsPassed that are not live out from all 550193323Sed // reachable predecessors. 551193323Sed RegSet dead; 552193323Sed for (RegSet::iterator I = MInfo.vregsPassed.begin(), 553193323Sed E = MInfo.vregsPassed.end(); I != E; ++I) { 554193323Sed for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 555193323Sed PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 556193323Sed BBInfo &PrInfo = MBBInfoMap[*PrI]; 557193323Sed if (PrInfo.reachable && !PrInfo.isLiveOut(*I)) { 558193323Sed dead.insert(*I); 559193323Sed break; 560193323Sed } 561193323Sed } 562193323Sed } 563193323Sed // If any regs removed, we need to recheck successors. 564193323Sed if (!dead.empty()) { 565193323Sed set_subtract(MInfo.vregsPassed, dead); 566193323Sed todo.insert(MBB->succ_begin(), MBB->succ_end()); 567193323Sed } 568193323Sed } 569193323Sed} 570193323Sed 571193323Sed// Check PHI instructions at the beginning of MBB. It is assumed that 572193323Sed// calcMinRegsPassed has been run so BBInfo::isLiveOut is valid. 573193323Sedvoid 574193323SedMachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) 575193323Sed{ 576193323Sed for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 577193323Sed BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) { 578193323Sed DenseSet<const MachineBasicBlock*> seen; 579193323Sed 580193323Sed for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 581193323Sed unsigned Reg = BBI->getOperand(i).getReg(); 582193323Sed const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB(); 583193323Sed if (!Pre->isSuccessor(MBB)) 584193323Sed continue; 585193323Sed seen.insert(Pre); 586193323Sed BBInfo &PrInfo = MBBInfoMap[Pre]; 587193323Sed if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 588193323Sed report("PHI operand is not live-out from predecessor", 589193323Sed &BBI->getOperand(i), i); 590193323Sed } 591193323Sed 592193323Sed // Did we see all predecessors? 593193323Sed for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 594193323Sed PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 595193323Sed if (!seen.count(*PrI)) { 596193323Sed report("Missing PHI operand", BBI); 597193323Sed *OS << "MBB #" << (*PrI)->getNumber() 598193323Sed << " is a predecessor according to the CFG.\n"; 599193323Sed } 600193323Sed } 601193323Sed } 602193323Sed} 603193323Sed 604193323Sedvoid 605193323SedMachineVerifier::visitMachineFunctionAfter() 606193323Sed{ 607193323Sed calcMaxRegsPassed(); 608193323Sed 609193323Sed // With the maximal set of vregsPassed we can verify dead-in registers. 610193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 611193323Sed MFI != MFE; ++MFI) { 612193323Sed BBInfo &MInfo = MBBInfoMap[MFI]; 613193323Sed 614193323Sed // Skip unreachable MBBs. 615193323Sed if (!MInfo.reachable) 616193323Sed continue; 617193323Sed 618193323Sed for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(), 619193323Sed PrE = MFI->pred_end(); PrI != PrE; ++PrI) { 620193323Sed BBInfo &PrInfo = MBBInfoMap[*PrI]; 621193323Sed if (!PrInfo.reachable) 622193323Sed continue; 623193323Sed 624193323Sed // Verify physical live-ins. EH landing pads have magic live-ins so we 625193323Sed // ignore them. 626193323Sed if (!MFI->isLandingPad()) { 627193323Sed for (MachineBasicBlock::const_livein_iterator I = MFI->livein_begin(), 628193323Sed E = MFI->livein_end(); I != E; ++I) { 629193323Sed if (TargetRegisterInfo::isPhysicalRegister(*I) && 630193323Sed !isReserved (*I) && !PrInfo.isLiveOut(*I)) { 631193323Sed report("Live-in physical register is not live-out from predecessor", 632193323Sed MFI); 633193323Sed *OS << "Register " << TRI->getName(*I) 634193323Sed << " is not live-out from MBB #" << (*PrI)->getNumber() 635193323Sed << ".\n"; 636193323Sed } 637193323Sed } 638193323Sed } 639193323Sed 640193323Sed 641193323Sed // Verify dead-in virtual registers. 642193323Sed if (!allowVirtDoubleDefs) { 643193323Sed for (RegMap::iterator I = MInfo.vregsDeadIn.begin(), 644193323Sed E = MInfo.vregsDeadIn.end(); I != E; ++I) { 645193323Sed // DeadIn register must be in neither regsLiveOut or vregsPassed of 646193323Sed // any predecessor. 647193323Sed if (PrInfo.isLiveOut(I->first)) { 648193323Sed report("Live-in virtual register redefined", I->second); 649193323Sed *OS << "Register %reg" << I->first 650193323Sed << " was live-out from predecessor MBB #" 651193323Sed << (*PrI)->getNumber() << ".\n"; 652193323Sed } 653193323Sed } 654193323Sed } 655193323Sed } 656193323Sed } 657193323Sed 658193323Sed calcMinRegsPassed(); 659193323Sed 660193323Sed // With the minimal set of vregsPassed we can verify live-in virtual 661193323Sed // registers, including PHI instructions. 662193323Sed for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 663193323Sed MFI != MFE; ++MFI) { 664193323Sed BBInfo &MInfo = MBBInfoMap[MFI]; 665193323Sed 666193323Sed // Skip unreachable MBBs. 667193323Sed if (!MInfo.reachable) 668193323Sed continue; 669193323Sed 670193323Sed checkPHIOps(MFI); 671193323Sed 672193323Sed for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(), 673193323Sed PrE = MFI->pred_end(); PrI != PrE; ++PrI) { 674193323Sed BBInfo &PrInfo = MBBInfoMap[*PrI]; 675193323Sed if (!PrInfo.reachable) 676193323Sed continue; 677193323Sed 678193323Sed for (RegMap::iterator I = MInfo.vregsLiveIn.begin(), 679193323Sed E = MInfo.vregsLiveIn.end(); I != E; ++I) { 680193323Sed if (!PrInfo.isLiveOut(I->first)) { 681193323Sed report("Used virtual register is not live-in", I->second); 682193323Sed *OS << "Register %reg" << I->first 683193323Sed << " is not live-out from predecessor MBB #" 684193323Sed << (*PrI)->getNumber() 685193323Sed << ".\n"; 686193323Sed } 687193323Sed } 688193323Sed } 689193323Sed } 690193323Sed} 691