MachineVerifier.cpp revision 198090
1//===-- MachineVerifier.cpp - Machine Code Verifier -------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Pass to verify generated machine code. The following is checked: 11// 12// Operand counts: All explicit operands must be present. 13// 14// Register classes: All physical and virtual register operands must be 15// compatible with the register class required by the instruction descriptor. 16// 17// Register live intervals: Registers must be defined only once, and must be 18// defined before use. 19// 20// The machine code verifier is enabled from LLVMTargetMachine.cpp with the 21// command-line option -verify-machineinstrs, or by defining the environment 22// variable LLVM_VERIFY_MACHINEINSTRS to the name of a file that will receive 23// the verifier errors. 24//===----------------------------------------------------------------------===// 25 26#include "llvm/Function.h" 27#include "llvm/CodeGen/LiveVariables.h" 28#include "llvm/CodeGen/MachineFunctionPass.h" 29#include "llvm/CodeGen/MachineFrameInfo.h" 30#include "llvm/CodeGen/MachineMemOperand.h" 31#include "llvm/CodeGen/MachineRegisterInfo.h" 32#include "llvm/CodeGen/Passes.h" 33#include "llvm/Target/TargetMachine.h" 34#include "llvm/Target/TargetRegisterInfo.h" 35#include "llvm/Target/TargetInstrInfo.h" 36#include "llvm/ADT/DenseSet.h" 37#include "llvm/ADT/SetOperations.h" 38#include "llvm/ADT/SmallVector.h" 39#include "llvm/Support/Compiler.h" 40#include "llvm/Support/Debug.h" 41#include "llvm/Support/ErrorHandling.h" 42#include "llvm/Support/raw_ostream.h" 43using namespace llvm; 44 45namespace { 46 struct VISIBILITY_HIDDEN MachineVerifier : public MachineFunctionPass { 47 static char ID; // Pass ID, replacement for typeid 48 49 MachineVerifier(bool allowDoubleDefs = false) : 50 MachineFunctionPass(&ID), 51 allowVirtDoubleDefs(allowDoubleDefs), 52 allowPhysDoubleDefs(allowDoubleDefs), 53 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) 54 {} 55 56 void getAnalysisUsage(AnalysisUsage &AU) const { 57 AU.setPreservesAll(); 58 MachineFunctionPass::getAnalysisUsage(AU); 59 } 60 61 bool runOnMachineFunction(MachineFunction &MF); 62 63 const bool allowVirtDoubleDefs; 64 const bool allowPhysDoubleDefs; 65 66 const char *const OutFileName; 67 raw_ostream *OS; 68 const MachineFunction *MF; 69 const TargetMachine *TM; 70 const TargetRegisterInfo *TRI; 71 const MachineRegisterInfo *MRI; 72 73 unsigned foundErrors; 74 75 typedef SmallVector<unsigned, 16> RegVector; 76 typedef DenseSet<unsigned> RegSet; 77 typedef DenseMap<unsigned, const MachineInstr*> RegMap; 78 79 BitVector regsReserved; 80 RegSet regsLive; 81 RegVector regsDefined, regsDead, regsKilled; 82 RegSet regsLiveInButUnused; 83 84 // Add Reg and any sub-registers to RV 85 void addRegWithSubRegs(RegVector &RV, unsigned Reg) { 86 RV.push_back(Reg); 87 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 88 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 89 RV.push_back(*R); 90 } 91 92 struct BBInfo { 93 // Is this MBB reachable from the MF entry point? 94 bool reachable; 95 96 // Vregs that must be live in because they are used without being 97 // defined. Map value is the user. 98 RegMap vregsLiveIn; 99 100 // Vregs that must be dead in because they are defined without being 101 // killed first. Map value is the defining instruction. 102 RegMap vregsDeadIn; 103 104 // Regs killed in MBB. They may be defined again, and will then be in both 105 // regsKilled and regsLiveOut. 106 RegSet regsKilled; 107 108 // Regs defined in MBB and live out. Note that vregs passing through may 109 // be live out without being mentioned here. 110 RegSet regsLiveOut; 111 112 // Vregs that pass through MBB untouched. This set is disjoint from 113 // regsKilled and regsLiveOut. 114 RegSet vregsPassed; 115 116 BBInfo() : reachable(false) {} 117 118 // Add register to vregsPassed if it belongs there. Return true if 119 // anything changed. 120 bool addPassed(unsigned Reg) { 121 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 122 return false; 123 if (regsKilled.count(Reg) || regsLiveOut.count(Reg)) 124 return false; 125 return vregsPassed.insert(Reg).second; 126 } 127 128 // Same for a full set. 129 bool addPassed(const RegSet &RS) { 130 bool changed = false; 131 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 132 if (addPassed(*I)) 133 changed = true; 134 return changed; 135 } 136 137 // Live-out registers are either in regsLiveOut or vregsPassed. 138 bool isLiveOut(unsigned Reg) const { 139 return regsLiveOut.count(Reg) || vregsPassed.count(Reg); 140 } 141 }; 142 143 // Extra register info per MBB. 144 DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap; 145 146 bool isReserved(unsigned Reg) { 147 return Reg < regsReserved.size() && regsReserved.test(Reg); 148 } 149 150 void visitMachineFunctionBefore(); 151 void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); 152 void visitMachineInstrBefore(const MachineInstr *MI); 153 void visitMachineOperand(const MachineOperand *MO, unsigned MONum); 154 void visitMachineInstrAfter(const MachineInstr *MI); 155 void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB); 156 void visitMachineFunctionAfter(); 157 158 void report(const char *msg, const MachineFunction *MF); 159 void report(const char *msg, const MachineBasicBlock *MBB); 160 void report(const char *msg, const MachineInstr *MI); 161 void report(const char *msg, const MachineOperand *MO, unsigned MONum); 162 163 void markReachable(const MachineBasicBlock *MBB); 164 void calcMaxRegsPassed(); 165 void calcMinRegsPassed(); 166 void checkPHIOps(const MachineBasicBlock *MBB); 167 }; 168} 169 170char MachineVerifier::ID = 0; 171static RegisterPass<MachineVerifier> 172MachineVer("machineverifier", "Verify generated machine code"); 173static const PassInfo *const MachineVerifyID = &MachineVer; 174 175FunctionPass *llvm::createMachineVerifierPass(bool allowPhysDoubleDefs) { 176 return new MachineVerifier(allowPhysDoubleDefs); 177} 178 179bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { 180 raw_ostream *OutFile = 0; 181 if (OutFileName) { 182 std::string ErrorInfo; 183 OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, 184 raw_fd_ostream::F_Append); 185 if (!ErrorInfo.empty()) { 186 errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n'; 187 exit(1); 188 } 189 190 OS = OutFile; 191 } else { 192 OS = &errs(); 193 } 194 195 foundErrors = 0; 196 197 this->MF = &MF; 198 TM = &MF.getTarget(); 199 TRI = TM->getRegisterInfo(); 200 MRI = &MF.getRegInfo(); 201 202 visitMachineFunctionBefore(); 203 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 204 MFI!=MFE; ++MFI) { 205 visitMachineBasicBlockBefore(MFI); 206 for (MachineBasicBlock::const_iterator MBBI = MFI->begin(), 207 MBBE = MFI->end(); MBBI != MBBE; ++MBBI) { 208 visitMachineInstrBefore(MBBI); 209 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) 210 visitMachineOperand(&MBBI->getOperand(I), I); 211 visitMachineInstrAfter(MBBI); 212 } 213 visitMachineBasicBlockAfter(MFI); 214 } 215 visitMachineFunctionAfter(); 216 217 if (OutFile) 218 delete OutFile; 219 else if (foundErrors) 220 llvm_report_error("Found "+Twine(foundErrors)+" machine code errors."); 221 222 // Clean up. 223 regsLive.clear(); 224 regsDefined.clear(); 225 regsDead.clear(); 226 regsKilled.clear(); 227 regsLiveInButUnused.clear(); 228 MBBInfoMap.clear(); 229 230 return false; // no changes 231} 232 233void MachineVerifier::report(const char *msg, const MachineFunction *MF) { 234 assert(MF); 235 *OS << '\n'; 236 if (!foundErrors++) 237 MF->print(*OS); 238 *OS << "*** Bad machine code: " << msg << " ***\n" 239 << "- function: " << MF->getFunction()->getNameStr() << "\n"; 240} 241 242void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { 243 assert(MBB); 244 report(msg, MBB->getParent()); 245 *OS << "- basic block: " << MBB->getBasicBlock()->getNameStr() 246 << " " << (void*)MBB 247 << " (#" << MBB->getNumber() << ")\n"; 248} 249 250void MachineVerifier::report(const char *msg, const MachineInstr *MI) { 251 assert(MI); 252 report(msg, MI->getParent()); 253 *OS << "- instruction: "; 254 MI->print(*OS, TM); 255} 256 257void MachineVerifier::report(const char *msg, 258 const MachineOperand *MO, unsigned MONum) { 259 assert(MO); 260 report(msg, MO->getParent()); 261 *OS << "- operand " << MONum << ": "; 262 MO->print(*OS, TM); 263 *OS << "\n"; 264} 265 266void MachineVerifier::markReachable(const MachineBasicBlock *MBB) { 267 BBInfo &MInfo = MBBInfoMap[MBB]; 268 if (!MInfo.reachable) { 269 MInfo.reachable = true; 270 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 271 SuE = MBB->succ_end(); SuI != SuE; ++SuI) 272 markReachable(*SuI); 273 } 274} 275 276void MachineVerifier::visitMachineFunctionBefore() { 277 regsReserved = TRI->getReservedRegs(*MF); 278 279 // A sub-register of a reserved register is also reserved 280 for (int Reg = regsReserved.find_first(); Reg>=0; 281 Reg = regsReserved.find_next(Reg)) { 282 for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) { 283 // FIXME: This should probably be: 284 // assert(regsReserved.test(*Sub) && "Non-reserved sub-register"); 285 regsReserved.set(*Sub); 286 } 287 } 288 markReachable(&MF->front()); 289} 290 291void MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { 292 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 293 294 // Start with minimal CFG sanity checks. 295 MachineFunction::const_iterator MBBI = MBB; 296 ++MBBI; 297 if (MBBI != MF->end()) { 298 // Block is not last in function. 299 if (!MBB->isSuccessor(MBBI)) { 300 // Block does not fall through. 301 if (MBB->empty()) { 302 report("MBB doesn't fall through but is empty!", MBB); 303 } 304 } 305 if (TII->BlockHasNoFallThrough(*MBB)) { 306 if (MBB->empty()) { 307 report("TargetInstrInfo says the block has no fall through, but the " 308 "block is empty!", MBB); 309 } else if (!MBB->back().getDesc().isBarrier()) { 310 report("TargetInstrInfo says the block has no fall through, but the " 311 "block does not end in a barrier!", MBB); 312 } 313 } 314 } else { 315 // Block is last in function. 316 if (MBB->empty()) { 317 report("MBB is last in function but is empty!", MBB); 318 } 319 } 320 321 // Call AnalyzeBranch. If it succeeds, there several more conditions to check. 322 MachineBasicBlock *TBB = 0, *FBB = 0; 323 SmallVector<MachineOperand, 4> Cond; 324 if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB), 325 TBB, FBB, Cond)) { 326 // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's 327 // check whether its answers match up with reality. 328 if (!TBB && !FBB) { 329 // Block falls through to its successor. 330 MachineFunction::const_iterator MBBI = MBB; 331 ++MBBI; 332 if (MBBI == MF->end()) { 333 // It's possible that the block legitimately ends with a noreturn 334 // call or an unreachable, in which case it won't actually fall 335 // out the bottom of the function. 336 } else if (MBB->succ_empty()) { 337 // It's possible that the block legitimately ends with a noreturn 338 // call or an unreachable, in which case it won't actuall fall 339 // out of the block. 340 } else if (MBB->succ_size() != 1) { 341 report("MBB exits via unconditional fall-through but doesn't have " 342 "exactly one CFG successor!", MBB); 343 } else if (MBB->succ_begin()[0] != MBBI) { 344 report("MBB exits via unconditional fall-through but its successor " 345 "differs from its CFG successor!", MBB); 346 } 347 if (!MBB->empty() && MBB->back().getDesc().isBarrier()) { 348 report("MBB exits via unconditional fall-through but ends with a " 349 "barrier instruction!", MBB); 350 } 351 if (!Cond.empty()) { 352 report("MBB exits via unconditional fall-through but has a condition!", 353 MBB); 354 } 355 } else if (TBB && !FBB && Cond.empty()) { 356 // Block unconditionally branches somewhere. 357 if (MBB->succ_size() != 1) { 358 report("MBB exits via unconditional branch but doesn't have " 359 "exactly one CFG successor!", MBB); 360 } else if (MBB->succ_begin()[0] != TBB) { 361 report("MBB exits via unconditional branch but the CFG " 362 "successor doesn't match the actual successor!", MBB); 363 } 364 if (MBB->empty()) { 365 report("MBB exits via unconditional branch but doesn't contain " 366 "any instructions!", MBB); 367 } else if (!MBB->back().getDesc().isBarrier()) { 368 report("MBB exits via unconditional branch but doesn't end with a " 369 "barrier instruction!", MBB); 370 } else if (!MBB->back().getDesc().isTerminator()) { 371 report("MBB exits via unconditional branch but the branch isn't a " 372 "terminator instruction!", MBB); 373 } 374 } else if (TBB && !FBB && !Cond.empty()) { 375 // Block conditionally branches somewhere, otherwise falls through. 376 MachineFunction::const_iterator MBBI = MBB; 377 ++MBBI; 378 if (MBBI == MF->end()) { 379 report("MBB conditionally falls through out of function!", MBB); 380 } if (MBB->succ_size() != 2) { 381 report("MBB exits via conditional branch/fall-through but doesn't have " 382 "exactly two CFG successors!", MBB); 383 } else if ((MBB->succ_begin()[0] == TBB && MBB->succ_end()[1] == MBBI) || 384 (MBB->succ_begin()[1] == TBB && MBB->succ_end()[0] == MBBI)) { 385 report("MBB exits via conditional branch/fall-through but the CFG " 386 "successors don't match the actual successors!", MBB); 387 } 388 if (MBB->empty()) { 389 report("MBB exits via conditional branch/fall-through but doesn't " 390 "contain any instructions!", MBB); 391 } else if (MBB->back().getDesc().isBarrier()) { 392 report("MBB exits via conditional branch/fall-through but ends with a " 393 "barrier instruction!", MBB); 394 } else if (!MBB->back().getDesc().isTerminator()) { 395 report("MBB exits via conditional branch/fall-through but the branch " 396 "isn't a terminator instruction!", MBB); 397 } 398 } else if (TBB && FBB) { 399 // Block conditionally branches somewhere, otherwise branches 400 // somewhere else. 401 if (MBB->succ_size() != 2) { 402 report("MBB exits via conditional branch/branch but doesn't have " 403 "exactly two CFG successors!", MBB); 404 } else if ((MBB->succ_begin()[0] == TBB && MBB->succ_end()[1] == FBB) || 405 (MBB->succ_begin()[1] == TBB && MBB->succ_end()[0] == FBB)) { 406 report("MBB exits via conditional branch/branch but the CFG " 407 "successors don't match the actual successors!", MBB); 408 } 409 if (MBB->empty()) { 410 report("MBB exits via conditional branch/branch but doesn't " 411 "contain any instructions!", MBB); 412 } else if (!MBB->back().getDesc().isBarrier()) { 413 report("MBB exits via conditional branch/branch but doesn't end with a " 414 "barrier instruction!", MBB); 415 } else if (!MBB->back().getDesc().isTerminator()) { 416 report("MBB exits via conditional branch/branch but the branch " 417 "isn't a terminator instruction!", MBB); 418 } 419 if (Cond.empty()) { 420 report("MBB exits via conditinal branch/branch but there's no " 421 "condition!", MBB); 422 } 423 } else { 424 report("AnalyzeBranch returned invalid data!", MBB); 425 } 426 } 427 428 regsLive.clear(); 429 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 430 E = MBB->livein_end(); I != E; ++I) { 431 if (!TargetRegisterInfo::isPhysicalRegister(*I)) { 432 report("MBB live-in list contains non-physical register", MBB); 433 continue; 434 } 435 regsLive.insert(*I); 436 for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++) 437 regsLive.insert(*R); 438 } 439 regsLiveInButUnused = regsLive; 440 441 const MachineFrameInfo *MFI = MF->getFrameInfo(); 442 assert(MFI && "Function has no frame info"); 443 BitVector PR = MFI->getPristineRegs(MBB); 444 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { 445 regsLive.insert(I); 446 for (const unsigned *R = TRI->getSubRegisters(I); *R; R++) 447 regsLive.insert(*R); 448 } 449 450 regsKilled.clear(); 451 regsDefined.clear(); 452} 453 454void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { 455 const TargetInstrDesc &TI = MI->getDesc(); 456 if (MI->getNumOperands() < TI.getNumOperands()) { 457 report("Too few operands", MI); 458 *OS << TI.getNumOperands() << " operands expected, but " 459 << MI->getNumExplicitOperands() << " given.\n"; 460 } 461 462 // Check the MachineMemOperands for basic consistency. 463 for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 464 E = MI->memoperands_end(); I != E; ++I) { 465 if ((*I)->isLoad() && !TI.mayLoad()) 466 report("Missing mayLoad flag", MI); 467 if ((*I)->isStore() && !TI.mayStore()) 468 report("Missing mayStore flag", MI); 469 } 470} 471 472void 473MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { 474 const MachineInstr *MI = MO->getParent(); 475 const TargetInstrDesc &TI = MI->getDesc(); 476 477 // The first TI.NumDefs operands must be explicit register defines 478 if (MONum < TI.getNumDefs()) { 479 if (!MO->isReg()) 480 report("Explicit definition must be a register", MO, MONum); 481 else if (!MO->isDef()) 482 report("Explicit definition marked as use", MO, MONum); 483 else if (MO->isImplicit()) 484 report("Explicit definition marked as implicit", MO, MONum); 485 } else if (MONum < TI.getNumOperands()) { 486 if (MO->isReg()) { 487 if (MO->isDef()) 488 report("Explicit operand marked as def", MO, MONum); 489 if (MO->isImplicit()) 490 report("Explicit operand marked as implicit", MO, MONum); 491 } 492 } else { 493 if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic()) 494 report("Extra explicit operand on non-variadic instruction", MO, MONum); 495 } 496 497 switch (MO->getType()) { 498 case MachineOperand::MO_Register: { 499 const unsigned Reg = MO->getReg(); 500 if (!Reg) 501 return; 502 503 // Check Live Variables. 504 if (MO->isUndef()) { 505 // An <undef> doesn't refer to any register, so just skip it. 506 } else if (MO->isUse()) { 507 regsLiveInButUnused.erase(Reg); 508 509 if (MO->isKill()) { 510 addRegWithSubRegs(regsKilled, Reg); 511 // Tied operands on two-address instuctions MUST NOT have a <kill> flag. 512 if (MI->isRegTiedToDefOperand(MONum)) 513 report("Illegal kill flag on two-address instruction operand", 514 MO, MONum); 515 } else { 516 // TwoAddress instr modifying a reg is treated as kill+def. 517 unsigned defIdx; 518 if (MI->isRegTiedToDefOperand(MONum, &defIdx) && 519 MI->getOperand(defIdx).getReg() == Reg) 520 addRegWithSubRegs(regsKilled, Reg); 521 } 522 // Use of a dead register. 523 if (!regsLive.count(Reg)) { 524 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 525 // Reserved registers may be used even when 'dead'. 526 if (!isReserved(Reg)) 527 report("Using an undefined physical register", MO, MONum); 528 } else { 529 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 530 // We don't know which virtual registers are live in, so only complain 531 // if vreg was killed in this MBB. Otherwise keep track of vregs that 532 // must be live in. PHI instructions are handled separately. 533 if (MInfo.regsKilled.count(Reg)) 534 report("Using a killed virtual register", MO, MONum); 535 else if (MI->getOpcode() != TargetInstrInfo::PHI) 536 MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 537 } 538 } 539 } else { 540 assert(MO->isDef()); 541 // Register defined. 542 // TODO: verify that earlyclobber ops are not used. 543 if (MO->isDead()) 544 addRegWithSubRegs(regsDead, Reg); 545 else 546 addRegWithSubRegs(regsDefined, Reg); 547 } 548 549 // Check register classes. 550 if (MONum < TI.getNumOperands() && !MO->isImplicit()) { 551 const TargetOperandInfo &TOI = TI.OpInfo[MONum]; 552 unsigned SubIdx = MO->getSubReg(); 553 554 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 555 unsigned sr = Reg; 556 if (SubIdx) { 557 unsigned s = TRI->getSubReg(Reg, SubIdx); 558 if (!s) { 559 report("Invalid subregister index for physical register", 560 MO, MONum); 561 return; 562 } 563 sr = s; 564 } 565 if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) { 566 if (!DRC->contains(sr)) { 567 report("Illegal physical register for instruction", MO, MONum); 568 *OS << TRI->getName(sr) << " is not a " 569 << DRC->getName() << " register.\n"; 570 } 571 } 572 } else { 573 // Virtual register. 574 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 575 if (SubIdx) { 576 if (RC->subregclasses_begin()+SubIdx >= RC->subregclasses_end()) { 577 report("Invalid subregister index for virtual register", MO, MONum); 578 return; 579 } 580 RC = *(RC->subregclasses_begin()+SubIdx); 581 } 582 if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) { 583 if (RC != DRC && !RC->hasSuperClass(DRC)) { 584 report("Illegal virtual register for instruction", MO, MONum); 585 *OS << "Expected a " << DRC->getName() << " register, but got a " 586 << RC->getName() << " register\n"; 587 } 588 } 589 } 590 } 591 break; 592 } 593 594 case MachineOperand::MO_MachineBasicBlock: 595 if (MI->getOpcode() == TargetInstrInfo::PHI) { 596 if (!MO->getMBB()->isSuccessor(MI->getParent())) 597 report("PHI operand is not in the CFG", MO, MONum); 598 } 599 break; 600 601 default: 602 break; 603 } 604} 605 606void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { 607 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 608 set_union(MInfo.regsKilled, regsKilled); 609 set_subtract(regsLive, regsKilled); 610 regsKilled.clear(); 611 612 // Verify that both <def> and <def,dead> operands refer to dead registers. 613 RegVector defs(regsDefined); 614 defs.append(regsDead.begin(), regsDead.end()); 615 616 for (RegVector::const_iterator I = defs.begin(), E = defs.end(); 617 I != E; ++I) { 618 if (regsLive.count(*I)) { 619 if (TargetRegisterInfo::isPhysicalRegister(*I)) { 620 if (!allowPhysDoubleDefs && !isReserved(*I) && 621 !regsLiveInButUnused.count(*I)) { 622 report("Redefining a live physical register", MI); 623 *OS << "Register " << TRI->getName(*I) 624 << " was defined but already live.\n"; 625 } 626 } else { 627 if (!allowVirtDoubleDefs) { 628 report("Redefining a live virtual register", MI); 629 *OS << "Virtual register %reg" << *I 630 << " was defined but already live.\n"; 631 } 632 } 633 } else if (TargetRegisterInfo::isVirtualRegister(*I) && 634 !MInfo.regsKilled.count(*I)) { 635 // Virtual register defined without being killed first must be dead on 636 // entry. 637 MInfo.vregsDeadIn.insert(std::make_pair(*I, MI)); 638 } 639 } 640 641 set_subtract(regsLive, regsDead); regsDead.clear(); 642 set_union(regsLive, regsDefined); regsDefined.clear(); 643} 644 645void 646MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { 647 MBBInfoMap[MBB].regsLiveOut = regsLive; 648 regsLive.clear(); 649} 650 651// Calculate the largest possible vregsPassed sets. These are the registers that 652// can pass through an MBB live, but may not be live every time. It is assumed 653// that all vregsPassed sets are empty before the call. 654void MachineVerifier::calcMaxRegsPassed() { 655 // First push live-out regs to successors' vregsPassed. Remember the MBBs that 656 // have any vregsPassed. 657 DenseSet<const MachineBasicBlock*> todo; 658 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 659 MFI != MFE; ++MFI) { 660 const MachineBasicBlock &MBB(*MFI); 661 BBInfo &MInfo = MBBInfoMap[&MBB]; 662 if (!MInfo.reachable) 663 continue; 664 for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 665 SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 666 BBInfo &SInfo = MBBInfoMap[*SuI]; 667 if (SInfo.addPassed(MInfo.regsLiveOut)) 668 todo.insert(*SuI); 669 } 670 } 671 672 // Iteratively push vregsPassed to successors. This will converge to the same 673 // final state regardless of DenseSet iteration order. 674 while (!todo.empty()) { 675 const MachineBasicBlock *MBB = *todo.begin(); 676 todo.erase(MBB); 677 BBInfo &MInfo = MBBInfoMap[MBB]; 678 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 679 SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 680 if (*SuI == MBB) 681 continue; 682 BBInfo &SInfo = MBBInfoMap[*SuI]; 683 if (SInfo.addPassed(MInfo.vregsPassed)) 684 todo.insert(*SuI); 685 } 686 } 687} 688 689// Calculate the minimum vregsPassed set. These are the registers that always 690// pass live through an MBB. The calculation assumes that calcMaxRegsPassed has 691// been called earlier. 692void MachineVerifier::calcMinRegsPassed() { 693 DenseSet<const MachineBasicBlock*> todo; 694 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 695 MFI != MFE; ++MFI) 696 todo.insert(MFI); 697 698 while (!todo.empty()) { 699 const MachineBasicBlock *MBB = *todo.begin(); 700 todo.erase(MBB); 701 BBInfo &MInfo = MBBInfoMap[MBB]; 702 703 // Remove entries from vRegsPassed that are not live out from all 704 // reachable predecessors. 705 RegSet dead; 706 for (RegSet::iterator I = MInfo.vregsPassed.begin(), 707 E = MInfo.vregsPassed.end(); I != E; ++I) { 708 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 709 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 710 BBInfo &PrInfo = MBBInfoMap[*PrI]; 711 if (PrInfo.reachable && !PrInfo.isLiveOut(*I)) { 712 dead.insert(*I); 713 break; 714 } 715 } 716 } 717 // If any regs removed, we need to recheck successors. 718 if (!dead.empty()) { 719 set_subtract(MInfo.vregsPassed, dead); 720 todo.insert(MBB->succ_begin(), MBB->succ_end()); 721 } 722 } 723} 724 725// Check PHI instructions at the beginning of MBB. It is assumed that 726// calcMinRegsPassed has been run so BBInfo::isLiveOut is valid. 727void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) { 728 for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 729 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) { 730 DenseSet<const MachineBasicBlock*> seen; 731 732 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 733 unsigned Reg = BBI->getOperand(i).getReg(); 734 const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB(); 735 if (!Pre->isSuccessor(MBB)) 736 continue; 737 seen.insert(Pre); 738 BBInfo &PrInfo = MBBInfoMap[Pre]; 739 if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 740 report("PHI operand is not live-out from predecessor", 741 &BBI->getOperand(i), i); 742 } 743 744 // Did we see all predecessors? 745 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 746 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 747 if (!seen.count(*PrI)) { 748 report("Missing PHI operand", BBI); 749 *OS << "MBB #" << (*PrI)->getNumber() 750 << " is a predecessor according to the CFG.\n"; 751 } 752 } 753 } 754} 755 756void MachineVerifier::visitMachineFunctionAfter() { 757 calcMaxRegsPassed(); 758 759 // With the maximal set of vregsPassed we can verify dead-in registers. 760 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 761 MFI != MFE; ++MFI) { 762 BBInfo &MInfo = MBBInfoMap[MFI]; 763 764 // Skip unreachable MBBs. 765 if (!MInfo.reachable) 766 continue; 767 768 for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(), 769 PrE = MFI->pred_end(); PrI != PrE; ++PrI) { 770 BBInfo &PrInfo = MBBInfoMap[*PrI]; 771 if (!PrInfo.reachable) 772 continue; 773 774 // Verify physical live-ins. EH landing pads have magic live-ins so we 775 // ignore them. 776 if (!MFI->isLandingPad()) { 777 for (MachineBasicBlock::const_livein_iterator I = MFI->livein_begin(), 778 E = MFI->livein_end(); I != E; ++I) { 779 if (TargetRegisterInfo::isPhysicalRegister(*I) && 780 !isReserved (*I) && !PrInfo.isLiveOut(*I)) { 781 report("Live-in physical register is not live-out from predecessor", 782 MFI); 783 *OS << "Register " << TRI->getName(*I) 784 << " is not live-out from MBB #" << (*PrI)->getNumber() 785 << ".\n"; 786 } 787 } 788 } 789 790 791 // Verify dead-in virtual registers. 792 if (!allowVirtDoubleDefs) { 793 for (RegMap::iterator I = MInfo.vregsDeadIn.begin(), 794 E = MInfo.vregsDeadIn.end(); I != E; ++I) { 795 // DeadIn register must be in neither regsLiveOut or vregsPassed of 796 // any predecessor. 797 if (PrInfo.isLiveOut(I->first)) { 798 report("Live-in virtual register redefined", I->second); 799 *OS << "Register %reg" << I->first 800 << " was live-out from predecessor MBB #" 801 << (*PrI)->getNumber() << ".\n"; 802 } 803 } 804 } 805 } 806 } 807 808 calcMinRegsPassed(); 809 810 // With the minimal set of vregsPassed we can verify live-in virtual 811 // registers, including PHI instructions. 812 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 813 MFI != MFE; ++MFI) { 814 BBInfo &MInfo = MBBInfoMap[MFI]; 815 816 // Skip unreachable MBBs. 817 if (!MInfo.reachable) 818 continue; 819 820 checkPHIOps(MFI); 821 822 for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(), 823 PrE = MFI->pred_end(); PrI != PrE; ++PrI) { 824 BBInfo &PrInfo = MBBInfoMap[*PrI]; 825 if (!PrInfo.reachable) 826 continue; 827 828 for (RegMap::iterator I = MInfo.vregsLiveIn.begin(), 829 E = MInfo.vregsLiveIn.end(); I != E; ++I) { 830 if (!PrInfo.isLiveOut(I->first)) { 831 report("Used virtual register is not live-in", I->second); 832 *OS << "Register %reg" << I->first 833 << " is not live-out from predecessor MBB #" 834 << (*PrI)->getNumber() 835 << ".\n"; 836 } 837 } 838 } 839 } 840} 841