LLVM API Documentation
00001 //===-- MachineVerifier.cpp - Machine Code Verifier -------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Pass to verify generated machine code. The following is checked: 00011 // 00012 // Operand counts: All explicit operands must be present. 00013 // 00014 // Register classes: All physical and virtual register operands must be 00015 // compatible with the register class required by the instruction descriptor. 00016 // 00017 // Register live intervals: Registers must be defined only once, and must be 00018 // defined before use. 00019 // 00020 // The machine code verifier is enabled from LLVMTargetMachine.cpp with the 00021 // command-line option -verify-machineinstrs, or by defining the environment 00022 // variable LLVM_VERIFY_MACHINEINSTRS to the name of a file that will receive 00023 // the verifier errors. 00024 //===----------------------------------------------------------------------===// 00025 00026 #include "llvm/ADT/DenseSet.h" 00027 #include "llvm/ADT/SetOperations.h" 00028 #include "llvm/ADT/SmallVector.h" 00029 #include "llvm/Function.h" 00030 #include "llvm/CodeGen/LiveVariables.h" 00031 #include "llvm/CodeGen/MachineFunctionPass.h" 00032 #include "llvm/CodeGen/MachineFrameInfo.h" 00033 #include "llvm/CodeGen/MachineRegisterInfo.h" 00034 #include "llvm/CodeGen/Passes.h" 00035 #include "llvm/Target/TargetMachine.h" 00036 #include "llvm/Target/TargetRegisterInfo.h" 00037 #include "llvm/Target/TargetInstrInfo.h" 00038 #include "llvm/Support/Compiler.h" 00039 #include "llvm/Support/Debug.h" 00040 #include "llvm/Support/ErrorHandling.h" 00041 #include "llvm/Support/raw_ostream.h" 00042 #include <fstream> 00043 00044 using namespace llvm; 00045 00046 namespace { 00047 struct VISIBILITY_HIDDEN MachineVerifier : public MachineFunctionPass { 00048 static char ID; // Pass ID, replacement for typeid 00049 00050 MachineVerifier(bool allowDoubleDefs = false) : 00051 MachineFunctionPass(&ID), 00052 allowVirtDoubleDefs(allowDoubleDefs), 00053 allowPhysDoubleDefs(allowDoubleDefs), 00054 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) 00055 {} 00056 00057 void getAnalysisUsage(AnalysisUsage &AU) const { 00058 AU.setPreservesAll(); 00059 MachineFunctionPass::getAnalysisUsage(AU); 00060 } 00061 00062 bool runOnMachineFunction(MachineFunction &MF); 00063 00064 const bool allowVirtDoubleDefs; 00065 const bool allowPhysDoubleDefs; 00066 00067 const char *const OutFileName; 00068 std::ostream *OS; 00069 const MachineFunction *MF; 00070 const TargetMachine *TM; 00071 const TargetRegisterInfo *TRI; 00072 const MachineRegisterInfo *MRI; 00073 00074 unsigned foundErrors; 00075 00076 typedef SmallVector<unsigned, 16> RegVector; 00077 typedef DenseSet<unsigned> RegSet; 00078 typedef DenseMap<unsigned, const MachineInstr*> RegMap; 00079 00080 BitVector regsReserved; 00081 RegSet regsLive; 00082 RegVector regsDefined, regsDead, regsKilled; 00083 RegSet regsLiveInButUnused; 00084 00085 // Add Reg and any sub-registers to RV 00086 void addRegWithSubRegs(RegVector &RV, unsigned Reg) { 00087 RV.push_back(Reg); 00088 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 00089 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 00090 RV.push_back(*R); 00091 } 00092 00093 struct BBInfo { 00094 // Is this MBB reachable from the MF entry point? 00095 bool reachable; 00096 00097 // Vregs that must be live in because they are used without being 00098 // defined. Map value is the user. 00099 RegMap vregsLiveIn; 00100 00101 // Vregs that must be dead in because they are defined without being 00102 // killed first. Map value is the defining instruction. 00103 RegMap vregsDeadIn; 00104 00105 // Regs killed in MBB. They may be defined again, and will then be in both 00106 // regsKilled and regsLiveOut. 00107 RegSet regsKilled; 00108 00109 // Regs defined in MBB and live out. Note that vregs passing through may 00110 // be live out without being mentioned here. 00111 RegSet regsLiveOut; 00112 00113 // Vregs that pass through MBB untouched. This set is disjoint from 00114 // regsKilled and regsLiveOut. 00115 RegSet vregsPassed; 00116 00117 BBInfo() : reachable(false) {} 00118 00119 // Add register to vregsPassed if it belongs there. Return true if 00120 // anything changed. 00121 bool addPassed(unsigned Reg) { 00122 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 00123 return false; 00124 if (regsKilled.count(Reg) || regsLiveOut.count(Reg)) 00125 return false; 00126 return vregsPassed.insert(Reg).second; 00127 } 00128 00129 // Same for a full set. 00130 bool addPassed(const RegSet &RS) { 00131 bool changed = false; 00132 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 00133 if (addPassed(*I)) 00134 changed = true; 00135 return changed; 00136 } 00137 00138 // Live-out registers are either in regsLiveOut or vregsPassed. 00139 bool isLiveOut(unsigned Reg) const { 00140 return regsLiveOut.count(Reg) || vregsPassed.count(Reg); 00141 } 00142 }; 00143 00144 // Extra register info per MBB. 00145 DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap; 00146 00147 bool isReserved(unsigned Reg) { 00148 return Reg < regsReserved.size() && regsReserved.test(Reg); 00149 } 00150 00151 void visitMachineFunctionBefore(); 00152 void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); 00153 void visitMachineInstrBefore(const MachineInstr *MI); 00154 void visitMachineOperand(const MachineOperand *MO, unsigned MONum); 00155 void visitMachineInstrAfter(const MachineInstr *MI); 00156 void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB); 00157 void visitMachineFunctionAfter(); 00158 00159 void report(const char *msg, const MachineFunction *MF); 00160 void report(const char *msg, const MachineBasicBlock *MBB); 00161 void report(const char *msg, const MachineInstr *MI); 00162 void report(const char *msg, const MachineOperand *MO, unsigned MONum); 00163 00164 void markReachable(const MachineBasicBlock *MBB); 00165 void calcMaxRegsPassed(); 00166 void calcMinRegsPassed(); 00167 void checkPHIOps(const MachineBasicBlock *MBB); 00168 }; 00169 } 00170 00171 char MachineVerifier::ID = 0; 00172 static RegisterPass<MachineVerifier> 00173 MachineVer("machineverifier", "Verify generated machine code"); 00174 static const PassInfo *const MachineVerifyID = &MachineVer; 00175 00176 FunctionPass * 00177 llvm::createMachineVerifierPass(bool allowPhysDoubleDefs) 00178 { 00179 return new MachineVerifier(allowPhysDoubleDefs); 00180 } 00181 00182 bool 00183 MachineVerifier::runOnMachineFunction(MachineFunction &MF) 00184 { 00185 std::ofstream OutFile; 00186 if (OutFileName) { 00187 OutFile.open(OutFileName, std::ios::out | std::ios::app); 00188 OS = &OutFile; 00189 } else { 00190 OS = cerr.stream(); 00191 } 00192 00193 foundErrors = 0; 00194 00195 this->MF = &MF; 00196 TM = &MF.getTarget(); 00197 TRI = TM->getRegisterInfo(); 00198 MRI = &MF.getRegInfo(); 00199 00200 visitMachineFunctionBefore(); 00201 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 00202 MFI!=MFE; ++MFI) { 00203 visitMachineBasicBlockBefore(MFI); 00204 for (MachineBasicBlock::const_iterator MBBI = MFI->begin(), 00205 MBBE = MFI->end(); MBBI != MBBE; ++MBBI) { 00206 visitMachineInstrBefore(MBBI); 00207 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) 00208 visitMachineOperand(&MBBI->getOperand(I), I); 00209 visitMachineInstrAfter(MBBI); 00210 } 00211 visitMachineBasicBlockAfter(MFI); 00212 } 00213 visitMachineFunctionAfter(); 00214 00215 if (OutFileName) 00216 OutFile.close(); 00217 else if (foundErrors) { 00218 std::string msg; 00219 raw_string_ostream Msg(msg); 00220 Msg << "Found " << foundErrors << " machine code errors."; 00221 llvm_report_error(Msg.str()); 00222 } 00223 00224 // Clean up. 00225 regsLive.clear(); 00226 regsDefined.clear(); 00227 regsDead.clear(); 00228 regsKilled.clear(); 00229 regsLiveInButUnused.clear(); 00230 MBBInfoMap.clear(); 00231 00232 return false; // no changes 00233 } 00234 00235 void 00236 MachineVerifier::report(const char *msg, const MachineFunction *MF) 00237 { 00238 assert(MF); 00239 *OS << "\n"; 00240 if (!foundErrors++) 00241 MF->print(OS); 00242 *OS << "*** Bad machine code: " << msg << " ***\n" 00243 << "- function: " << MF->getFunction()->getNameStr() << "\n"; 00244 } 00245 00246 void 00247 MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) 00248 { 00249 assert(MBB); 00250 report(msg, MBB->getParent()); 00251 *OS << "- basic block: " << MBB->getBasicBlock()->getNameStr() 00252 << " " << (void*)MBB 00253 << " (#" << MBB->getNumber() << ")\n"; 00254 } 00255 00256 void 00257 MachineVerifier::report(const char *msg, const MachineInstr *MI) 00258 { 00259 assert(MI); 00260 report(msg, MI->getParent()); 00261 *OS << "- instruction: "; 00262 MI->print(OS, TM); 00263 } 00264 00265 void 00266 MachineVerifier::report(const char *msg, 00267 const MachineOperand *MO, unsigned MONum) 00268 { 00269 assert(MO); 00270 report(msg, MO->getParent()); 00271 *OS << "- operand " << MONum << ": "; 00272 MO->print(*OS, TM); 00273 *OS << "\n"; 00274 } 00275 00276 void 00277 MachineVerifier::markReachable(const MachineBasicBlock *MBB) 00278 { 00279 BBInfo &MInfo = MBBInfoMap[MBB]; 00280 if (!MInfo.reachable) { 00281 MInfo.reachable = true; 00282 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 00283 SuE = MBB->succ_end(); SuI != SuE; ++SuI) 00284 markReachable(*SuI); 00285 } 00286 } 00287 00288 void 00289 MachineVerifier::visitMachineFunctionBefore() 00290 { 00291 regsReserved = TRI->getReservedRegs(*MF); 00292 00293 // A sub-register of a reserved register is also reserved 00294 for (int Reg = regsReserved.find_first(); Reg>=0; 00295 Reg = regsReserved.find_next(Reg)) { 00296 for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) { 00297 // FIXME: This should probably be: 00298 // assert(regsReserved.test(*Sub) && "Non-reserved sub-register"); 00299 regsReserved.set(*Sub); 00300 } 00301 } 00302 markReachable(&MF->front()); 00303 } 00304 00305 void 00306 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) 00307 { 00308 regsLive.clear(); 00309 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 00310 E = MBB->livein_end(); I != E; ++I) { 00311 if (!TargetRegisterInfo::isPhysicalRegister(*I)) { 00312 report("MBB live-in list contains non-physical register", MBB); 00313 continue; 00314 } 00315 regsLive.insert(*I); 00316 for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++) 00317 regsLive.insert(*R); 00318 } 00319 regsLiveInButUnused = regsLive; 00320 00321 const MachineFrameInfo *MFI = MF->getFrameInfo(); 00322 assert(MFI && "Function has no frame info"); 00323 BitVector PR = MFI->getPristineRegs(MBB); 00324 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { 00325 regsLive.insert(I); 00326 for (const unsigned *R = TRI->getSubRegisters(I); *R; R++) 00327 regsLive.insert(*R); 00328 } 00329 00330 regsKilled.clear(); 00331 regsDefined.clear(); 00332 } 00333 00334 void 00335 MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) 00336 { 00337 const TargetInstrDesc &TI = MI->getDesc(); 00338 if (MI->getNumExplicitOperands() < TI.getNumOperands()) { 00339 report("Too few operands", MI); 00340 *OS << TI.getNumOperands() << " operands expected, but " 00341 << MI->getNumExplicitOperands() << " given.\n"; 00342 } 00343 if (!TI.isVariadic()) { 00344 if (MI->getNumExplicitOperands() > TI.getNumOperands()) { 00345 report("Too many operands", MI); 00346 *OS << TI.getNumOperands() << " operands expected, but " 00347 << MI->getNumExplicitOperands() << " given.\n"; 00348 } 00349 } 00350 } 00351 00352 void 00353 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) 00354 { 00355 const MachineInstr *MI = MO->getParent(); 00356 const TargetInstrDesc &TI = MI->getDesc(); 00357 00358 // The first TI.NumDefs operands must be explicit register defines 00359 if (MONum < TI.getNumDefs()) { 00360 if (!MO->isReg()) 00361 report("Explicit definition must be a register", MO, MONum); 00362 else if (!MO->isDef()) 00363 report("Explicit definition marked as use", MO, MONum); 00364 else if (MO->isImplicit()) 00365 report("Explicit definition marked as implicit", MO, MONum); 00366 } 00367 00368 switch (MO->getType()) { 00369 case MachineOperand::MO_Register: { 00370 const unsigned Reg = MO->getReg(); 00371 if (!Reg) 00372 return; 00373 00374 // Check Live Variables. 00375 if (MO->isUndef()) { 00376 // An <undef> doesn't refer to any register, so just skip it. 00377 } else if (MO->isUse()) { 00378 regsLiveInButUnused.erase(Reg); 00379 00380 if (MO->isKill()) { 00381 addRegWithSubRegs(regsKilled, Reg); 00382 // Tied operands on two-address instuctions MUST NOT have a <kill> flag. 00383 if (MI->isRegTiedToDefOperand(MONum)) 00384 report("Illegal kill flag on two-address instruction operand", 00385 MO, MONum); 00386 } else { 00387 // TwoAddress instr modifying a reg is treated as kill+def. 00388 unsigned defIdx; 00389 if (MI->isRegTiedToDefOperand(MONum, &defIdx) && 00390 MI->getOperand(defIdx).getReg() == Reg) 00391 addRegWithSubRegs(regsKilled, Reg); 00392 } 00393 // Use of a dead register. 00394 if (!regsLive.count(Reg)) { 00395 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 00396 // Reserved registers may be used even when 'dead'. 00397 if (!isReserved(Reg)) 00398 report("Using an undefined physical register", MO, MONum); 00399 } else { 00400 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 00401 // We don't know which virtual registers are live in, so only complain 00402 // if vreg was killed in this MBB. Otherwise keep track of vregs that 00403 // must be live in. PHI instructions are handled separately. 00404 if (MInfo.regsKilled.count(Reg)) 00405 report("Using a killed virtual register", MO, MONum); 00406 else if (MI->getOpcode() != TargetInstrInfo::PHI) 00407 MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 00408 } 00409 } 00410 } else { 00411 assert(MO->isDef()); 00412 // Register defined. 00413 // TODO: verify that earlyclobber ops are not used. 00414 if (MO->isDead()) 00415 addRegWithSubRegs(regsDead, Reg); 00416 else 00417 addRegWithSubRegs(regsDefined, Reg); 00418 } 00419 00420 // Check register classes. 00421 if (MONum < TI.getNumOperands() && !MO->isImplicit()) { 00422 const TargetOperandInfo &TOI = TI.OpInfo[MONum]; 00423 unsigned SubIdx = MO->getSubReg(); 00424 00425 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 00426 unsigned sr = Reg; 00427 if (SubIdx) { 00428 unsigned s = TRI->getSubReg(Reg, SubIdx); 00429 if (!s) { 00430 report("Invalid subregister index for physical register", 00431 MO, MONum); 00432 return; 00433 } 00434 sr = s; 00435 } 00436 if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) { 00437 if (!DRC->contains(sr)) { 00438 report("Illegal physical register for instruction", MO, MONum); 00439 *OS << TRI->getName(sr) << " is not a " 00440 << DRC->getName() << " register.\n"; 00441 } 00442 } 00443 } else { 00444 // Virtual register. 00445 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 00446 if (SubIdx) { 00447 if (RC->subregclasses_begin()+SubIdx >= RC->subregclasses_end()) { 00448 report("Invalid subregister index for virtual register", MO, MONum); 00449 return; 00450 } 00451 RC = *(RC->subregclasses_begin()+SubIdx); 00452 } 00453 if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) { 00454 if (RC != DRC && !RC->hasSuperClass(DRC)) { 00455 report("Illegal virtual register for instruction", MO, MONum); 00456 *OS << "Expected a " << DRC->getName() << " register, but got a " 00457 << RC->getName() << " register\n"; 00458 } 00459 } 00460 } 00461 } 00462 break; 00463 } 00464 // Can PHI instrs refer to MBBs not in the CFG? X86 and ARM do. 00465 // case MachineOperand::MO_MachineBasicBlock: 00466 // if (MI->getOpcode() == TargetInstrInfo::PHI) { 00467 // if (!MO->getMBB()->isSuccessor(MI->getParent())) 00468 // report("PHI operand is not in the CFG", MO, MONum); 00469 // } 00470 // break; 00471 default: 00472 break; 00473 } 00474 } 00475 00476 void 00477 MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) 00478 { 00479 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 00480 set_union(MInfo.regsKilled, regsKilled); 00481 set_subtract(regsLive, regsKilled); 00482 regsKilled.clear(); 00483 00484 // Verify that both <def> and <def,dead> operands refer to dead registers. 00485 RegVector defs(regsDefined); 00486 defs.append(regsDead.begin(), regsDead.end()); 00487 00488 for (RegVector::const_iterator I = defs.begin(), E = defs.end(); 00489 I != E; ++I) { 00490 if (regsLive.count(*I)) { 00491 if (TargetRegisterInfo::isPhysicalRegister(*I)) { 00492 if (!allowPhysDoubleDefs && !isReserved(*I) && 00493 !regsLiveInButUnused.count(*I)) { 00494 report("Redefining a live physical register", MI); 00495 *OS << "Register " << TRI->getName(*I) 00496 << " was defined but already live.\n"; 00497 } 00498 } else { 00499 if (!allowVirtDoubleDefs) { 00500 report("Redefining a live virtual register", MI); 00501 *OS << "Virtual register %reg" << *I 00502 << " was defined but already live.\n"; 00503 } 00504 } 00505 } else if (TargetRegisterInfo::isVirtualRegister(*I) && 00506 !MInfo.regsKilled.count(*I)) { 00507 // Virtual register defined without being killed first must be dead on 00508 // entry. 00509 MInfo.vregsDeadIn.insert(std::make_pair(*I, MI)); 00510 } 00511 } 00512 00513 set_subtract(regsLive, regsDead); regsDead.clear(); 00514 set_union(regsLive, regsDefined); regsDefined.clear(); 00515 } 00516 00517 void 00518 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) 00519 { 00520 MBBInfoMap[MBB].regsLiveOut = regsLive; 00521 regsLive.clear(); 00522 } 00523 00524 // Calculate the largest possible vregsPassed sets. These are the registers that 00525 // can pass through an MBB live, but may not be live every time. It is assumed 00526 // that all vregsPassed sets are empty before the call. 00527 void 00528 MachineVerifier::calcMaxRegsPassed() 00529 { 00530 // First push live-out regs to successors' vregsPassed. Remember the MBBs that 00531 // have any vregsPassed. 00532 DenseSet<const MachineBasicBlock*> todo; 00533 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 00534 MFI != MFE; ++MFI) { 00535 const MachineBasicBlock &MBB(*MFI); 00536 BBInfo &MInfo = MBBInfoMap[&MBB]; 00537 if (!MInfo.reachable) 00538 continue; 00539 for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 00540 SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 00541 BBInfo &SInfo = MBBInfoMap[*SuI]; 00542 if (SInfo.addPassed(MInfo.regsLiveOut)) 00543 todo.insert(*SuI); 00544 } 00545 } 00546 00547 // Iteratively push vregsPassed to successors. This will converge to the same 00548 // final state regardless of DenseSet iteration order. 00549 while (!todo.empty()) { 00550 const MachineBasicBlock *MBB = *todo.begin(); 00551 todo.erase(MBB); 00552 BBInfo &MInfo = MBBInfoMap[MBB]; 00553 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 00554 SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 00555 if (*SuI == MBB) 00556 continue; 00557 BBInfo &SInfo = MBBInfoMap[*SuI]; 00558 if (SInfo.addPassed(MInfo.vregsPassed)) 00559 todo.insert(*SuI); 00560 } 00561 } 00562 } 00563 00564 // Calculate the minimum vregsPassed set. These are the registers that always 00565 // pass live through an MBB. The calculation assumes that calcMaxRegsPassed has 00566 // been called earlier. 00567 void 00568 MachineVerifier::calcMinRegsPassed() 00569 { 00570 DenseSet<const MachineBasicBlock*> todo; 00571 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 00572 MFI != MFE; ++MFI) 00573 todo.insert(MFI); 00574 00575 while (!todo.empty()) { 00576 const MachineBasicBlock *MBB = *todo.begin(); 00577 todo.erase(MBB); 00578 BBInfo &MInfo = MBBInfoMap[MBB]; 00579 00580 // Remove entries from vRegsPassed that are not live out from all 00581 // reachable predecessors. 00582 RegSet dead; 00583 for (RegSet::iterator I = MInfo.vregsPassed.begin(), 00584 E = MInfo.vregsPassed.end(); I != E; ++I) { 00585 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 00586 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 00587 BBInfo &PrInfo = MBBInfoMap[*PrI]; 00588 if (PrInfo.reachable && !PrInfo.isLiveOut(*I)) { 00589 dead.insert(*I); 00590 break; 00591 } 00592 } 00593 } 00594 // If any regs removed, we need to recheck successors. 00595 if (!dead.empty()) { 00596 set_subtract(MInfo.vregsPassed, dead); 00597 todo.insert(MBB->succ_begin(), MBB->succ_end()); 00598 } 00599 } 00600 } 00601 00602 // Check PHI instructions at the beginning of MBB. It is assumed that 00603 // calcMinRegsPassed has been run so BBInfo::isLiveOut is valid. 00604 void 00605 MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) 00606 { 00607 for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 00608 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) { 00609 DenseSet<const MachineBasicBlock*> seen; 00610 00611 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 00612 unsigned Reg = BBI->getOperand(i).getReg(); 00613 const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB(); 00614 if (!Pre->isSuccessor(MBB)) 00615 continue; 00616 seen.insert(Pre); 00617 BBInfo &PrInfo = MBBInfoMap[Pre]; 00618 if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 00619 report("PHI operand is not live-out from predecessor", 00620 &BBI->getOperand(i), i); 00621 } 00622 00623 // Did we see all predecessors? 00624 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 00625 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 00626 if (!seen.count(*PrI)) { 00627 report("Missing PHI operand", BBI); 00628 *OS << "MBB #" << (*PrI)->getNumber() 00629 << " is a predecessor according to the CFG.\n"; 00630 } 00631 } 00632 } 00633 } 00634 00635 void 00636 MachineVerifier::visitMachineFunctionAfter() 00637 { 00638 calcMaxRegsPassed(); 00639 00640 // With the maximal set of vregsPassed we can verify dead-in registers. 00641 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 00642 MFI != MFE; ++MFI) { 00643 BBInfo &MInfo = MBBInfoMap[MFI]; 00644 00645 // Skip unreachable MBBs. 00646 if (!MInfo.reachable) 00647 continue; 00648 00649 for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(), 00650 PrE = MFI->pred_end(); PrI != PrE; ++PrI) { 00651 BBInfo &PrInfo = MBBInfoMap[*PrI]; 00652 if (!PrInfo.reachable) 00653 continue; 00654 00655 // Verify physical live-ins. EH landing pads have magic live-ins so we 00656 // ignore them. 00657 if (!MFI->isLandingPad()) { 00658 for (MachineBasicBlock::const_livein_iterator I = MFI->livein_begin(), 00659 E = MFI->livein_end(); I != E; ++I) { 00660 if (TargetRegisterInfo::isPhysicalRegister(*I) && 00661 !isReserved (*I) && !PrInfo.isLiveOut(*I)) { 00662 report("Live-in physical register is not live-out from predecessor", 00663 MFI); 00664 *OS << "Register " << TRI->getName(*I) 00665 << " is not live-out from MBB #" << (*PrI)->getNumber() 00666 << ".\n"; 00667 } 00668 } 00669 } 00670 00671 00672 // Verify dead-in virtual registers. 00673 if (!allowVirtDoubleDefs) { 00674 for (RegMap::iterator I = MInfo.vregsDeadIn.begin(), 00675 E = MInfo.vregsDeadIn.end(); I != E; ++I) { 00676 // DeadIn register must be in neither regsLiveOut or vregsPassed of 00677 // any predecessor. 00678 if (PrInfo.isLiveOut(I->first)) { 00679 report("Live-in virtual register redefined", I->second); 00680 *OS << "Register %reg" << I->first 00681 << " was live-out from predecessor MBB #" 00682 << (*PrI)->getNumber() << ".\n"; 00683 } 00684 } 00685 } 00686 } 00687 } 00688 00689 calcMinRegsPassed(); 00690 00691 // With the minimal set of vregsPassed we can verify live-in virtual 00692 // registers, including PHI instructions. 00693 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 00694 MFI != MFE; ++MFI) { 00695 BBInfo &MInfo = MBBInfoMap[MFI]; 00696 00697 // Skip unreachable MBBs. 00698 if (!MInfo.reachable) 00699 continue; 00700 00701 checkPHIOps(MFI); 00702 00703 for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(), 00704 PrE = MFI->pred_end(); PrI != PrE; ++PrI) { 00705 BBInfo &PrInfo = MBBInfoMap[*PrI]; 00706 if (!PrInfo.reachable) 00707 continue; 00708 00709 for (RegMap::iterator I = MInfo.vregsLiveIn.begin(), 00710 E = MInfo.vregsLiveIn.end(); I != E; ++I) { 00711 if (!PrInfo.isLiveOut(I->first)) { 00712 report("Used virtual register is not live-in", I->second); 00713 *OS << "Register %reg" << I->first 00714 << " is not live-out from predecessor MBB #" 00715 << (*PrI)->getNumber() 00716 << ".\n"; 00717 } 00718 } 00719 } 00720 } 00721 }