MachineVerifier.cpp revision 245431
1//===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===// 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/BasicBlock.h" 27#include "llvm/InlineAsm.h" 28#include "llvm/Instructions.h" 29#include "llvm/CodeGen/LiveIntervalAnalysis.h" 30#include "llvm/CodeGen/LiveVariables.h" 31#include "llvm/CodeGen/LiveStackAnalysis.h" 32#include "llvm/CodeGen/MachineInstrBundle.h" 33#include "llvm/CodeGen/MachineFunctionPass.h" 34#include "llvm/CodeGen/MachineFrameInfo.h" 35#include "llvm/CodeGen/MachineMemOperand.h" 36#include "llvm/CodeGen/MachineRegisterInfo.h" 37#include "llvm/CodeGen/Passes.h" 38#include "llvm/MC/MCAsmInfo.h" 39#include "llvm/Target/TargetMachine.h" 40#include "llvm/Target/TargetRegisterInfo.h" 41#include "llvm/Target/TargetInstrInfo.h" 42#include "llvm/ADT/DenseSet.h" 43#include "llvm/ADT/SetOperations.h" 44#include "llvm/ADT/SmallVector.h" 45#include "llvm/Support/Debug.h" 46#include "llvm/Support/ErrorHandling.h" 47#include "llvm/Support/raw_ostream.h" 48using namespace llvm; 49 50namespace { 51 struct MachineVerifier { 52 53 MachineVerifier(Pass *pass, const char *b) : 54 PASS(pass), 55 Banner(b), 56 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) 57 {} 58 59 bool runOnMachineFunction(MachineFunction &MF); 60 61 Pass *const PASS; 62 const char *Banner; 63 const char *const OutFileName; 64 raw_ostream *OS; 65 const MachineFunction *MF; 66 const TargetMachine *TM; 67 const TargetInstrInfo *TII; 68 const TargetRegisterInfo *TRI; 69 const MachineRegisterInfo *MRI; 70 71 unsigned foundErrors; 72 73 typedef SmallVector<unsigned, 16> RegVector; 74 typedef SmallVector<const uint32_t*, 4> RegMaskVector; 75 typedef DenseSet<unsigned> RegSet; 76 typedef DenseMap<unsigned, const MachineInstr*> RegMap; 77 typedef SmallPtrSet<const MachineBasicBlock*, 8> BlockSet; 78 79 const MachineInstr *FirstTerminator; 80 BlockSet FunctionBlocks; 81 82 BitVector regsReserved; 83 RegSet regsLive; 84 RegVector regsDefined, regsDead, regsKilled; 85 RegMaskVector regMasks; 86 RegSet regsLiveInButUnused; 87 88 SlotIndex lastIndex; 89 90 // Add Reg and any sub-registers to RV 91 void addRegWithSubRegs(RegVector &RV, unsigned Reg) { 92 RV.push_back(Reg); 93 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 94 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 95 RV.push_back(*SubRegs); 96 } 97 98 struct BBInfo { 99 // Is this MBB reachable from the MF entry point? 100 bool reachable; 101 102 // Vregs that must be live in because they are used without being 103 // defined. Map value is the user. 104 RegMap vregsLiveIn; 105 106 // Regs killed in MBB. They may be defined again, and will then be in both 107 // regsKilled and regsLiveOut. 108 RegSet regsKilled; 109 110 // Regs defined in MBB and live out. Note that vregs passing through may 111 // be live out without being mentioned here. 112 RegSet regsLiveOut; 113 114 // Vregs that pass through MBB untouched. This set is disjoint from 115 // regsKilled and regsLiveOut. 116 RegSet vregsPassed; 117 118 // Vregs that must pass through MBB because they are needed by a successor 119 // block. This set is disjoint from regsLiveOut. 120 RegSet vregsRequired; 121 122 // Set versions of block's predecessor and successor lists. 123 BlockSet Preds, Succs; 124 125 BBInfo() : reachable(false) {} 126 127 // Add register to vregsPassed if it belongs there. Return true if 128 // anything changed. 129 bool addPassed(unsigned Reg) { 130 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 131 return false; 132 if (regsKilled.count(Reg) || regsLiveOut.count(Reg)) 133 return false; 134 return vregsPassed.insert(Reg).second; 135 } 136 137 // Same for a full set. 138 bool addPassed(const RegSet &RS) { 139 bool changed = false; 140 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 141 if (addPassed(*I)) 142 changed = true; 143 return changed; 144 } 145 146 // Add register to vregsRequired if it belongs there. Return true if 147 // anything changed. 148 bool addRequired(unsigned Reg) { 149 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 150 return false; 151 if (regsLiveOut.count(Reg)) 152 return false; 153 return vregsRequired.insert(Reg).second; 154 } 155 156 // Same for a full set. 157 bool addRequired(const RegSet &RS) { 158 bool changed = false; 159 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I) 160 if (addRequired(*I)) 161 changed = true; 162 return changed; 163 } 164 165 // Same for a full map. 166 bool addRequired(const RegMap &RM) { 167 bool changed = false; 168 for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I) 169 if (addRequired(I->first)) 170 changed = true; 171 return changed; 172 } 173 174 // Live-out registers are either in regsLiveOut or vregsPassed. 175 bool isLiveOut(unsigned Reg) const { 176 return regsLiveOut.count(Reg) || vregsPassed.count(Reg); 177 } 178 }; 179 180 // Extra register info per MBB. 181 DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap; 182 183 bool isReserved(unsigned Reg) { 184 return Reg < regsReserved.size() && regsReserved.test(Reg); 185 } 186 187 bool isAllocatable(unsigned Reg) { 188 return Reg < TRI->getNumRegs() && MRI->isAllocatable(Reg); 189 } 190 191 // Analysis information if available 192 LiveVariables *LiveVars; 193 LiveIntervals *LiveInts; 194 LiveStacks *LiveStks; 195 SlotIndexes *Indexes; 196 197 void visitMachineFunctionBefore(); 198 void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB); 199 void visitMachineBundleBefore(const MachineInstr *MI); 200 void visitMachineInstrBefore(const MachineInstr *MI); 201 void visitMachineOperand(const MachineOperand *MO, unsigned MONum); 202 void visitMachineInstrAfter(const MachineInstr *MI); 203 void visitMachineBundleAfter(const MachineInstr *MI); 204 void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB); 205 void visitMachineFunctionAfter(); 206 207 void report(const char *msg, const MachineFunction *MF); 208 void report(const char *msg, const MachineBasicBlock *MBB); 209 void report(const char *msg, const MachineInstr *MI); 210 void report(const char *msg, const MachineOperand *MO, unsigned MONum); 211 void report(const char *msg, const MachineFunction *MF, 212 const LiveInterval &LI); 213 void report(const char *msg, const MachineBasicBlock *MBB, 214 const LiveInterval &LI); 215 216 void verifyInlineAsm(const MachineInstr *MI); 217 218 void checkLiveness(const MachineOperand *MO, unsigned MONum); 219 void markReachable(const MachineBasicBlock *MBB); 220 void calcRegsPassed(); 221 void checkPHIOps(const MachineBasicBlock *MBB); 222 223 void calcRegsRequired(); 224 void verifyLiveVariables(); 225 void verifyLiveIntervals(); 226 void verifyLiveInterval(const LiveInterval&); 227 void verifyLiveIntervalValue(const LiveInterval&, VNInfo*); 228 void verifyLiveIntervalSegment(const LiveInterval&, 229 LiveInterval::const_iterator); 230 }; 231 232 struct MachineVerifierPass : public MachineFunctionPass { 233 static char ID; // Pass ID, replacement for typeid 234 const char *const Banner; 235 236 MachineVerifierPass(const char *b = 0) 237 : MachineFunctionPass(ID), Banner(b) { 238 initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry()); 239 } 240 241 void getAnalysisUsage(AnalysisUsage &AU) const { 242 AU.setPreservesAll(); 243 MachineFunctionPass::getAnalysisUsage(AU); 244 } 245 246 bool runOnMachineFunction(MachineFunction &MF) { 247 MF.verify(this, Banner); 248 return false; 249 } 250 }; 251 252} 253 254char MachineVerifierPass::ID = 0; 255INITIALIZE_PASS(MachineVerifierPass, "machineverifier", 256 "Verify generated machine code", false, false) 257 258FunctionPass *llvm::createMachineVerifierPass(const char *Banner) { 259 return new MachineVerifierPass(Banner); 260} 261 262void MachineFunction::verify(Pass *p, const char *Banner) const { 263 MachineVerifier(p, Banner) 264 .runOnMachineFunction(const_cast<MachineFunction&>(*this)); 265} 266 267bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) { 268 raw_ostream *OutFile = 0; 269 if (OutFileName) { 270 std::string ErrorInfo; 271 OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, 272 raw_fd_ostream::F_Append); 273 if (!ErrorInfo.empty()) { 274 errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n'; 275 exit(1); 276 } 277 278 OS = OutFile; 279 } else { 280 OS = &errs(); 281 } 282 283 foundErrors = 0; 284 285 this->MF = &MF; 286 TM = &MF.getTarget(); 287 TII = TM->getInstrInfo(); 288 TRI = TM->getRegisterInfo(); 289 MRI = &MF.getRegInfo(); 290 291 LiveVars = NULL; 292 LiveInts = NULL; 293 LiveStks = NULL; 294 Indexes = NULL; 295 if (PASS) { 296 LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>(); 297 // We don't want to verify LiveVariables if LiveIntervals is available. 298 if (!LiveInts) 299 LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>(); 300 LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>(); 301 Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>(); 302 } 303 304 visitMachineFunctionBefore(); 305 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 306 MFI!=MFE; ++MFI) { 307 visitMachineBasicBlockBefore(MFI); 308 // Keep track of the current bundle header. 309 const MachineInstr *CurBundle = 0; 310 for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), 311 MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) { 312 if (MBBI->getParent() != MFI) { 313 report("Bad instruction parent pointer", MFI); 314 *OS << "Instruction: " << *MBBI; 315 continue; 316 } 317 // Is this a bundle header? 318 if (!MBBI->isInsideBundle()) { 319 if (CurBundle) 320 visitMachineBundleAfter(CurBundle); 321 CurBundle = MBBI; 322 visitMachineBundleBefore(CurBundle); 323 } else if (!CurBundle) 324 report("No bundle header", MBBI); 325 visitMachineInstrBefore(MBBI); 326 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) 327 visitMachineOperand(&MBBI->getOperand(I), I); 328 visitMachineInstrAfter(MBBI); 329 } 330 if (CurBundle) 331 visitMachineBundleAfter(CurBundle); 332 visitMachineBasicBlockAfter(MFI); 333 } 334 visitMachineFunctionAfter(); 335 336 if (OutFile) 337 delete OutFile; 338 else if (foundErrors) 339 report_fatal_error("Found "+Twine(foundErrors)+" machine code errors."); 340 341 // Clean up. 342 regsLive.clear(); 343 regsDefined.clear(); 344 regsDead.clear(); 345 regsKilled.clear(); 346 regMasks.clear(); 347 regsLiveInButUnused.clear(); 348 MBBInfoMap.clear(); 349 350 return false; // no changes 351} 352 353void MachineVerifier::report(const char *msg, const MachineFunction *MF) { 354 assert(MF); 355 *OS << '\n'; 356 if (!foundErrors++) { 357 if (Banner) 358 *OS << "# " << Banner << '\n'; 359 MF->print(*OS, Indexes); 360 } 361 *OS << "*** Bad machine code: " << msg << " ***\n" 362 << "- function: " << MF->getName() << "\n"; 363} 364 365void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { 366 assert(MBB); 367 report(msg, MBB->getParent()); 368 *OS << "- basic block: BB#" << MBB->getNumber() 369 << ' ' << MBB->getName() 370 << " (" << (const void*)MBB << ')'; 371 if (Indexes) 372 *OS << " [" << Indexes->getMBBStartIdx(MBB) 373 << ';' << Indexes->getMBBEndIdx(MBB) << ')'; 374 *OS << '\n'; 375} 376 377void MachineVerifier::report(const char *msg, const MachineInstr *MI) { 378 assert(MI); 379 report(msg, MI->getParent()); 380 *OS << "- instruction: "; 381 if (Indexes && Indexes->hasIndex(MI)) 382 *OS << Indexes->getInstructionIndex(MI) << '\t'; 383 MI->print(*OS, TM); 384} 385 386void MachineVerifier::report(const char *msg, 387 const MachineOperand *MO, unsigned MONum) { 388 assert(MO); 389 report(msg, MO->getParent()); 390 *OS << "- operand " << MONum << ": "; 391 MO->print(*OS, TM); 392 *OS << "\n"; 393} 394 395void MachineVerifier::report(const char *msg, const MachineFunction *MF, 396 const LiveInterval &LI) { 397 report(msg, MF); 398 *OS << "- interval: "; 399 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) 400 *OS << PrintReg(LI.reg, TRI); 401 else 402 *OS << PrintRegUnit(LI.reg, TRI); 403 *OS << ' ' << LI << '\n'; 404} 405 406void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB, 407 const LiveInterval &LI) { 408 report(msg, MBB); 409 *OS << "- interval: "; 410 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) 411 *OS << PrintReg(LI.reg, TRI); 412 else 413 *OS << PrintRegUnit(LI.reg, TRI); 414 *OS << ' ' << LI << '\n'; 415} 416 417void MachineVerifier::markReachable(const MachineBasicBlock *MBB) { 418 BBInfo &MInfo = MBBInfoMap[MBB]; 419 if (!MInfo.reachable) { 420 MInfo.reachable = true; 421 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 422 SuE = MBB->succ_end(); SuI != SuE; ++SuI) 423 markReachable(*SuI); 424 } 425} 426 427void MachineVerifier::visitMachineFunctionBefore() { 428 lastIndex = SlotIndex(); 429 regsReserved = MRI->getReservedRegs(); 430 431 // A sub-register of a reserved register is also reserved 432 for (int Reg = regsReserved.find_first(); Reg>=0; 433 Reg = regsReserved.find_next(Reg)) { 434 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 435 // FIXME: This should probably be: 436 // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register"); 437 regsReserved.set(*SubRegs); 438 } 439 } 440 441 markReachable(&MF->front()); 442 443 // Build a set of the basic blocks in the function. 444 FunctionBlocks.clear(); 445 for (MachineFunction::const_iterator 446 I = MF->begin(), E = MF->end(); I != E; ++I) { 447 FunctionBlocks.insert(I); 448 BBInfo &MInfo = MBBInfoMap[I]; 449 450 MInfo.Preds.insert(I->pred_begin(), I->pred_end()); 451 if (MInfo.Preds.size() != I->pred_size()) 452 report("MBB has duplicate entries in its predecessor list.", I); 453 454 MInfo.Succs.insert(I->succ_begin(), I->succ_end()); 455 if (MInfo.Succs.size() != I->succ_size()) 456 report("MBB has duplicate entries in its successor list.", I); 457 } 458} 459 460// Does iterator point to a and b as the first two elements? 461static bool matchPair(MachineBasicBlock::const_succ_iterator i, 462 const MachineBasicBlock *a, const MachineBasicBlock *b) { 463 if (*i == a) 464 return *++i == b; 465 if (*i == b) 466 return *++i == a; 467 return false; 468} 469 470void 471MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { 472 FirstTerminator = 0; 473 474 if (MRI->isSSA()) { 475 // If this block has allocatable physical registers live-in, check that 476 // it is an entry block or landing pad. 477 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 478 LE = MBB->livein_end(); 479 LI != LE; ++LI) { 480 unsigned reg = *LI; 481 if (isAllocatable(reg) && !MBB->isLandingPad() && 482 MBB != MBB->getParent()->begin()) { 483 report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB); 484 } 485 } 486 } 487 488 // Count the number of landing pad successors. 489 SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs; 490 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 491 E = MBB->succ_end(); I != E; ++I) { 492 if ((*I)->isLandingPad()) 493 LandingPadSuccs.insert(*I); 494 if (!FunctionBlocks.count(*I)) 495 report("MBB has successor that isn't part of the function.", MBB); 496 if (!MBBInfoMap[*I].Preds.count(MBB)) { 497 report("Inconsistent CFG", MBB); 498 *OS << "MBB is not in the predecessor list of the successor BB#" 499 << (*I)->getNumber() << ".\n"; 500 } 501 } 502 503 // Check the predecessor list. 504 for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 505 E = MBB->pred_end(); I != E; ++I) { 506 if (!FunctionBlocks.count(*I)) 507 report("MBB has predecessor that isn't part of the function.", MBB); 508 if (!MBBInfoMap[*I].Succs.count(MBB)) { 509 report("Inconsistent CFG", MBB); 510 *OS << "MBB is not in the successor list of the predecessor BB#" 511 << (*I)->getNumber() << ".\n"; 512 } 513 } 514 515 const MCAsmInfo *AsmInfo = TM->getMCAsmInfo(); 516 const BasicBlock *BB = MBB->getBasicBlock(); 517 if (LandingPadSuccs.size() > 1 && 518 !(AsmInfo && 519 AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj && 520 BB && isa<SwitchInst>(BB->getTerminator()))) 521 report("MBB has more than one landing pad successor", MBB); 522 523 // Call AnalyzeBranch. If it succeeds, there several more conditions to check. 524 MachineBasicBlock *TBB = 0, *FBB = 0; 525 SmallVector<MachineOperand, 4> Cond; 526 if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB), 527 TBB, FBB, Cond)) { 528 // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's 529 // check whether its answers match up with reality. 530 if (!TBB && !FBB) { 531 // Block falls through to its successor. 532 MachineFunction::const_iterator MBBI = MBB; 533 ++MBBI; 534 if (MBBI == MF->end()) { 535 // It's possible that the block legitimately ends with a noreturn 536 // call or an unreachable, in which case it won't actually fall 537 // out the bottom of the function. 538 } else if (MBB->succ_size() == LandingPadSuccs.size()) { 539 // It's possible that the block legitimately ends with a noreturn 540 // call or an unreachable, in which case it won't actuall fall 541 // out of the block. 542 } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 543 report("MBB exits via unconditional fall-through but doesn't have " 544 "exactly one CFG successor!", MBB); 545 } else if (!MBB->isSuccessor(MBBI)) { 546 report("MBB exits via unconditional fall-through but its successor " 547 "differs from its CFG successor!", MBB); 548 } 549 if (!MBB->empty() && getBundleStart(&MBB->back())->isBarrier() && 550 !TII->isPredicated(getBundleStart(&MBB->back()))) { 551 report("MBB exits via unconditional fall-through but ends with a " 552 "barrier instruction!", MBB); 553 } 554 if (!Cond.empty()) { 555 report("MBB exits via unconditional fall-through but has a condition!", 556 MBB); 557 } 558 } else if (TBB && !FBB && Cond.empty()) { 559 // Block unconditionally branches somewhere. 560 if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 561 report("MBB exits via unconditional branch but doesn't have " 562 "exactly one CFG successor!", MBB); 563 } else if (!MBB->isSuccessor(TBB)) { 564 report("MBB exits via unconditional branch but the CFG " 565 "successor doesn't match the actual successor!", MBB); 566 } 567 if (MBB->empty()) { 568 report("MBB exits via unconditional branch but doesn't contain " 569 "any instructions!", MBB); 570 } else if (!getBundleStart(&MBB->back())->isBarrier()) { 571 report("MBB exits via unconditional branch but doesn't end with a " 572 "barrier instruction!", MBB); 573 } else if (!getBundleStart(&MBB->back())->isTerminator()) { 574 report("MBB exits via unconditional branch but the branch isn't a " 575 "terminator instruction!", MBB); 576 } 577 } else if (TBB && !FBB && !Cond.empty()) { 578 // Block conditionally branches somewhere, otherwise falls through. 579 MachineFunction::const_iterator MBBI = MBB; 580 ++MBBI; 581 if (MBBI == MF->end()) { 582 report("MBB conditionally falls through out of function!", MBB); 583 } if (MBB->succ_size() == 1) { 584 // A conditional branch with only one successor is weird, but allowed. 585 if (&*MBBI != TBB) 586 report("MBB exits via conditional branch/fall-through but only has " 587 "one CFG successor!", MBB); 588 else if (TBB != *MBB->succ_begin()) 589 report("MBB exits via conditional branch/fall-through but the CFG " 590 "successor don't match the actual successor!", MBB); 591 } else if (MBB->succ_size() != 2) { 592 report("MBB exits via conditional branch/fall-through but doesn't have " 593 "exactly two CFG successors!", MBB); 594 } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) { 595 report("MBB exits via conditional branch/fall-through but the CFG " 596 "successors don't match the actual successors!", MBB); 597 } 598 if (MBB->empty()) { 599 report("MBB exits via conditional branch/fall-through but doesn't " 600 "contain any instructions!", MBB); 601 } else if (getBundleStart(&MBB->back())->isBarrier()) { 602 report("MBB exits via conditional branch/fall-through but ends with a " 603 "barrier instruction!", MBB); 604 } else if (!getBundleStart(&MBB->back())->isTerminator()) { 605 report("MBB exits via conditional branch/fall-through but the branch " 606 "isn't a terminator instruction!", MBB); 607 } 608 } else if (TBB && FBB) { 609 // Block conditionally branches somewhere, otherwise branches 610 // somewhere else. 611 if (MBB->succ_size() == 1) { 612 // A conditional branch with only one successor is weird, but allowed. 613 if (FBB != TBB) 614 report("MBB exits via conditional branch/branch through but only has " 615 "one CFG successor!", MBB); 616 else if (TBB != *MBB->succ_begin()) 617 report("MBB exits via conditional branch/branch through but the CFG " 618 "successor don't match the actual successor!", MBB); 619 } else if (MBB->succ_size() != 2) { 620 report("MBB exits via conditional branch/branch but doesn't have " 621 "exactly two CFG successors!", MBB); 622 } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) { 623 report("MBB exits via conditional branch/branch but the CFG " 624 "successors don't match the actual successors!", MBB); 625 } 626 if (MBB->empty()) { 627 report("MBB exits via conditional branch/branch but doesn't " 628 "contain any instructions!", MBB); 629 } else if (!getBundleStart(&MBB->back())->isBarrier()) { 630 report("MBB exits via conditional branch/branch but doesn't end with a " 631 "barrier instruction!", MBB); 632 } else if (!getBundleStart(&MBB->back())->isTerminator()) { 633 report("MBB exits via conditional branch/branch but the branch " 634 "isn't a terminator instruction!", MBB); 635 } 636 if (Cond.empty()) { 637 report("MBB exits via conditinal branch/branch but there's no " 638 "condition!", MBB); 639 } 640 } else { 641 report("AnalyzeBranch returned invalid data!", MBB); 642 } 643 } 644 645 regsLive.clear(); 646 for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 647 E = MBB->livein_end(); I != E; ++I) { 648 if (!TargetRegisterInfo::isPhysicalRegister(*I)) { 649 report("MBB live-in list contains non-physical register", MBB); 650 continue; 651 } 652 regsLive.insert(*I); 653 for (MCSubRegIterator SubRegs(*I, TRI); SubRegs.isValid(); ++SubRegs) 654 regsLive.insert(*SubRegs); 655 } 656 regsLiveInButUnused = regsLive; 657 658 const MachineFrameInfo *MFI = MF->getFrameInfo(); 659 assert(MFI && "Function has no frame info"); 660 BitVector PR = MFI->getPristineRegs(MBB); 661 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { 662 regsLive.insert(I); 663 for (MCSubRegIterator SubRegs(I, TRI); SubRegs.isValid(); ++SubRegs) 664 regsLive.insert(*SubRegs); 665 } 666 667 regsKilled.clear(); 668 regsDefined.clear(); 669 670 if (Indexes) 671 lastIndex = Indexes->getMBBStartIdx(MBB); 672} 673 674// This function gets called for all bundle headers, including normal 675// stand-alone unbundled instructions. 676void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) { 677 if (Indexes && Indexes->hasIndex(MI)) { 678 SlotIndex idx = Indexes->getInstructionIndex(MI); 679 if (!(idx > lastIndex)) { 680 report("Instruction index out of order", MI); 681 *OS << "Last instruction was at " << lastIndex << '\n'; 682 } 683 lastIndex = idx; 684 } 685 686 // Ensure non-terminators don't follow terminators. 687 // Ignore predicated terminators formed by if conversion. 688 // FIXME: If conversion shouldn't need to violate this rule. 689 if (MI->isTerminator() && !TII->isPredicated(MI)) { 690 if (!FirstTerminator) 691 FirstTerminator = MI; 692 } else if (FirstTerminator) { 693 report("Non-terminator instruction after the first terminator", MI); 694 *OS << "First terminator was:\t" << *FirstTerminator; 695 } 696} 697 698// The operands on an INLINEASM instruction must follow a template. 699// Verify that the flag operands make sense. 700void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) { 701 // The first two operands on INLINEASM are the asm string and global flags. 702 if (MI->getNumOperands() < 2) { 703 report("Too few operands on inline asm", MI); 704 return; 705 } 706 if (!MI->getOperand(0).isSymbol()) 707 report("Asm string must be an external symbol", MI); 708 if (!MI->getOperand(1).isImm()) 709 report("Asm flags must be an immediate", MI); 710 // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2, 711 // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16. 712 if (!isUInt<5>(MI->getOperand(1).getImm())) 713 report("Unknown asm flags", &MI->getOperand(1), 1); 714 715 assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed"); 716 717 unsigned OpNo = InlineAsm::MIOp_FirstOperand; 718 unsigned NumOps; 719 for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) { 720 const MachineOperand &MO = MI->getOperand(OpNo); 721 // There may be implicit ops after the fixed operands. 722 if (!MO.isImm()) 723 break; 724 NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm()); 725 } 726 727 if (OpNo > MI->getNumOperands()) 728 report("Missing operands in last group", MI); 729 730 // An optional MDNode follows the groups. 731 if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata()) 732 ++OpNo; 733 734 // All trailing operands must be implicit registers. 735 for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) { 736 const MachineOperand &MO = MI->getOperand(OpNo); 737 if (!MO.isReg() || !MO.isImplicit()) 738 report("Expected implicit register after groups", &MO, OpNo); 739 } 740} 741 742void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { 743 const MCInstrDesc &MCID = MI->getDesc(); 744 if (MI->getNumOperands() < MCID.getNumOperands()) { 745 report("Too few operands", MI); 746 *OS << MCID.getNumOperands() << " operands expected, but " 747 << MI->getNumExplicitOperands() << " given.\n"; 748 } 749 750 // Check the tied operands. 751 if (MI->isInlineAsm()) 752 verifyInlineAsm(MI); 753 754 // Check the MachineMemOperands for basic consistency. 755 for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 756 E = MI->memoperands_end(); I != E; ++I) { 757 if ((*I)->isLoad() && !MI->mayLoad()) 758 report("Missing mayLoad flag", MI); 759 if ((*I)->isStore() && !MI->mayStore()) 760 report("Missing mayStore flag", MI); 761 } 762 763 // Debug values must not have a slot index. 764 // Other instructions must have one, unless they are inside a bundle. 765 if (LiveInts) { 766 bool mapped = !LiveInts->isNotInMIMap(MI); 767 if (MI->isDebugValue()) { 768 if (mapped) 769 report("Debug instruction has a slot index", MI); 770 } else if (MI->isInsideBundle()) { 771 if (mapped) 772 report("Instruction inside bundle has a slot index", MI); 773 } else { 774 if (!mapped) 775 report("Missing slot index", MI); 776 } 777 } 778 779 StringRef ErrorInfo; 780 if (!TII->verifyInstruction(MI, ErrorInfo)) 781 report(ErrorInfo.data(), MI); 782} 783 784void 785MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { 786 const MachineInstr *MI = MO->getParent(); 787 const MCInstrDesc &MCID = MI->getDesc(); 788 789 // The first MCID.NumDefs operands must be explicit register defines 790 if (MONum < MCID.getNumDefs()) { 791 const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 792 if (!MO->isReg()) 793 report("Explicit definition must be a register", MO, MONum); 794 else if (!MO->isDef() && !MCOI.isOptionalDef()) 795 report("Explicit definition marked as use", MO, MONum); 796 else if (MO->isImplicit()) 797 report("Explicit definition marked as implicit", MO, MONum); 798 } else if (MONum < MCID.getNumOperands()) { 799 const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 800 // Don't check if it's the last operand in a variadic instruction. See, 801 // e.g., LDM_RET in the arm back end. 802 if (MO->isReg() && 803 !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { 804 if (MO->isDef() && !MCOI.isOptionalDef()) 805 report("Explicit operand marked as def", MO, MONum); 806 if (MO->isImplicit()) 807 report("Explicit operand marked as implicit", MO, MONum); 808 } 809 810 int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO); 811 if (TiedTo != -1) { 812 if (!MO->isReg()) 813 report("Tied use must be a register", MO, MONum); 814 else if (!MO->isTied()) 815 report("Operand should be tied", MO, MONum); 816 else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum)) 817 report("Tied def doesn't match MCInstrDesc", MO, MONum); 818 } else if (MO->isReg() && MO->isTied()) 819 report("Explicit operand should not be tied", MO, MONum); 820 } else { 821 // ARM adds %reg0 operands to indicate predicates. We'll allow that. 822 if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg()) 823 report("Extra explicit operand on non-variadic instruction", MO, MONum); 824 } 825 826 switch (MO->getType()) { 827 case MachineOperand::MO_Register: { 828 const unsigned Reg = MO->getReg(); 829 if (!Reg) 830 return; 831 if (MRI->tracksLiveness() && !MI->isDebugValue()) 832 checkLiveness(MO, MONum); 833 834 // Verify the consistency of tied operands. 835 if (MO->isTied()) { 836 unsigned OtherIdx = MI->findTiedOperandIdx(MONum); 837 const MachineOperand &OtherMO = MI->getOperand(OtherIdx); 838 if (!OtherMO.isReg()) 839 report("Must be tied to a register", MO, MONum); 840 if (!OtherMO.isTied()) 841 report("Missing tie flags on tied operand", MO, MONum); 842 if (MI->findTiedOperandIdx(OtherIdx) != MONum) 843 report("Inconsistent tie links", MO, MONum); 844 if (MONum < MCID.getNumDefs()) { 845 if (OtherIdx < MCID.getNumOperands()) { 846 if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO)) 847 report("Explicit def tied to explicit use without tie constraint", 848 MO, MONum); 849 } else { 850 if (!OtherMO.isImplicit()) 851 report("Explicit def should be tied to implicit use", MO, MONum); 852 } 853 } 854 } 855 856 // Verify two-address constraints after leaving SSA form. 857 unsigned DefIdx; 858 if (!MRI->isSSA() && MO->isUse() && 859 MI->isRegTiedToDefOperand(MONum, &DefIdx) && 860 Reg != MI->getOperand(DefIdx).getReg()) 861 report("Two-address instruction operands must be identical", MO, MONum); 862 863 // Check register classes. 864 if (MONum < MCID.getNumOperands() && !MO->isImplicit()) { 865 unsigned SubIdx = MO->getSubReg(); 866 867 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 868 if (SubIdx) { 869 report("Illegal subregister index for physical register", MO, MONum); 870 return; 871 } 872 if (const TargetRegisterClass *DRC = 873 TII->getRegClass(MCID, MONum, TRI, *MF)) { 874 if (!DRC->contains(Reg)) { 875 report("Illegal physical register for instruction", MO, MONum); 876 *OS << TRI->getName(Reg) << " is not a " 877 << DRC->getName() << " register.\n"; 878 } 879 } 880 } else { 881 // Virtual register. 882 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 883 if (SubIdx) { 884 const TargetRegisterClass *SRC = 885 TRI->getSubClassWithSubReg(RC, SubIdx); 886 if (!SRC) { 887 report("Invalid subregister index for virtual register", MO, MONum); 888 *OS << "Register class " << RC->getName() 889 << " does not support subreg index " << SubIdx << "\n"; 890 return; 891 } 892 if (RC != SRC) { 893 report("Invalid register class for subregister index", MO, MONum); 894 *OS << "Register class " << RC->getName() 895 << " does not fully support subreg index " << SubIdx << "\n"; 896 return; 897 } 898 } 899 if (const TargetRegisterClass *DRC = 900 TII->getRegClass(MCID, MONum, TRI, *MF)) { 901 if (SubIdx) { 902 const TargetRegisterClass *SuperRC = 903 TRI->getLargestLegalSuperClass(RC); 904 if (!SuperRC) { 905 report("No largest legal super class exists.", MO, MONum); 906 return; 907 } 908 DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx); 909 if (!DRC) { 910 report("No matching super-reg register class.", MO, MONum); 911 return; 912 } 913 } 914 if (!RC->hasSuperClassEq(DRC)) { 915 report("Illegal virtual register for instruction", MO, MONum); 916 *OS << "Expected a " << DRC->getName() << " register, but got a " 917 << RC->getName() << " register\n"; 918 } 919 } 920 } 921 } 922 break; 923 } 924 925 case MachineOperand::MO_RegisterMask: 926 regMasks.push_back(MO->getRegMask()); 927 break; 928 929 case MachineOperand::MO_MachineBasicBlock: 930 if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent())) 931 report("PHI operand is not in the CFG", MO, MONum); 932 break; 933 934 case MachineOperand::MO_FrameIndex: 935 if (LiveStks && LiveStks->hasInterval(MO->getIndex()) && 936 LiveInts && !LiveInts->isNotInMIMap(MI)) { 937 LiveInterval &LI = LiveStks->getInterval(MO->getIndex()); 938 SlotIndex Idx = LiveInts->getInstructionIndex(MI); 939 if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) { 940 report("Instruction loads from dead spill slot", MO, MONum); 941 *OS << "Live stack: " << LI << '\n'; 942 } 943 if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) { 944 report("Instruction stores to dead spill slot", MO, MONum); 945 *OS << "Live stack: " << LI << '\n'; 946 } 947 } 948 break; 949 950 default: 951 break; 952 } 953} 954 955void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { 956 const MachineInstr *MI = MO->getParent(); 957 const unsigned Reg = MO->getReg(); 958 959 // Both use and def operands can read a register. 960 if (MO->readsReg()) { 961 regsLiveInButUnused.erase(Reg); 962 963 if (MO->isKill()) 964 addRegWithSubRegs(regsKilled, Reg); 965 966 // Check that LiveVars knows this kill. 967 if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) && 968 MO->isKill()) { 969 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 970 if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end()) 971 report("Kill missing from LiveVariables", MO, MONum); 972 } 973 974 // Check LiveInts liveness and kill. 975 if (LiveInts && !LiveInts->isNotInMIMap(MI)) { 976 SlotIndex UseIdx = LiveInts->getInstructionIndex(MI); 977 // Check the cached regunit intervals. 978 if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) { 979 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 980 if (const LiveInterval *LI = LiveInts->getCachedRegUnit(*Units)) { 981 LiveRangeQuery LRQ(*LI, UseIdx); 982 if (!LRQ.valueIn()) { 983 report("No live range at use", MO, MONum); 984 *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI) 985 << ' ' << *LI << '\n'; 986 } 987 if (MO->isKill() && !LRQ.isKill()) { 988 report("Live range continues after kill flag", MO, MONum); 989 *OS << PrintRegUnit(*Units, TRI) << ' ' << *LI << '\n'; 990 } 991 } 992 } 993 } 994 995 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 996 if (LiveInts->hasInterval(Reg)) { 997 // This is a virtual register interval. 998 const LiveInterval &LI = LiveInts->getInterval(Reg); 999 LiveRangeQuery LRQ(LI, UseIdx); 1000 if (!LRQ.valueIn()) { 1001 report("No live range at use", MO, MONum); 1002 *OS << UseIdx << " is not live in " << LI << '\n'; 1003 } 1004 // Check for extra kill flags. 1005 // Note that we allow missing kill flags for now. 1006 if (MO->isKill() && !LRQ.isKill()) { 1007 report("Live range continues after kill flag", MO, MONum); 1008 *OS << "Live range: " << LI << '\n'; 1009 } 1010 } else { 1011 report("Virtual register has no live interval", MO, MONum); 1012 } 1013 } 1014 } 1015 1016 // Use of a dead register. 1017 if (!regsLive.count(Reg)) { 1018 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 1019 // Reserved registers may be used even when 'dead'. 1020 if (!isReserved(Reg)) 1021 report("Using an undefined physical register", MO, MONum); 1022 } else if (MRI->def_empty(Reg)) { 1023 report("Reading virtual register without a def", MO, MONum); 1024 } else { 1025 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1026 // We don't know which virtual registers are live in, so only complain 1027 // if vreg was killed in this MBB. Otherwise keep track of vregs that 1028 // must be live in. PHI instructions are handled separately. 1029 if (MInfo.regsKilled.count(Reg)) 1030 report("Using a killed virtual register", MO, MONum); 1031 else if (!MI->isPHI()) 1032 MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 1033 } 1034 } 1035 } 1036 1037 if (MO->isDef()) { 1038 // Register defined. 1039 // TODO: verify that earlyclobber ops are not used. 1040 if (MO->isDead()) 1041 addRegWithSubRegs(regsDead, Reg); 1042 else 1043 addRegWithSubRegs(regsDefined, Reg); 1044 1045 // Verify SSA form. 1046 if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) && 1047 llvm::next(MRI->def_begin(Reg)) != MRI->def_end()) 1048 report("Multiple virtual register defs in SSA form", MO, MONum); 1049 1050 // Check LiveInts for a live range, but only for virtual registers. 1051 if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) && 1052 !LiveInts->isNotInMIMap(MI)) { 1053 SlotIndex DefIdx = LiveInts->getInstructionIndex(MI); 1054 DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber()); 1055 if (LiveInts->hasInterval(Reg)) { 1056 const LiveInterval &LI = LiveInts->getInterval(Reg); 1057 if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) { 1058 assert(VNI && "NULL valno is not allowed"); 1059 if (VNI->def != DefIdx) { 1060 report("Inconsistent valno->def", MO, MONum); 1061 *OS << "Valno " << VNI->id << " is not defined at " 1062 << DefIdx << " in " << LI << '\n'; 1063 } 1064 } else { 1065 report("No live range at def", MO, MONum); 1066 *OS << DefIdx << " is not live in " << LI << '\n'; 1067 } 1068 } else { 1069 report("Virtual register has no Live interval", MO, MONum); 1070 } 1071 } 1072 } 1073} 1074 1075void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { 1076} 1077 1078// This function gets called after visiting all instructions in a bundle. The 1079// argument points to the bundle header. 1080// Normal stand-alone instructions are also considered 'bundles', and this 1081// function is called for all of them. 1082void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) { 1083 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1084 set_union(MInfo.regsKilled, regsKilled); 1085 set_subtract(regsLive, regsKilled); regsKilled.clear(); 1086 // Kill any masked registers. 1087 while (!regMasks.empty()) { 1088 const uint32_t *Mask = regMasks.pop_back_val(); 1089 for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I) 1090 if (TargetRegisterInfo::isPhysicalRegister(*I) && 1091 MachineOperand::clobbersPhysReg(Mask, *I)) 1092 regsDead.push_back(*I); 1093 } 1094 set_subtract(regsLive, regsDead); regsDead.clear(); 1095 set_union(regsLive, regsDefined); regsDefined.clear(); 1096} 1097 1098void 1099MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { 1100 MBBInfoMap[MBB].regsLiveOut = regsLive; 1101 regsLive.clear(); 1102 1103 if (Indexes) { 1104 SlotIndex stop = Indexes->getMBBEndIdx(MBB); 1105 if (!(stop > lastIndex)) { 1106 report("Block ends before last instruction index", MBB); 1107 *OS << "Block ends at " << stop 1108 << " last instruction was at " << lastIndex << '\n'; 1109 } 1110 lastIndex = stop; 1111 } 1112} 1113 1114// Calculate the largest possible vregsPassed sets. These are the registers that 1115// can pass through an MBB live, but may not be live every time. It is assumed 1116// that all vregsPassed sets are empty before the call. 1117void MachineVerifier::calcRegsPassed() { 1118 // First push live-out regs to successors' vregsPassed. Remember the MBBs that 1119 // have any vregsPassed. 1120 SmallPtrSet<const MachineBasicBlock*, 8> todo; 1121 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1122 MFI != MFE; ++MFI) { 1123 const MachineBasicBlock &MBB(*MFI); 1124 BBInfo &MInfo = MBBInfoMap[&MBB]; 1125 if (!MInfo.reachable) 1126 continue; 1127 for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 1128 SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 1129 BBInfo &SInfo = MBBInfoMap[*SuI]; 1130 if (SInfo.addPassed(MInfo.regsLiveOut)) 1131 todo.insert(*SuI); 1132 } 1133 } 1134 1135 // Iteratively push vregsPassed to successors. This will converge to the same 1136 // final state regardless of DenseSet iteration order. 1137 while (!todo.empty()) { 1138 const MachineBasicBlock *MBB = *todo.begin(); 1139 todo.erase(MBB); 1140 BBInfo &MInfo = MBBInfoMap[MBB]; 1141 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 1142 SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 1143 if (*SuI == MBB) 1144 continue; 1145 BBInfo &SInfo = MBBInfoMap[*SuI]; 1146 if (SInfo.addPassed(MInfo.vregsPassed)) 1147 todo.insert(*SuI); 1148 } 1149 } 1150} 1151 1152// Calculate the set of virtual registers that must be passed through each basic 1153// block in order to satisfy the requirements of successor blocks. This is very 1154// similar to calcRegsPassed, only backwards. 1155void MachineVerifier::calcRegsRequired() { 1156 // First push live-in regs to predecessors' vregsRequired. 1157 SmallPtrSet<const MachineBasicBlock*, 8> todo; 1158 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1159 MFI != MFE; ++MFI) { 1160 const MachineBasicBlock &MBB(*MFI); 1161 BBInfo &MInfo = MBBInfoMap[&MBB]; 1162 for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(), 1163 PrE = MBB.pred_end(); PrI != PrE; ++PrI) { 1164 BBInfo &PInfo = MBBInfoMap[*PrI]; 1165 if (PInfo.addRequired(MInfo.vregsLiveIn)) 1166 todo.insert(*PrI); 1167 } 1168 } 1169 1170 // Iteratively push vregsRequired to predecessors. This will converge to the 1171 // same final state regardless of DenseSet iteration order. 1172 while (!todo.empty()) { 1173 const MachineBasicBlock *MBB = *todo.begin(); 1174 todo.erase(MBB); 1175 BBInfo &MInfo = MBBInfoMap[MBB]; 1176 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1177 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1178 if (*PrI == MBB) 1179 continue; 1180 BBInfo &SInfo = MBBInfoMap[*PrI]; 1181 if (SInfo.addRequired(MInfo.vregsRequired)) 1182 todo.insert(*PrI); 1183 } 1184 } 1185} 1186 1187// Check PHI instructions at the beginning of MBB. It is assumed that 1188// calcRegsPassed has been run so BBInfo::isLiveOut is valid. 1189void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) { 1190 SmallPtrSet<const MachineBasicBlock*, 8> seen; 1191 for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end(); 1192 BBI != BBE && BBI->isPHI(); ++BBI) { 1193 seen.clear(); 1194 1195 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 1196 unsigned Reg = BBI->getOperand(i).getReg(); 1197 const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB(); 1198 if (!Pre->isSuccessor(MBB)) 1199 continue; 1200 seen.insert(Pre); 1201 BBInfo &PrInfo = MBBInfoMap[Pre]; 1202 if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 1203 report("PHI operand is not live-out from predecessor", 1204 &BBI->getOperand(i), i); 1205 } 1206 1207 // Did we see all predecessors? 1208 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1209 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1210 if (!seen.count(*PrI)) { 1211 report("Missing PHI operand", BBI); 1212 *OS << "BB#" << (*PrI)->getNumber() 1213 << " is a predecessor according to the CFG.\n"; 1214 } 1215 } 1216 } 1217} 1218 1219void MachineVerifier::visitMachineFunctionAfter() { 1220 calcRegsPassed(); 1221 1222 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1223 MFI != MFE; ++MFI) { 1224 BBInfo &MInfo = MBBInfoMap[MFI]; 1225 1226 // Skip unreachable MBBs. 1227 if (!MInfo.reachable) 1228 continue; 1229 1230 checkPHIOps(MFI); 1231 } 1232 1233 // Now check liveness info if available 1234 calcRegsRequired(); 1235 1236 // Check for killed virtual registers that should be live out. 1237 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1238 MFI != MFE; ++MFI) { 1239 BBInfo &MInfo = MBBInfoMap[MFI]; 1240 for (RegSet::iterator 1241 I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1242 ++I) 1243 if (MInfo.regsKilled.count(*I)) { 1244 report("Virtual register killed in block, but needed live out.", MFI); 1245 *OS << "Virtual register " << PrintReg(*I) 1246 << " is used after the block.\n"; 1247 } 1248 } 1249 1250 if (!MF->empty()) { 1251 BBInfo &MInfo = MBBInfoMap[&MF->front()]; 1252 for (RegSet::iterator 1253 I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1254 ++I) 1255 report("Virtual register def doesn't dominate all uses.", 1256 MRI->getVRegDef(*I)); 1257 } 1258 1259 if (LiveVars) 1260 verifyLiveVariables(); 1261 if (LiveInts) 1262 verifyLiveIntervals(); 1263} 1264 1265void MachineVerifier::verifyLiveVariables() { 1266 assert(LiveVars && "Don't call verifyLiveVariables without LiveVars"); 1267 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1268 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1269 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1270 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 1271 MFI != MFE; ++MFI) { 1272 BBInfo &MInfo = MBBInfoMap[MFI]; 1273 1274 // Our vregsRequired should be identical to LiveVariables' AliveBlocks 1275 if (MInfo.vregsRequired.count(Reg)) { 1276 if (!VI.AliveBlocks.test(MFI->getNumber())) { 1277 report("LiveVariables: Block missing from AliveBlocks", MFI); 1278 *OS << "Virtual register " << PrintReg(Reg) 1279 << " must be live through the block.\n"; 1280 } 1281 } else { 1282 if (VI.AliveBlocks.test(MFI->getNumber())) { 1283 report("LiveVariables: Block should not be in AliveBlocks", MFI); 1284 *OS << "Virtual register " << PrintReg(Reg) 1285 << " is not needed live through the block.\n"; 1286 } 1287 } 1288 } 1289 } 1290} 1291 1292void MachineVerifier::verifyLiveIntervals() { 1293 assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts"); 1294 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1295 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1296 1297 // Spilling and splitting may leave unused registers around. Skip them. 1298 if (MRI->reg_nodbg_empty(Reg)) 1299 continue; 1300 1301 if (!LiveInts->hasInterval(Reg)) { 1302 report("Missing live interval for virtual register", MF); 1303 *OS << PrintReg(Reg, TRI) << " still has defs or uses\n"; 1304 continue; 1305 } 1306 1307 const LiveInterval &LI = LiveInts->getInterval(Reg); 1308 assert(Reg == LI.reg && "Invalid reg to interval mapping"); 1309 verifyLiveInterval(LI); 1310 } 1311 1312 // Verify all the cached regunit intervals. 1313 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 1314 if (const LiveInterval *LI = LiveInts->getCachedRegUnit(i)) 1315 verifyLiveInterval(*LI); 1316} 1317 1318void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI, 1319 VNInfo *VNI) { 1320 if (VNI->isUnused()) 1321 return; 1322 1323 const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def); 1324 1325 if (!DefVNI) { 1326 report("Valno not live at def and not marked unused", MF, LI); 1327 *OS << "Valno #" << VNI->id << '\n'; 1328 return; 1329 } 1330 1331 if (DefVNI != VNI) { 1332 report("Live range at def has different valno", MF, LI); 1333 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1334 << " where valno #" << DefVNI->id << " is live\n"; 1335 return; 1336 } 1337 1338 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); 1339 if (!MBB) { 1340 report("Invalid definition index", MF, LI); 1341 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1342 << " in " << LI << '\n'; 1343 return; 1344 } 1345 1346 if (VNI->isPHIDef()) { 1347 if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { 1348 report("PHIDef value is not defined at MBB start", MBB, LI); 1349 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def 1350 << ", not at the beginning of BB#" << MBB->getNumber() << '\n'; 1351 } 1352 return; 1353 } 1354 1355 // Non-PHI def. 1356 const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); 1357 if (!MI) { 1358 report("No instruction at def index", MBB, LI); 1359 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1360 return; 1361 } 1362 1363 bool hasDef = false; 1364 bool isEarlyClobber = false; 1365 for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1366 if (!MOI->isReg() || !MOI->isDef()) 1367 continue; 1368 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1369 if (MOI->getReg() != LI.reg) 1370 continue; 1371 } else { 1372 if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || 1373 !TRI->hasRegUnit(MOI->getReg(), LI.reg)) 1374 continue; 1375 } 1376 hasDef = true; 1377 if (MOI->isEarlyClobber()) 1378 isEarlyClobber = true; 1379 } 1380 1381 if (!hasDef) { 1382 report("Defining instruction does not modify register", MI); 1383 *OS << "Valno #" << VNI->id << " in " << LI << '\n'; 1384 } 1385 1386 // Early clobber defs begin at USE slots, but other defs must begin at 1387 // DEF slots. 1388 if (isEarlyClobber) { 1389 if (!VNI->def.isEarlyClobber()) { 1390 report("Early clobber def must be at an early-clobber slot", MBB, LI); 1391 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1392 } 1393 } else if (!VNI->def.isRegister()) { 1394 report("Non-PHI, non-early clobber def must be at a register slot", 1395 MBB, LI); 1396 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n'; 1397 } 1398} 1399 1400void 1401MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI, 1402 LiveInterval::const_iterator I) { 1403 const VNInfo *VNI = I->valno; 1404 assert(VNI && "Live range has no valno"); 1405 1406 if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) { 1407 report("Foreign valno in live range", MF, LI); 1408 *OS << *I << " has a bad valno\n"; 1409 } 1410 1411 if (VNI->isUnused()) { 1412 report("Live range valno is marked unused", MF, LI); 1413 *OS << *I << '\n'; 1414 } 1415 1416 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start); 1417 if (!MBB) { 1418 report("Bad start of live segment, no basic block", MF, LI); 1419 *OS << *I << '\n'; 1420 return; 1421 } 1422 SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB); 1423 if (I->start != MBBStartIdx && I->start != VNI->def) { 1424 report("Live segment must begin at MBB entry or valno def", MBB, LI); 1425 *OS << *I << '\n'; 1426 } 1427 1428 const MachineBasicBlock *EndMBB = 1429 LiveInts->getMBBFromIndex(I->end.getPrevSlot()); 1430 if (!EndMBB) { 1431 report("Bad end of live segment, no basic block", MF, LI); 1432 *OS << *I << '\n'; 1433 return; 1434 } 1435 1436 // No more checks for live-out segments. 1437 if (I->end == LiveInts->getMBBEndIdx(EndMBB)) 1438 return; 1439 1440 // RegUnit intervals are allowed dead phis. 1441 if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && VNI->isPHIDef() && 1442 I->start == VNI->def && I->end == VNI->def.getDeadSlot()) 1443 return; 1444 1445 // The live segment is ending inside EndMBB 1446 const MachineInstr *MI = 1447 LiveInts->getInstructionFromIndex(I->end.getPrevSlot()); 1448 if (!MI) { 1449 report("Live segment doesn't end at a valid instruction", EndMBB, LI); 1450 *OS << *I << '\n'; 1451 return; 1452 } 1453 1454 // The block slot must refer to a basic block boundary. 1455 if (I->end.isBlock()) { 1456 report("Live segment ends at B slot of an instruction", EndMBB, LI); 1457 *OS << *I << '\n'; 1458 } 1459 1460 if (I->end.isDead()) { 1461 // Segment ends on the dead slot. 1462 // That means there must be a dead def. 1463 if (!SlotIndex::isSameInstr(I->start, I->end)) { 1464 report("Live segment ending at dead slot spans instructions", EndMBB, LI); 1465 *OS << *I << '\n'; 1466 } 1467 } 1468 1469 // A live segment can only end at an early-clobber slot if it is being 1470 // redefined by an early-clobber def. 1471 if (I->end.isEarlyClobber()) { 1472 if (I+1 == LI.end() || (I+1)->start != I->end) { 1473 report("Live segment ending at early clobber slot must be " 1474 "redefined by an EC def in the same instruction", EndMBB, LI); 1475 *OS << *I << '\n'; 1476 } 1477 } 1478 1479 // The following checks only apply to virtual registers. Physreg liveness 1480 // is too weird to check. 1481 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1482 // A live range can end with either a redefinition, a kill flag on a 1483 // use, or a dead flag on a def. 1484 bool hasRead = false; 1485 bool hasDeadDef = false; 1486 for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) { 1487 if (!MOI->isReg() || MOI->getReg() != LI.reg) 1488 continue; 1489 if (MOI->readsReg()) 1490 hasRead = true; 1491 if (MOI->isDef() && MOI->isDead()) 1492 hasDeadDef = true; 1493 } 1494 1495 if (I->end.isDead()) { 1496 if (!hasDeadDef) { 1497 report("Instruction doesn't have a dead def operand", MI); 1498 I->print(*OS); 1499 *OS << " in " << LI << '\n'; 1500 } 1501 } else { 1502 if (!hasRead) { 1503 report("Instruction ending live range doesn't read the register", MI); 1504 *OS << *I << " in " << LI << '\n'; 1505 } 1506 } 1507 } 1508 1509 // Now check all the basic blocks in this live segment. 1510 MachineFunction::const_iterator MFI = MBB; 1511 // Is this live range the beginning of a non-PHIDef VN? 1512 if (I->start == VNI->def && !VNI->isPHIDef()) { 1513 // Not live-in to any blocks. 1514 if (MBB == EndMBB) 1515 return; 1516 // Skip this block. 1517 ++MFI; 1518 } 1519 for (;;) { 1520 assert(LiveInts->isLiveInToMBB(LI, MFI)); 1521 // We don't know how to track physregs into a landing pad. 1522 if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && 1523 MFI->isLandingPad()) { 1524 if (&*MFI == EndMBB) 1525 break; 1526 ++MFI; 1527 continue; 1528 } 1529 1530 // Is VNI a PHI-def in the current block? 1531 bool IsPHI = VNI->isPHIDef() && 1532 VNI->def == LiveInts->getMBBStartIdx(MFI); 1533 1534 // Check that VNI is live-out of all predecessors. 1535 for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(), 1536 PE = MFI->pred_end(); PI != PE; ++PI) { 1537 SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI); 1538 const VNInfo *PVNI = LI.getVNInfoBefore(PEnd); 1539 1540 // All predecessors must have a live-out value. 1541 if (!PVNI) { 1542 report("Register not marked live out of predecessor", *PI, LI); 1543 *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber() 1544 << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before " 1545 << PEnd << '\n'; 1546 continue; 1547 } 1548 1549 // Only PHI-defs can take different predecessor values. 1550 if (!IsPHI && PVNI != VNI) { 1551 report("Different value live out of predecessor", *PI, LI); 1552 *OS << "Valno #" << PVNI->id << " live out of BB#" 1553 << (*PI)->getNumber() << '@' << PEnd 1554 << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber() 1555 << '@' << LiveInts->getMBBStartIdx(MFI) << '\n'; 1556 } 1557 } 1558 if (&*MFI == EndMBB) 1559 break; 1560 ++MFI; 1561 } 1562} 1563 1564void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { 1565 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 1566 I!=E; ++I) 1567 verifyLiveIntervalValue(LI, *I); 1568 1569 for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) 1570 verifyLiveIntervalSegment(LI, I); 1571 1572 // Check the LI only has one connected component. 1573 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 1574 ConnectedVNInfoEqClasses ConEQ(*LiveInts); 1575 unsigned NumComp = ConEQ.Classify(&LI); 1576 if (NumComp > 1) { 1577 report("Multiple connected components in live interval", MF, LI); 1578 for (unsigned comp = 0; comp != NumComp; ++comp) { 1579 *OS << comp << ": valnos"; 1580 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), 1581 E = LI.vni_end(); I!=E; ++I) 1582 if (comp == ConEQ.getEqClass(*I)) 1583 *OS << ' ' << (*I)->id; 1584 *OS << '\n'; 1585 } 1586 } 1587 } 1588} 1589