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/CodeGen/Passes.h" 27 #include "llvm/ADT/DenseSet.h" 28 #include "llvm/ADT/DepthFirstIterator.h" 29 #include "llvm/ADT/SetOperations.h" 30 #include "llvm/ADT/SmallVector.h" 31 #include "llvm/Analysis/EHPersonalities.h" 32 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 33 #include "llvm/CodeGen/LiveStackAnalysis.h" 34 #include "llvm/CodeGen/LiveVariables.h" 35 #include "llvm/CodeGen/MachineFrameInfo.h" 36 #include "llvm/CodeGen/MachineFunctionPass.h" 37 #include "llvm/CodeGen/MachineMemOperand.h" 38 #include "llvm/CodeGen/MachineRegisterInfo.h" 39 #include "llvm/IR/BasicBlock.h" 40 #include "llvm/IR/InlineAsm.h" 41 #include "llvm/IR/Instructions.h" 42 #include "llvm/MC/MCAsmInfo.h" 43 #include "llvm/Support/Debug.h" 44 #include "llvm/Support/ErrorHandling.h" 45 #include "llvm/Support/FileSystem.h" 46 #include "llvm/Support/raw_ostream.h" 47 #include "llvm/Target/TargetInstrInfo.h" 48 #include "llvm/Target/TargetMachine.h" 49 #include "llvm/Target/TargetRegisterInfo.h" 50 #include "llvm/Target/TargetSubtargetInfo.h" 51 using namespace llvm; 52 53 namespace { 54 struct MachineVerifier { 55 56 MachineVerifier(Pass *pass, const char *b) : 57 PASS(pass), 58 Banner(b) 59 {} 60 61 unsigned verify(MachineFunction &MF); 62 63 Pass *const PASS; 64 const char *Banner; 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 template <typename T> void report(const char *msg, ilist_iterator<T> I) { 208 report(msg, &*I); 209 } 210 void report(const char *msg, const MachineFunction *MF); 211 void report(const char *msg, const MachineBasicBlock *MBB); 212 void report(const char *msg, const MachineInstr *MI); 213 void report(const char *msg, const MachineOperand *MO, unsigned MONum); 214 215 void report_context(const LiveInterval &LI) const; 216 void report_context(const LiveRange &LR, unsigned Reg, 217 LaneBitmask LaneMask) const; 218 void report_context(const LiveRange::Segment &S) const; 219 void report_context(const VNInfo &VNI) const; 220 void report_context(SlotIndex Pos) const; 221 void report_context_liverange(const LiveRange &LR) const; 222 void report_context_lanemask(LaneBitmask LaneMask) const; 223 void report_context_vreg(unsigned VReg) const; 224 void report_context_vreg_regunit(unsigned VRegOrRegUnit) const; 225 226 void verifyInlineAsm(const MachineInstr *MI); 227 228 void checkLiveness(const MachineOperand *MO, unsigned MONum); 229 void checkLivenessAtUse(const MachineOperand *MO, unsigned MONum, 230 SlotIndex UseIdx, const LiveRange &LR, unsigned Reg, 231 LaneBitmask LaneMask = 0); 232 void checkLivenessAtDef(const MachineOperand *MO, unsigned MONum, 233 SlotIndex DefIdx, const LiveRange &LR, unsigned Reg, 234 LaneBitmask LaneMask = 0); 235 236 void markReachable(const MachineBasicBlock *MBB); 237 void calcRegsPassed(); 238 void checkPHIOps(const MachineBasicBlock *MBB); 239 240 void calcRegsRequired(); 241 void verifyLiveVariables(); 242 void verifyLiveIntervals(); 243 void verifyLiveInterval(const LiveInterval&); 244 void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned, 245 unsigned); 246 void verifyLiveRangeSegment(const LiveRange&, 247 const LiveRange::const_iterator I, unsigned, 248 unsigned); 249 void verifyLiveRange(const LiveRange&, unsigned, LaneBitmask LaneMask = 0); 250 251 void verifyStackFrame(); 252 253 void verifySlotIndexes() const; 254 void verifyProperties(const MachineFunction &MF); 255 }; 256 257 struct MachineVerifierPass : public MachineFunctionPass { 258 static char ID; // Pass ID, replacement for typeid 259 const std::string Banner; 260 261 MachineVerifierPass(const std::string &banner = nullptr) 262 : MachineFunctionPass(ID), Banner(banner) { 263 initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry()); 264 } 265 266 void getAnalysisUsage(AnalysisUsage &AU) const override { 267 AU.setPreservesAll(); 268 MachineFunctionPass::getAnalysisUsage(AU); 269 } 270 271 bool runOnMachineFunction(MachineFunction &MF) override { 272 unsigned FoundErrors = MachineVerifier(this, Banner.c_str()).verify(MF); 273 if (FoundErrors) 274 report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors."); 275 return false; 276 } 277 }; 278 279 } 280 281 char MachineVerifierPass::ID = 0; 282 INITIALIZE_PASS(MachineVerifierPass, "machineverifier", 283 "Verify generated machine code", false, false) 284 285 FunctionPass *llvm::createMachineVerifierPass(const std::string &Banner) { 286 return new MachineVerifierPass(Banner); 287 } 288 289 bool MachineFunction::verify(Pass *p, const char *Banner, bool AbortOnErrors) 290 const { 291 MachineFunction &MF = const_cast<MachineFunction&>(*this); 292 unsigned FoundErrors = MachineVerifier(p, Banner).verify(MF); 293 if (AbortOnErrors && FoundErrors) 294 report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors."); 295 return FoundErrors == 0; 296 } 297 298 void MachineVerifier::verifySlotIndexes() const { 299 if (Indexes == nullptr) 300 return; 301 302 // Ensure the IdxMBB list is sorted by slot indexes. 303 SlotIndex Last; 304 for (SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(), 305 E = Indexes->MBBIndexEnd(); I != E; ++I) { 306 assert(!Last.isValid() || I->first > Last); 307 Last = I->first; 308 } 309 } 310 311 void MachineVerifier::verifyProperties(const MachineFunction &MF) { 312 // If a pass has introduced virtual registers without clearing the 313 // AllVRegsAllocated property (or set it without allocating the vregs) 314 // then report an error. 315 if (MF.getProperties().hasProperty( 316 MachineFunctionProperties::Property::AllVRegsAllocated) && 317 MRI->getNumVirtRegs()) { 318 report( 319 "Function has AllVRegsAllocated property but there are VReg operands", 320 &MF); 321 } 322 } 323 324 unsigned MachineVerifier::verify(MachineFunction &MF) { 325 foundErrors = 0; 326 327 this->MF = &MF; 328 TM = &MF.getTarget(); 329 TII = MF.getSubtarget().getInstrInfo(); 330 TRI = MF.getSubtarget().getRegisterInfo(); 331 MRI = &MF.getRegInfo(); 332 333 LiveVars = nullptr; 334 LiveInts = nullptr; 335 LiveStks = nullptr; 336 Indexes = nullptr; 337 if (PASS) { 338 LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>(); 339 // We don't want to verify LiveVariables if LiveIntervals is available. 340 if (!LiveInts) 341 LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>(); 342 LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>(); 343 Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>(); 344 } 345 346 verifySlotIndexes(); 347 348 verifyProperties(MF); 349 350 visitMachineFunctionBefore(); 351 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end(); 352 MFI!=MFE; ++MFI) { 353 visitMachineBasicBlockBefore(&*MFI); 354 // Keep track of the current bundle header. 355 const MachineInstr *CurBundle = nullptr; 356 // Do we expect the next instruction to be part of the same bundle? 357 bool InBundle = false; 358 359 for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(), 360 MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) { 361 if (MBBI->getParent() != &*MFI) { 362 report("Bad instruction parent pointer", MFI); 363 errs() << "Instruction: " << *MBBI; 364 continue; 365 } 366 367 // Check for consistent bundle flags. 368 if (InBundle && !MBBI->isBundledWithPred()) 369 report("Missing BundledPred flag, " 370 "BundledSucc was set on predecessor", 371 &*MBBI); 372 if (!InBundle && MBBI->isBundledWithPred()) 373 report("BundledPred flag is set, " 374 "but BundledSucc not set on predecessor", 375 &*MBBI); 376 377 // Is this a bundle header? 378 if (!MBBI->isInsideBundle()) { 379 if (CurBundle) 380 visitMachineBundleAfter(CurBundle); 381 CurBundle = &*MBBI; 382 visitMachineBundleBefore(CurBundle); 383 } else if (!CurBundle) 384 report("No bundle header", MBBI); 385 visitMachineInstrBefore(&*MBBI); 386 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) { 387 const MachineInstr &MI = *MBBI; 388 const MachineOperand &Op = MI.getOperand(I); 389 if (Op.getParent() != &MI) { 390 // Make sure to use correct addOperand / RemoveOperand / ChangeTo 391 // functions when replacing operands of a MachineInstr. 392 report("Instruction has operand with wrong parent set", &MI); 393 } 394 395 visitMachineOperand(&Op, I); 396 } 397 398 visitMachineInstrAfter(&*MBBI); 399 400 // Was this the last bundled instruction? 401 InBundle = MBBI->isBundledWithSucc(); 402 } 403 if (CurBundle) 404 visitMachineBundleAfter(CurBundle); 405 if (InBundle) 406 report("BundledSucc flag set on last instruction in block", &MFI->back()); 407 visitMachineBasicBlockAfter(&*MFI); 408 } 409 visitMachineFunctionAfter(); 410 411 // Clean up. 412 regsLive.clear(); 413 regsDefined.clear(); 414 regsDead.clear(); 415 regsKilled.clear(); 416 regMasks.clear(); 417 regsLiveInButUnused.clear(); 418 MBBInfoMap.clear(); 419 420 return foundErrors; 421 } 422 423 void MachineVerifier::report(const char *msg, const MachineFunction *MF) { 424 assert(MF); 425 errs() << '\n'; 426 if (!foundErrors++) { 427 if (Banner) 428 errs() << "# " << Banner << '\n'; 429 if (LiveInts != nullptr) 430 LiveInts->print(errs()); 431 else 432 MF->print(errs(), Indexes); 433 } 434 errs() << "*** Bad machine code: " << msg << " ***\n" 435 << "- function: " << MF->getName() << "\n"; 436 } 437 438 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) { 439 assert(MBB); 440 report(msg, MBB->getParent()); 441 errs() << "- basic block: BB#" << MBB->getNumber() 442 << ' ' << MBB->getName() 443 << " (" << (const void*)MBB << ')'; 444 if (Indexes) 445 errs() << " [" << Indexes->getMBBStartIdx(MBB) 446 << ';' << Indexes->getMBBEndIdx(MBB) << ')'; 447 errs() << '\n'; 448 } 449 450 void MachineVerifier::report(const char *msg, const MachineInstr *MI) { 451 assert(MI); 452 report(msg, MI->getParent()); 453 errs() << "- instruction: "; 454 if (Indexes && Indexes->hasIndex(*MI)) 455 errs() << Indexes->getInstructionIndex(*MI) << '\t'; 456 MI->print(errs(), /*SkipOpers=*/true); 457 errs() << '\n'; 458 } 459 460 void MachineVerifier::report(const char *msg, 461 const MachineOperand *MO, unsigned MONum) { 462 assert(MO); 463 report(msg, MO->getParent()); 464 errs() << "- operand " << MONum << ": "; 465 MO->print(errs(), TRI); 466 errs() << "\n"; 467 } 468 469 void MachineVerifier::report_context(SlotIndex Pos) const { 470 errs() << "- at: " << Pos << '\n'; 471 } 472 473 void MachineVerifier::report_context(const LiveInterval &LI) const { 474 errs() << "- interval: " << LI << '\n'; 475 } 476 477 void MachineVerifier::report_context(const LiveRange &LR, unsigned Reg, 478 LaneBitmask LaneMask) const { 479 report_context_liverange(LR); 480 errs() << "- register: " << PrintReg(Reg, TRI) << '\n'; 481 if (LaneMask != 0) 482 report_context_lanemask(LaneMask); 483 } 484 485 void MachineVerifier::report_context(const LiveRange::Segment &S) const { 486 errs() << "- segment: " << S << '\n'; 487 } 488 489 void MachineVerifier::report_context(const VNInfo &VNI) const { 490 errs() << "- ValNo: " << VNI.id << " (def " << VNI.def << ")\n"; 491 } 492 493 void MachineVerifier::report_context_liverange(const LiveRange &LR) const { 494 errs() << "- liverange: " << LR << '\n'; 495 } 496 497 void MachineVerifier::report_context_vreg(unsigned VReg) const { 498 errs() << "- v. register: " << PrintReg(VReg, TRI) << '\n'; 499 } 500 501 void MachineVerifier::report_context_vreg_regunit(unsigned VRegOrUnit) const { 502 if (TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) { 503 report_context_vreg(VRegOrUnit); 504 } else { 505 errs() << "- regunit: " << PrintRegUnit(VRegOrUnit, TRI) << '\n'; 506 } 507 } 508 509 void MachineVerifier::report_context_lanemask(LaneBitmask LaneMask) const { 510 errs() << "- lanemask: " << PrintLaneMask(LaneMask) << '\n'; 511 } 512 513 void MachineVerifier::markReachable(const MachineBasicBlock *MBB) { 514 BBInfo &MInfo = MBBInfoMap[MBB]; 515 if (!MInfo.reachable) { 516 MInfo.reachable = true; 517 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 518 SuE = MBB->succ_end(); SuI != SuE; ++SuI) 519 markReachable(*SuI); 520 } 521 } 522 523 void MachineVerifier::visitMachineFunctionBefore() { 524 lastIndex = SlotIndex(); 525 regsReserved = MRI->getReservedRegs(); 526 527 // A sub-register of a reserved register is also reserved 528 for (int Reg = regsReserved.find_first(); Reg>=0; 529 Reg = regsReserved.find_next(Reg)) { 530 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 531 // FIXME: This should probably be: 532 // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register"); 533 regsReserved.set(*SubRegs); 534 } 535 } 536 537 markReachable(&MF->front()); 538 539 // Build a set of the basic blocks in the function. 540 FunctionBlocks.clear(); 541 for (const auto &MBB : *MF) { 542 FunctionBlocks.insert(&MBB); 543 BBInfo &MInfo = MBBInfoMap[&MBB]; 544 545 MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end()); 546 if (MInfo.Preds.size() != MBB.pred_size()) 547 report("MBB has duplicate entries in its predecessor list.", &MBB); 548 549 MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end()); 550 if (MInfo.Succs.size() != MBB.succ_size()) 551 report("MBB has duplicate entries in its successor list.", &MBB); 552 } 553 554 // Check that the register use lists are sane. 555 MRI->verifyUseLists(); 556 557 verifyStackFrame(); 558 } 559 560 // Does iterator point to a and b as the first two elements? 561 static bool matchPair(MachineBasicBlock::const_succ_iterator i, 562 const MachineBasicBlock *a, const MachineBasicBlock *b) { 563 if (*i == a) 564 return *++i == b; 565 if (*i == b) 566 return *++i == a; 567 return false; 568 } 569 570 void 571 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) { 572 FirstTerminator = nullptr; 573 574 if (MRI->isSSA()) { 575 // If this block has allocatable physical registers live-in, check that 576 // it is an entry block or landing pad. 577 for (const auto &LI : MBB->liveins()) { 578 if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() && 579 MBB->getIterator() != MBB->getParent()->begin()) { 580 report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB); 581 } 582 } 583 } 584 585 // Count the number of landing pad successors. 586 SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs; 587 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 588 E = MBB->succ_end(); I != E; ++I) { 589 if ((*I)->isEHPad()) 590 LandingPadSuccs.insert(*I); 591 if (!FunctionBlocks.count(*I)) 592 report("MBB has successor that isn't part of the function.", MBB); 593 if (!MBBInfoMap[*I].Preds.count(MBB)) { 594 report("Inconsistent CFG", MBB); 595 errs() << "MBB is not in the predecessor list of the successor BB#" 596 << (*I)->getNumber() << ".\n"; 597 } 598 } 599 600 // Check the predecessor list. 601 for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 602 E = MBB->pred_end(); I != E; ++I) { 603 if (!FunctionBlocks.count(*I)) 604 report("MBB has predecessor that isn't part of the function.", MBB); 605 if (!MBBInfoMap[*I].Succs.count(MBB)) { 606 report("Inconsistent CFG", MBB); 607 errs() << "MBB is not in the successor list of the predecessor BB#" 608 << (*I)->getNumber() << ".\n"; 609 } 610 } 611 612 const MCAsmInfo *AsmInfo = TM->getMCAsmInfo(); 613 const BasicBlock *BB = MBB->getBasicBlock(); 614 const Function *Fn = MF->getFunction(); 615 if (LandingPadSuccs.size() > 1 && 616 !(AsmInfo && 617 AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj && 618 BB && isa<SwitchInst>(BB->getTerminator())) && 619 !isFuncletEHPersonality(classifyEHPersonality(Fn->getPersonalityFn()))) 620 report("MBB has more than one landing pad successor", MBB); 621 622 // Call AnalyzeBranch. If it succeeds, there several more conditions to check. 623 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 624 SmallVector<MachineOperand, 4> Cond; 625 if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB, 626 Cond)) { 627 // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's 628 // check whether its answers match up with reality. 629 if (!TBB && !FBB) { 630 // Block falls through to its successor. 631 MachineFunction::const_iterator MBBI = MBB->getIterator(); 632 ++MBBI; 633 if (MBBI == MF->end()) { 634 // It's possible that the block legitimately ends with a noreturn 635 // call or an unreachable, in which case it won't actually fall 636 // out the bottom of the function. 637 } else if (MBB->succ_size() == LandingPadSuccs.size()) { 638 // It's possible that the block legitimately ends with a noreturn 639 // call or an unreachable, in which case it won't actuall fall 640 // out of the block. 641 } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) { 642 report("MBB exits via unconditional fall-through but doesn't have " 643 "exactly one CFG successor!", MBB); 644 } else if (!MBB->isSuccessor(&*MBBI)) { 645 report("MBB exits via unconditional fall-through but its successor " 646 "differs from its CFG successor!", MBB); 647 } 648 if (!MBB->empty() && MBB->back().isBarrier() && 649 !TII->isPredicated(MBB->back())) { 650 report("MBB exits via unconditional fall-through but ends with a " 651 "barrier instruction!", MBB); 652 } 653 if (!Cond.empty()) { 654 report("MBB exits via unconditional fall-through but has a condition!", 655 MBB); 656 } 657 } else if (TBB && !FBB && Cond.empty()) { 658 // Block unconditionally branches somewhere. 659 // If the block has exactly one successor, that happens to be a 660 // landingpad, accept it as valid control flow. 661 if (MBB->succ_size() != 1+LandingPadSuccs.size() && 662 (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 || 663 *MBB->succ_begin() != *LandingPadSuccs.begin())) { 664 report("MBB exits via unconditional branch but doesn't have " 665 "exactly one CFG successor!", MBB); 666 } else if (!MBB->isSuccessor(TBB)) { 667 report("MBB exits via unconditional branch but the CFG " 668 "successor doesn't match the actual successor!", MBB); 669 } 670 if (MBB->empty()) { 671 report("MBB exits via unconditional branch but doesn't contain " 672 "any instructions!", MBB); 673 } else if (!MBB->back().isBarrier()) { 674 report("MBB exits via unconditional branch but doesn't end with a " 675 "barrier instruction!", MBB); 676 } else if (!MBB->back().isTerminator()) { 677 report("MBB exits via unconditional branch but the branch isn't a " 678 "terminator instruction!", MBB); 679 } 680 } else if (TBB && !FBB && !Cond.empty()) { 681 // Block conditionally branches somewhere, otherwise falls through. 682 MachineFunction::const_iterator MBBI = MBB->getIterator(); 683 ++MBBI; 684 if (MBBI == MF->end()) { 685 report("MBB conditionally falls through out of function!", MBB); 686 } else if (MBB->succ_size() == 1) { 687 // A conditional branch with only one successor is weird, but allowed. 688 if (&*MBBI != TBB) 689 report("MBB exits via conditional branch/fall-through but only has " 690 "one CFG successor!", MBB); 691 else if (TBB != *MBB->succ_begin()) 692 report("MBB exits via conditional branch/fall-through but the CFG " 693 "successor don't match the actual successor!", MBB); 694 } else if (MBB->succ_size() != 2) { 695 report("MBB exits via conditional branch/fall-through but doesn't have " 696 "exactly two CFG successors!", MBB); 697 } else if (!matchPair(MBB->succ_begin(), TBB, &*MBBI)) { 698 report("MBB exits via conditional branch/fall-through but the CFG " 699 "successors don't match the actual successors!", MBB); 700 } 701 if (MBB->empty()) { 702 report("MBB exits via conditional branch/fall-through but doesn't " 703 "contain any instructions!", MBB); 704 } else if (MBB->back().isBarrier()) { 705 report("MBB exits via conditional branch/fall-through but ends with a " 706 "barrier instruction!", MBB); 707 } else if (!MBB->back().isTerminator()) { 708 report("MBB exits via conditional branch/fall-through but the branch " 709 "isn't a terminator instruction!", MBB); 710 } 711 } else if (TBB && FBB) { 712 // Block conditionally branches somewhere, otherwise branches 713 // somewhere else. 714 if (MBB->succ_size() == 1) { 715 // A conditional branch with only one successor is weird, but allowed. 716 if (FBB != TBB) 717 report("MBB exits via conditional branch/branch through but only has " 718 "one CFG successor!", MBB); 719 else if (TBB != *MBB->succ_begin()) 720 report("MBB exits via conditional branch/branch through but the CFG " 721 "successor don't match the actual successor!", MBB); 722 } else if (MBB->succ_size() != 2) { 723 report("MBB exits via conditional branch/branch but doesn't have " 724 "exactly two CFG successors!", MBB); 725 } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) { 726 report("MBB exits via conditional branch/branch but the CFG " 727 "successors don't match the actual successors!", MBB); 728 } 729 if (MBB->empty()) { 730 report("MBB exits via conditional branch/branch but doesn't " 731 "contain any instructions!", MBB); 732 } else if (!MBB->back().isBarrier()) { 733 report("MBB exits via conditional branch/branch but doesn't end with a " 734 "barrier instruction!", MBB); 735 } else if (!MBB->back().isTerminator()) { 736 report("MBB exits via conditional branch/branch but the branch " 737 "isn't a terminator instruction!", MBB); 738 } 739 if (Cond.empty()) { 740 report("MBB exits via conditinal branch/branch but there's no " 741 "condition!", MBB); 742 } 743 } else { 744 report("AnalyzeBranch returned invalid data!", MBB); 745 } 746 } 747 748 regsLive.clear(); 749 for (const auto &LI : MBB->liveins()) { 750 if (!TargetRegisterInfo::isPhysicalRegister(LI.PhysReg)) { 751 report("MBB live-in list contains non-physical register", MBB); 752 continue; 753 } 754 for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true); 755 SubRegs.isValid(); ++SubRegs) 756 regsLive.insert(*SubRegs); 757 } 758 regsLiveInButUnused = regsLive; 759 760 const MachineFrameInfo *MFI = MF->getFrameInfo(); 761 assert(MFI && "Function has no frame info"); 762 BitVector PR = MFI->getPristineRegs(*MF); 763 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { 764 for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true); 765 SubRegs.isValid(); ++SubRegs) 766 regsLive.insert(*SubRegs); 767 } 768 769 regsKilled.clear(); 770 regsDefined.clear(); 771 772 if (Indexes) 773 lastIndex = Indexes->getMBBStartIdx(MBB); 774 } 775 776 // This function gets called for all bundle headers, including normal 777 // stand-alone unbundled instructions. 778 void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) { 779 if (Indexes && Indexes->hasIndex(*MI)) { 780 SlotIndex idx = Indexes->getInstructionIndex(*MI); 781 if (!(idx > lastIndex)) { 782 report("Instruction index out of order", MI); 783 errs() << "Last instruction was at " << lastIndex << '\n'; 784 } 785 lastIndex = idx; 786 } 787 788 // Ensure non-terminators don't follow terminators. 789 // Ignore predicated terminators formed by if conversion. 790 // FIXME: If conversion shouldn't need to violate this rule. 791 if (MI->isTerminator() && !TII->isPredicated(*MI)) { 792 if (!FirstTerminator) 793 FirstTerminator = MI; 794 } else if (FirstTerminator) { 795 report("Non-terminator instruction after the first terminator", MI); 796 errs() << "First terminator was:\t" << *FirstTerminator; 797 } 798 } 799 800 // The operands on an INLINEASM instruction must follow a template. 801 // Verify that the flag operands make sense. 802 void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) { 803 // The first two operands on INLINEASM are the asm string and global flags. 804 if (MI->getNumOperands() < 2) { 805 report("Too few operands on inline asm", MI); 806 return; 807 } 808 if (!MI->getOperand(0).isSymbol()) 809 report("Asm string must be an external symbol", MI); 810 if (!MI->getOperand(1).isImm()) 811 report("Asm flags must be an immediate", MI); 812 // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2, 813 // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16, 814 // and Extra_IsConvergent = 32. 815 if (!isUInt<6>(MI->getOperand(1).getImm())) 816 report("Unknown asm flags", &MI->getOperand(1), 1); 817 818 static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed"); 819 820 unsigned OpNo = InlineAsm::MIOp_FirstOperand; 821 unsigned NumOps; 822 for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) { 823 const MachineOperand &MO = MI->getOperand(OpNo); 824 // There may be implicit ops after the fixed operands. 825 if (!MO.isImm()) 826 break; 827 NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm()); 828 } 829 830 if (OpNo > MI->getNumOperands()) 831 report("Missing operands in last group", MI); 832 833 // An optional MDNode follows the groups. 834 if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata()) 835 ++OpNo; 836 837 // All trailing operands must be implicit registers. 838 for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) { 839 const MachineOperand &MO = MI->getOperand(OpNo); 840 if (!MO.isReg() || !MO.isImplicit()) 841 report("Expected implicit register after groups", &MO, OpNo); 842 } 843 } 844 845 void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) { 846 const MCInstrDesc &MCID = MI->getDesc(); 847 if (MI->getNumOperands() < MCID.getNumOperands()) { 848 report("Too few operands", MI); 849 errs() << MCID.getNumOperands() << " operands expected, but " 850 << MI->getNumOperands() << " given.\n"; 851 } 852 853 // Check the tied operands. 854 if (MI->isInlineAsm()) 855 verifyInlineAsm(MI); 856 857 // Check the MachineMemOperands for basic consistency. 858 for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 859 E = MI->memoperands_end(); I != E; ++I) { 860 if ((*I)->isLoad() && !MI->mayLoad()) 861 report("Missing mayLoad flag", MI); 862 if ((*I)->isStore() && !MI->mayStore()) 863 report("Missing mayStore flag", MI); 864 } 865 866 // Debug values must not have a slot index. 867 // Other instructions must have one, unless they are inside a bundle. 868 if (LiveInts) { 869 bool mapped = !LiveInts->isNotInMIMap(*MI); 870 if (MI->isDebugValue()) { 871 if (mapped) 872 report("Debug instruction has a slot index", MI); 873 } else if (MI->isInsideBundle()) { 874 if (mapped) 875 report("Instruction inside bundle has a slot index", MI); 876 } else { 877 if (!mapped) 878 report("Missing slot index", MI); 879 } 880 } 881 882 StringRef ErrorInfo; 883 if (!TII->verifyInstruction(*MI, ErrorInfo)) 884 report(ErrorInfo.data(), MI); 885 } 886 887 void 888 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) { 889 const MachineInstr *MI = MO->getParent(); 890 const MCInstrDesc &MCID = MI->getDesc(); 891 unsigned NumDefs = MCID.getNumDefs(); 892 if (MCID.getOpcode() == TargetOpcode::PATCHPOINT) 893 NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0; 894 895 // The first MCID.NumDefs operands must be explicit register defines 896 if (MONum < NumDefs) { 897 const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 898 if (!MO->isReg()) 899 report("Explicit definition must be a register", MO, MONum); 900 else if (!MO->isDef() && !MCOI.isOptionalDef()) 901 report("Explicit definition marked as use", MO, MONum); 902 else if (MO->isImplicit()) 903 report("Explicit definition marked as implicit", MO, MONum); 904 } else if (MONum < MCID.getNumOperands()) { 905 const MCOperandInfo &MCOI = MCID.OpInfo[MONum]; 906 // Don't check if it's the last operand in a variadic instruction. See, 907 // e.g., LDM_RET in the arm back end. 908 if (MO->isReg() && 909 !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) { 910 if (MO->isDef() && !MCOI.isOptionalDef()) 911 report("Explicit operand marked as def", MO, MONum); 912 if (MO->isImplicit()) 913 report("Explicit operand marked as implicit", MO, MONum); 914 } 915 916 int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO); 917 if (TiedTo != -1) { 918 if (!MO->isReg()) 919 report("Tied use must be a register", MO, MONum); 920 else if (!MO->isTied()) 921 report("Operand should be tied", MO, MONum); 922 else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum)) 923 report("Tied def doesn't match MCInstrDesc", MO, MONum); 924 } else if (MO->isReg() && MO->isTied()) 925 report("Explicit operand should not be tied", MO, MONum); 926 } else { 927 // ARM adds %reg0 operands to indicate predicates. We'll allow that. 928 if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg()) 929 report("Extra explicit operand on non-variadic instruction", MO, MONum); 930 } 931 932 switch (MO->getType()) { 933 case MachineOperand::MO_Register: { 934 const unsigned Reg = MO->getReg(); 935 if (!Reg) 936 return; 937 if (MRI->tracksLiveness() && !MI->isDebugValue()) 938 checkLiveness(MO, MONum); 939 940 // Verify the consistency of tied operands. 941 if (MO->isTied()) { 942 unsigned OtherIdx = MI->findTiedOperandIdx(MONum); 943 const MachineOperand &OtherMO = MI->getOperand(OtherIdx); 944 if (!OtherMO.isReg()) 945 report("Must be tied to a register", MO, MONum); 946 if (!OtherMO.isTied()) 947 report("Missing tie flags on tied operand", MO, MONum); 948 if (MI->findTiedOperandIdx(OtherIdx) != MONum) 949 report("Inconsistent tie links", MO, MONum); 950 if (MONum < MCID.getNumDefs()) { 951 if (OtherIdx < MCID.getNumOperands()) { 952 if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO)) 953 report("Explicit def tied to explicit use without tie constraint", 954 MO, MONum); 955 } else { 956 if (!OtherMO.isImplicit()) 957 report("Explicit def should be tied to implicit use", MO, MONum); 958 } 959 } 960 } 961 962 // Verify two-address constraints after leaving SSA form. 963 unsigned DefIdx; 964 if (!MRI->isSSA() && MO->isUse() && 965 MI->isRegTiedToDefOperand(MONum, &DefIdx) && 966 Reg != MI->getOperand(DefIdx).getReg()) 967 report("Two-address instruction operands must be identical", MO, MONum); 968 969 // Check register classes. 970 if (MONum < MCID.getNumOperands() && !MO->isImplicit()) { 971 unsigned SubIdx = MO->getSubReg(); 972 973 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 974 if (SubIdx) { 975 report("Illegal subregister index for physical register", MO, MONum); 976 return; 977 } 978 if (const TargetRegisterClass *DRC = 979 TII->getRegClass(MCID, MONum, TRI, *MF)) { 980 if (!DRC->contains(Reg)) { 981 report("Illegal physical register for instruction", MO, MONum); 982 errs() << TRI->getName(Reg) << " is not a " 983 << TRI->getRegClassName(DRC) << " register.\n"; 984 } 985 } 986 } else { 987 // Virtual register. 988 const TargetRegisterClass *RC = MRI->getRegClassOrNull(Reg); 989 if (!RC) { 990 // This is a generic virtual register. 991 // It must have a size and it must not have a SubIdx. 992 unsigned Size = MRI->getSize(Reg); 993 if (!Size) { 994 report("Generic virtual register must have a size", MO, MONum); 995 return; 996 } 997 // Make sure the register fits into its register bank if any. 998 const RegisterBank *RegBank = MRI->getRegBankOrNull(Reg); 999 if (RegBank && RegBank->getSize() < Size) { 1000 report("Register bank is too small for virtual register", MO, 1001 MONum); 1002 errs() << "Register bank " << RegBank->getName() << " too small(" 1003 << RegBank->getSize() << ") to fit " << Size << "-bits\n"; 1004 return; 1005 } 1006 if (SubIdx) { 1007 report("Generic virtual register does not subregister index", MO, MONum); 1008 return; 1009 } 1010 break; 1011 } 1012 if (SubIdx) { 1013 const TargetRegisterClass *SRC = 1014 TRI->getSubClassWithSubReg(RC, SubIdx); 1015 if (!SRC) { 1016 report("Invalid subregister index for virtual register", MO, MONum); 1017 errs() << "Register class " << TRI->getRegClassName(RC) 1018 << " does not support subreg index " << SubIdx << "\n"; 1019 return; 1020 } 1021 if (RC != SRC) { 1022 report("Invalid register class for subregister index", MO, MONum); 1023 errs() << "Register class " << TRI->getRegClassName(RC) 1024 << " does not fully support subreg index " << SubIdx << "\n"; 1025 return; 1026 } 1027 } 1028 if (const TargetRegisterClass *DRC = 1029 TII->getRegClass(MCID, MONum, TRI, *MF)) { 1030 if (SubIdx) { 1031 const TargetRegisterClass *SuperRC = 1032 TRI->getLargestLegalSuperClass(RC, *MF); 1033 if (!SuperRC) { 1034 report("No largest legal super class exists.", MO, MONum); 1035 return; 1036 } 1037 DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx); 1038 if (!DRC) { 1039 report("No matching super-reg register class.", MO, MONum); 1040 return; 1041 } 1042 } 1043 if (!RC->hasSuperClassEq(DRC)) { 1044 report("Illegal virtual register for instruction", MO, MONum); 1045 errs() << "Expected a " << TRI->getRegClassName(DRC) 1046 << " register, but got a " << TRI->getRegClassName(RC) 1047 << " register\n"; 1048 } 1049 } 1050 } 1051 } 1052 break; 1053 } 1054 1055 case MachineOperand::MO_RegisterMask: 1056 regMasks.push_back(MO->getRegMask()); 1057 break; 1058 1059 case MachineOperand::MO_MachineBasicBlock: 1060 if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent())) 1061 report("PHI operand is not in the CFG", MO, MONum); 1062 break; 1063 1064 case MachineOperand::MO_FrameIndex: 1065 if (LiveStks && LiveStks->hasInterval(MO->getIndex()) && 1066 LiveInts && !LiveInts->isNotInMIMap(*MI)) { 1067 int FI = MO->getIndex(); 1068 LiveInterval &LI = LiveStks->getInterval(FI); 1069 SlotIndex Idx = LiveInts->getInstructionIndex(*MI); 1070 1071 bool stores = MI->mayStore(); 1072 bool loads = MI->mayLoad(); 1073 // For a memory-to-memory move, we need to check if the frame 1074 // index is used for storing or loading, by inspecting the 1075 // memory operands. 1076 if (stores && loads) { 1077 for (auto *MMO : MI->memoperands()) { 1078 const PseudoSourceValue *PSV = MMO->getPseudoValue(); 1079 if (PSV == nullptr) continue; 1080 const FixedStackPseudoSourceValue *Value = 1081 dyn_cast<FixedStackPseudoSourceValue>(PSV); 1082 if (Value == nullptr) continue; 1083 if (Value->getFrameIndex() != FI) continue; 1084 1085 if (MMO->isStore()) 1086 loads = false; 1087 else 1088 stores = false; 1089 break; 1090 } 1091 if (loads == stores) 1092 report("Missing fixed stack memoperand.", MI); 1093 } 1094 if (loads && !LI.liveAt(Idx.getRegSlot(true))) { 1095 report("Instruction loads from dead spill slot", MO, MONum); 1096 errs() << "Live stack: " << LI << '\n'; 1097 } 1098 if (stores && !LI.liveAt(Idx.getRegSlot())) { 1099 report("Instruction stores to dead spill slot", MO, MONum); 1100 errs() << "Live stack: " << LI << '\n'; 1101 } 1102 } 1103 break; 1104 1105 default: 1106 break; 1107 } 1108 } 1109 1110 void MachineVerifier::checkLivenessAtUse(const MachineOperand *MO, 1111 unsigned MONum, SlotIndex UseIdx, const LiveRange &LR, unsigned VRegOrUnit, 1112 LaneBitmask LaneMask) { 1113 LiveQueryResult LRQ = LR.Query(UseIdx); 1114 // Check if we have a segment at the use, note however that we only need one 1115 // live subregister range, the others may be dead. 1116 if (!LRQ.valueIn() && LaneMask == 0) { 1117 report("No live segment at use", MO, MONum); 1118 report_context_liverange(LR); 1119 report_context_vreg_regunit(VRegOrUnit); 1120 report_context(UseIdx); 1121 } 1122 if (MO->isKill() && !LRQ.isKill()) { 1123 report("Live range continues after kill flag", MO, MONum); 1124 report_context_liverange(LR); 1125 report_context_vreg_regunit(VRegOrUnit); 1126 if (LaneMask != 0) 1127 report_context_lanemask(LaneMask); 1128 report_context(UseIdx); 1129 } 1130 } 1131 1132 void MachineVerifier::checkLivenessAtDef(const MachineOperand *MO, 1133 unsigned MONum, SlotIndex DefIdx, const LiveRange &LR, unsigned VRegOrUnit, 1134 LaneBitmask LaneMask) { 1135 if (const VNInfo *VNI = LR.getVNInfoAt(DefIdx)) { 1136 assert(VNI && "NULL valno is not allowed"); 1137 if (VNI->def != DefIdx) { 1138 report("Inconsistent valno->def", MO, MONum); 1139 report_context_liverange(LR); 1140 report_context_vreg_regunit(VRegOrUnit); 1141 if (LaneMask != 0) 1142 report_context_lanemask(LaneMask); 1143 report_context(*VNI); 1144 report_context(DefIdx); 1145 } 1146 } else { 1147 report("No live segment at def", MO, MONum); 1148 report_context_liverange(LR); 1149 report_context_vreg_regunit(VRegOrUnit); 1150 if (LaneMask != 0) 1151 report_context_lanemask(LaneMask); 1152 report_context(DefIdx); 1153 } 1154 // Check that, if the dead def flag is present, LiveInts agree. 1155 if (MO->isDead()) { 1156 LiveQueryResult LRQ = LR.Query(DefIdx); 1157 if (!LRQ.isDeadDef()) { 1158 // In case of physregs we can have a non-dead definition on another 1159 // operand. 1160 bool otherDef = false; 1161 if (!TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) { 1162 const MachineInstr &MI = *MO->getParent(); 1163 for (const MachineOperand &MO : MI.operands()) { 1164 if (!MO.isReg() || !MO.isDef() || MO.isDead()) 1165 continue; 1166 unsigned Reg = MO.getReg(); 1167 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 1168 if (*Units == VRegOrUnit) { 1169 otherDef = true; 1170 break; 1171 } 1172 } 1173 } 1174 } 1175 1176 if (!otherDef) { 1177 report("Live range continues after dead def flag", MO, MONum); 1178 report_context_liverange(LR); 1179 report_context_vreg_regunit(VRegOrUnit); 1180 if (LaneMask != 0) 1181 report_context_lanemask(LaneMask); 1182 } 1183 } 1184 } 1185 } 1186 1187 void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) { 1188 const MachineInstr *MI = MO->getParent(); 1189 const unsigned Reg = MO->getReg(); 1190 1191 // Both use and def operands can read a register. 1192 if (MO->readsReg()) { 1193 regsLiveInButUnused.erase(Reg); 1194 1195 if (MO->isKill()) 1196 addRegWithSubRegs(regsKilled, Reg); 1197 1198 // Check that LiveVars knows this kill. 1199 if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) && 1200 MO->isKill()) { 1201 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1202 if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end()) 1203 report("Kill missing from LiveVariables", MO, MONum); 1204 } 1205 1206 // Check LiveInts liveness and kill. 1207 if (LiveInts && !LiveInts->isNotInMIMap(*MI)) { 1208 SlotIndex UseIdx = LiveInts->getInstructionIndex(*MI); 1209 // Check the cached regunit intervals. 1210 if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) { 1211 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 1212 if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units)) 1213 checkLivenessAtUse(MO, MONum, UseIdx, *LR, *Units); 1214 } 1215 } 1216 1217 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1218 if (LiveInts->hasInterval(Reg)) { 1219 // This is a virtual register interval. 1220 const LiveInterval &LI = LiveInts->getInterval(Reg); 1221 checkLivenessAtUse(MO, MONum, UseIdx, LI, Reg); 1222 1223 if (LI.hasSubRanges() && !MO->isDef()) { 1224 unsigned SubRegIdx = MO->getSubReg(); 1225 LaneBitmask MOMask = SubRegIdx != 0 1226 ? TRI->getSubRegIndexLaneMask(SubRegIdx) 1227 : MRI->getMaxLaneMaskForVReg(Reg); 1228 LaneBitmask LiveInMask = 0; 1229 for (const LiveInterval::SubRange &SR : LI.subranges()) { 1230 if ((MOMask & SR.LaneMask) == 0) 1231 continue; 1232 checkLivenessAtUse(MO, MONum, UseIdx, SR, Reg, SR.LaneMask); 1233 LiveQueryResult LRQ = SR.Query(UseIdx); 1234 if (LRQ.valueIn()) 1235 LiveInMask |= SR.LaneMask; 1236 } 1237 // At least parts of the register has to be live at the use. 1238 if ((LiveInMask & MOMask) == 0) { 1239 report("No live subrange at use", MO, MONum); 1240 report_context(LI); 1241 report_context(UseIdx); 1242 } 1243 } 1244 } else { 1245 report("Virtual register has no live interval", MO, MONum); 1246 } 1247 } 1248 } 1249 1250 // Use of a dead register. 1251 if (!regsLive.count(Reg)) { 1252 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 1253 // Reserved registers may be used even when 'dead'. 1254 bool Bad = !isReserved(Reg); 1255 // We are fine if just any subregister has a defined value. 1256 if (Bad) { 1257 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 1258 ++SubRegs) { 1259 if (regsLive.count(*SubRegs)) { 1260 Bad = false; 1261 break; 1262 } 1263 } 1264 } 1265 // If there is an additional implicit-use of a super register we stop 1266 // here. By definition we are fine if the super register is not 1267 // (completely) dead, if the complete super register is dead we will 1268 // get a report for its operand. 1269 if (Bad) { 1270 for (const MachineOperand &MOP : MI->uses()) { 1271 if (!MOP.isReg()) 1272 continue; 1273 if (!MOP.isImplicit()) 1274 continue; 1275 for (MCSubRegIterator SubRegs(MOP.getReg(), TRI); SubRegs.isValid(); 1276 ++SubRegs) { 1277 if (*SubRegs == Reg) { 1278 Bad = false; 1279 break; 1280 } 1281 } 1282 } 1283 } 1284 if (Bad) 1285 report("Using an undefined physical register", MO, MONum); 1286 } else if (MRI->def_empty(Reg)) { 1287 report("Reading virtual register without a def", MO, MONum); 1288 } else { 1289 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1290 // We don't know which virtual registers are live in, so only complain 1291 // if vreg was killed in this MBB. Otherwise keep track of vregs that 1292 // must be live in. PHI instructions are handled separately. 1293 if (MInfo.regsKilled.count(Reg)) 1294 report("Using a killed virtual register", MO, MONum); 1295 else if (!MI->isPHI()) 1296 MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); 1297 } 1298 } 1299 } 1300 1301 if (MO->isDef()) { 1302 // Register defined. 1303 // TODO: verify that earlyclobber ops are not used. 1304 if (MO->isDead()) 1305 addRegWithSubRegs(regsDead, Reg); 1306 else 1307 addRegWithSubRegs(regsDefined, Reg); 1308 1309 // Verify SSA form. 1310 if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) && 1311 std::next(MRI->def_begin(Reg)) != MRI->def_end()) 1312 report("Multiple virtual register defs in SSA form", MO, MONum); 1313 1314 // Check LiveInts for a live segment, but only for virtual registers. 1315 if (LiveInts && !LiveInts->isNotInMIMap(*MI)) { 1316 SlotIndex DefIdx = LiveInts->getInstructionIndex(*MI); 1317 DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber()); 1318 1319 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1320 if (LiveInts->hasInterval(Reg)) { 1321 const LiveInterval &LI = LiveInts->getInterval(Reg); 1322 checkLivenessAtDef(MO, MONum, DefIdx, LI, Reg); 1323 1324 if (LI.hasSubRanges()) { 1325 unsigned SubRegIdx = MO->getSubReg(); 1326 LaneBitmask MOMask = SubRegIdx != 0 1327 ? TRI->getSubRegIndexLaneMask(SubRegIdx) 1328 : MRI->getMaxLaneMaskForVReg(Reg); 1329 for (const LiveInterval::SubRange &SR : LI.subranges()) { 1330 if ((SR.LaneMask & MOMask) == 0) 1331 continue; 1332 checkLivenessAtDef(MO, MONum, DefIdx, SR, Reg, SR.LaneMask); 1333 } 1334 } 1335 } else { 1336 report("Virtual register has no Live interval", MO, MONum); 1337 } 1338 } 1339 } 1340 } 1341 } 1342 1343 void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) { 1344 } 1345 1346 // This function gets called after visiting all instructions in a bundle. The 1347 // argument points to the bundle header. 1348 // Normal stand-alone instructions are also considered 'bundles', and this 1349 // function is called for all of them. 1350 void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) { 1351 BBInfo &MInfo = MBBInfoMap[MI->getParent()]; 1352 set_union(MInfo.regsKilled, regsKilled); 1353 set_subtract(regsLive, regsKilled); regsKilled.clear(); 1354 // Kill any masked registers. 1355 while (!regMasks.empty()) { 1356 const uint32_t *Mask = regMasks.pop_back_val(); 1357 for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I) 1358 if (TargetRegisterInfo::isPhysicalRegister(*I) && 1359 MachineOperand::clobbersPhysReg(Mask, *I)) 1360 regsDead.push_back(*I); 1361 } 1362 set_subtract(regsLive, regsDead); regsDead.clear(); 1363 set_union(regsLive, regsDefined); regsDefined.clear(); 1364 } 1365 1366 void 1367 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { 1368 MBBInfoMap[MBB].regsLiveOut = regsLive; 1369 regsLive.clear(); 1370 1371 if (Indexes) { 1372 SlotIndex stop = Indexes->getMBBEndIdx(MBB); 1373 if (!(stop > lastIndex)) { 1374 report("Block ends before last instruction index", MBB); 1375 errs() << "Block ends at " << stop 1376 << " last instruction was at " << lastIndex << '\n'; 1377 } 1378 lastIndex = stop; 1379 } 1380 } 1381 1382 // Calculate the largest possible vregsPassed sets. These are the registers that 1383 // can pass through an MBB live, but may not be live every time. It is assumed 1384 // that all vregsPassed sets are empty before the call. 1385 void MachineVerifier::calcRegsPassed() { 1386 // First push live-out regs to successors' vregsPassed. Remember the MBBs that 1387 // have any vregsPassed. 1388 SmallPtrSet<const MachineBasicBlock*, 8> todo; 1389 for (const auto &MBB : *MF) { 1390 BBInfo &MInfo = MBBInfoMap[&MBB]; 1391 if (!MInfo.reachable) 1392 continue; 1393 for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(), 1394 SuE = MBB.succ_end(); SuI != SuE; ++SuI) { 1395 BBInfo &SInfo = MBBInfoMap[*SuI]; 1396 if (SInfo.addPassed(MInfo.regsLiveOut)) 1397 todo.insert(*SuI); 1398 } 1399 } 1400 1401 // Iteratively push vregsPassed to successors. This will converge to the same 1402 // final state regardless of DenseSet iteration order. 1403 while (!todo.empty()) { 1404 const MachineBasicBlock *MBB = *todo.begin(); 1405 todo.erase(MBB); 1406 BBInfo &MInfo = MBBInfoMap[MBB]; 1407 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(), 1408 SuE = MBB->succ_end(); SuI != SuE; ++SuI) { 1409 if (*SuI == MBB) 1410 continue; 1411 BBInfo &SInfo = MBBInfoMap[*SuI]; 1412 if (SInfo.addPassed(MInfo.vregsPassed)) 1413 todo.insert(*SuI); 1414 } 1415 } 1416 } 1417 1418 // Calculate the set of virtual registers that must be passed through each basic 1419 // block in order to satisfy the requirements of successor blocks. This is very 1420 // similar to calcRegsPassed, only backwards. 1421 void MachineVerifier::calcRegsRequired() { 1422 // First push live-in regs to predecessors' vregsRequired. 1423 SmallPtrSet<const MachineBasicBlock*, 8> todo; 1424 for (const auto &MBB : *MF) { 1425 BBInfo &MInfo = MBBInfoMap[&MBB]; 1426 for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(), 1427 PrE = MBB.pred_end(); PrI != PrE; ++PrI) { 1428 BBInfo &PInfo = MBBInfoMap[*PrI]; 1429 if (PInfo.addRequired(MInfo.vregsLiveIn)) 1430 todo.insert(*PrI); 1431 } 1432 } 1433 1434 // Iteratively push vregsRequired to predecessors. This will converge to the 1435 // same final state regardless of DenseSet iteration order. 1436 while (!todo.empty()) { 1437 const MachineBasicBlock *MBB = *todo.begin(); 1438 todo.erase(MBB); 1439 BBInfo &MInfo = MBBInfoMap[MBB]; 1440 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1441 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1442 if (*PrI == MBB) 1443 continue; 1444 BBInfo &SInfo = MBBInfoMap[*PrI]; 1445 if (SInfo.addRequired(MInfo.vregsRequired)) 1446 todo.insert(*PrI); 1447 } 1448 } 1449 } 1450 1451 // Check PHI instructions at the beginning of MBB. It is assumed that 1452 // calcRegsPassed has been run so BBInfo::isLiveOut is valid. 1453 void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) { 1454 SmallPtrSet<const MachineBasicBlock*, 8> seen; 1455 for (const auto &BBI : *MBB) { 1456 if (!BBI.isPHI()) 1457 break; 1458 seen.clear(); 1459 1460 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) { 1461 unsigned Reg = BBI.getOperand(i).getReg(); 1462 const MachineBasicBlock *Pre = BBI.getOperand(i + 1).getMBB(); 1463 if (!Pre->isSuccessor(MBB)) 1464 continue; 1465 seen.insert(Pre); 1466 BBInfo &PrInfo = MBBInfoMap[Pre]; 1467 if (PrInfo.reachable && !PrInfo.isLiveOut(Reg)) 1468 report("PHI operand is not live-out from predecessor", 1469 &BBI.getOperand(i), i); 1470 } 1471 1472 // Did we see all predecessors? 1473 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(), 1474 PrE = MBB->pred_end(); PrI != PrE; ++PrI) { 1475 if (!seen.count(*PrI)) { 1476 report("Missing PHI operand", &BBI); 1477 errs() << "BB#" << (*PrI)->getNumber() 1478 << " is a predecessor according to the CFG.\n"; 1479 } 1480 } 1481 } 1482 } 1483 1484 void MachineVerifier::visitMachineFunctionAfter() { 1485 calcRegsPassed(); 1486 1487 for (const auto &MBB : *MF) { 1488 BBInfo &MInfo = MBBInfoMap[&MBB]; 1489 1490 // Skip unreachable MBBs. 1491 if (!MInfo.reachable) 1492 continue; 1493 1494 checkPHIOps(&MBB); 1495 } 1496 1497 // Now check liveness info if available 1498 calcRegsRequired(); 1499 1500 // Check for killed virtual registers that should be live out. 1501 for (const auto &MBB : *MF) { 1502 BBInfo &MInfo = MBBInfoMap[&MBB]; 1503 for (RegSet::iterator 1504 I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1505 ++I) 1506 if (MInfo.regsKilled.count(*I)) { 1507 report("Virtual register killed in block, but needed live out.", &MBB); 1508 errs() << "Virtual register " << PrintReg(*I) 1509 << " is used after the block.\n"; 1510 } 1511 } 1512 1513 if (!MF->empty()) { 1514 BBInfo &MInfo = MBBInfoMap[&MF->front()]; 1515 for (RegSet::iterator 1516 I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E; 1517 ++I) { 1518 report("Virtual register defs don't dominate all uses.", MF); 1519 report_context_vreg(*I); 1520 } 1521 } 1522 1523 if (LiveVars) 1524 verifyLiveVariables(); 1525 if (LiveInts) 1526 verifyLiveIntervals(); 1527 } 1528 1529 void MachineVerifier::verifyLiveVariables() { 1530 assert(LiveVars && "Don't call verifyLiveVariables without LiveVars"); 1531 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1532 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1533 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); 1534 for (const auto &MBB : *MF) { 1535 BBInfo &MInfo = MBBInfoMap[&MBB]; 1536 1537 // Our vregsRequired should be identical to LiveVariables' AliveBlocks 1538 if (MInfo.vregsRequired.count(Reg)) { 1539 if (!VI.AliveBlocks.test(MBB.getNumber())) { 1540 report("LiveVariables: Block missing from AliveBlocks", &MBB); 1541 errs() << "Virtual register " << PrintReg(Reg) 1542 << " must be live through the block.\n"; 1543 } 1544 } else { 1545 if (VI.AliveBlocks.test(MBB.getNumber())) { 1546 report("LiveVariables: Block should not be in AliveBlocks", &MBB); 1547 errs() << "Virtual register " << PrintReg(Reg) 1548 << " is not needed live through the block.\n"; 1549 } 1550 } 1551 } 1552 } 1553 } 1554 1555 void MachineVerifier::verifyLiveIntervals() { 1556 assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts"); 1557 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1558 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1559 1560 // Spilling and splitting may leave unused registers around. Skip them. 1561 if (MRI->reg_nodbg_empty(Reg)) 1562 continue; 1563 1564 if (!LiveInts->hasInterval(Reg)) { 1565 report("Missing live interval for virtual register", MF); 1566 errs() << PrintReg(Reg, TRI) << " still has defs or uses\n"; 1567 continue; 1568 } 1569 1570 const LiveInterval &LI = LiveInts->getInterval(Reg); 1571 assert(Reg == LI.reg && "Invalid reg to interval mapping"); 1572 verifyLiveInterval(LI); 1573 } 1574 1575 // Verify all the cached regunit intervals. 1576 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 1577 if (const LiveRange *LR = LiveInts->getCachedRegUnit(i)) 1578 verifyLiveRange(*LR, i); 1579 } 1580 1581 void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR, 1582 const VNInfo *VNI, unsigned Reg, 1583 LaneBitmask LaneMask) { 1584 if (VNI->isUnused()) 1585 return; 1586 1587 const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def); 1588 1589 if (!DefVNI) { 1590 report("Value not live at VNInfo def and not marked unused", MF); 1591 report_context(LR, Reg, LaneMask); 1592 report_context(*VNI); 1593 return; 1594 } 1595 1596 if (DefVNI != VNI) { 1597 report("Live segment at def has different VNInfo", MF); 1598 report_context(LR, Reg, LaneMask); 1599 report_context(*VNI); 1600 return; 1601 } 1602 1603 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def); 1604 if (!MBB) { 1605 report("Invalid VNInfo definition index", MF); 1606 report_context(LR, Reg, LaneMask); 1607 report_context(*VNI); 1608 return; 1609 } 1610 1611 if (VNI->isPHIDef()) { 1612 if (VNI->def != LiveInts->getMBBStartIdx(MBB)) { 1613 report("PHIDef VNInfo is not defined at MBB start", MBB); 1614 report_context(LR, Reg, LaneMask); 1615 report_context(*VNI); 1616 } 1617 return; 1618 } 1619 1620 // Non-PHI def. 1621 const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def); 1622 if (!MI) { 1623 report("No instruction at VNInfo def index", MBB); 1624 report_context(LR, Reg, LaneMask); 1625 report_context(*VNI); 1626 return; 1627 } 1628 1629 if (Reg != 0) { 1630 bool hasDef = false; 1631 bool isEarlyClobber = false; 1632 for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) { 1633 if (!MOI->isReg() || !MOI->isDef()) 1634 continue; 1635 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1636 if (MOI->getReg() != Reg) 1637 continue; 1638 } else { 1639 if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) || 1640 !TRI->hasRegUnit(MOI->getReg(), Reg)) 1641 continue; 1642 } 1643 if (LaneMask != 0 && 1644 (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask) == 0) 1645 continue; 1646 hasDef = true; 1647 if (MOI->isEarlyClobber()) 1648 isEarlyClobber = true; 1649 } 1650 1651 if (!hasDef) { 1652 report("Defining instruction does not modify register", MI); 1653 report_context(LR, Reg, LaneMask); 1654 report_context(*VNI); 1655 } 1656 1657 // Early clobber defs begin at USE slots, but other defs must begin at 1658 // DEF slots. 1659 if (isEarlyClobber) { 1660 if (!VNI->def.isEarlyClobber()) { 1661 report("Early clobber def must be at an early-clobber slot", MBB); 1662 report_context(LR, Reg, LaneMask); 1663 report_context(*VNI); 1664 } 1665 } else if (!VNI->def.isRegister()) { 1666 report("Non-PHI, non-early clobber def must be at a register slot", MBB); 1667 report_context(LR, Reg, LaneMask); 1668 report_context(*VNI); 1669 } 1670 } 1671 } 1672 1673 void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR, 1674 const LiveRange::const_iterator I, 1675 unsigned Reg, LaneBitmask LaneMask) 1676 { 1677 const LiveRange::Segment &S = *I; 1678 const VNInfo *VNI = S.valno; 1679 assert(VNI && "Live segment has no valno"); 1680 1681 if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) { 1682 report("Foreign valno in live segment", MF); 1683 report_context(LR, Reg, LaneMask); 1684 report_context(S); 1685 report_context(*VNI); 1686 } 1687 1688 if (VNI->isUnused()) { 1689 report("Live segment valno is marked unused", MF); 1690 report_context(LR, Reg, LaneMask); 1691 report_context(S); 1692 } 1693 1694 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start); 1695 if (!MBB) { 1696 report("Bad start of live segment, no basic block", MF); 1697 report_context(LR, Reg, LaneMask); 1698 report_context(S); 1699 return; 1700 } 1701 SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB); 1702 if (S.start != MBBStartIdx && S.start != VNI->def) { 1703 report("Live segment must begin at MBB entry or valno def", MBB); 1704 report_context(LR, Reg, LaneMask); 1705 report_context(S); 1706 } 1707 1708 const MachineBasicBlock *EndMBB = 1709 LiveInts->getMBBFromIndex(S.end.getPrevSlot()); 1710 if (!EndMBB) { 1711 report("Bad end of live segment, no basic block", MF); 1712 report_context(LR, Reg, LaneMask); 1713 report_context(S); 1714 return; 1715 } 1716 1717 // No more checks for live-out segments. 1718 if (S.end == LiveInts->getMBBEndIdx(EndMBB)) 1719 return; 1720 1721 // RegUnit intervals are allowed dead phis. 1722 if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() && 1723 S.start == VNI->def && S.end == VNI->def.getDeadSlot()) 1724 return; 1725 1726 // The live segment is ending inside EndMBB 1727 const MachineInstr *MI = 1728 LiveInts->getInstructionFromIndex(S.end.getPrevSlot()); 1729 if (!MI) { 1730 report("Live segment doesn't end at a valid instruction", EndMBB); 1731 report_context(LR, Reg, LaneMask); 1732 report_context(S); 1733 return; 1734 } 1735 1736 // The block slot must refer to a basic block boundary. 1737 if (S.end.isBlock()) { 1738 report("Live segment ends at B slot of an instruction", EndMBB); 1739 report_context(LR, Reg, LaneMask); 1740 report_context(S); 1741 } 1742 1743 if (S.end.isDead()) { 1744 // Segment ends on the dead slot. 1745 // That means there must be a dead def. 1746 if (!SlotIndex::isSameInstr(S.start, S.end)) { 1747 report("Live segment ending at dead slot spans instructions", EndMBB); 1748 report_context(LR, Reg, LaneMask); 1749 report_context(S); 1750 } 1751 } 1752 1753 // A live segment can only end at an early-clobber slot if it is being 1754 // redefined by an early-clobber def. 1755 if (S.end.isEarlyClobber()) { 1756 if (I+1 == LR.end() || (I+1)->start != S.end) { 1757 report("Live segment ending at early clobber slot must be " 1758 "redefined by an EC def in the same instruction", EndMBB); 1759 report_context(LR, Reg, LaneMask); 1760 report_context(S); 1761 } 1762 } 1763 1764 // The following checks only apply to virtual registers. Physreg liveness 1765 // is too weird to check. 1766 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1767 // A live segment can end with either a redefinition, a kill flag on a 1768 // use, or a dead flag on a def. 1769 bool hasRead = false; 1770 bool hasSubRegDef = false; 1771 bool hasDeadDef = false; 1772 for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) { 1773 if (!MOI->isReg() || MOI->getReg() != Reg) 1774 continue; 1775 if (LaneMask != 0 && 1776 (LaneMask & TRI->getSubRegIndexLaneMask(MOI->getSubReg())) == 0) 1777 continue; 1778 if (MOI->isDef()) { 1779 if (MOI->getSubReg() != 0) 1780 hasSubRegDef = true; 1781 if (MOI->isDead()) 1782 hasDeadDef = true; 1783 } 1784 if (MOI->readsReg()) 1785 hasRead = true; 1786 } 1787 if (S.end.isDead()) { 1788 // Make sure that the corresponding machine operand for a "dead" live 1789 // range has the dead flag. We cannot perform this check for subregister 1790 // liveranges as partially dead values are allowed. 1791 if (LaneMask == 0 && !hasDeadDef) { 1792 report("Instruction ending live segment on dead slot has no dead flag", 1793 MI); 1794 report_context(LR, Reg, LaneMask); 1795 report_context(S); 1796 } 1797 } else { 1798 if (!hasRead) { 1799 // When tracking subregister liveness, the main range must start new 1800 // values on partial register writes, even if there is no read. 1801 if (!MRI->shouldTrackSubRegLiveness(Reg) || LaneMask != 0 || 1802 !hasSubRegDef) { 1803 report("Instruction ending live segment doesn't read the register", 1804 MI); 1805 report_context(LR, Reg, LaneMask); 1806 report_context(S); 1807 } 1808 } 1809 } 1810 } 1811 1812 // Now check all the basic blocks in this live segment. 1813 MachineFunction::const_iterator MFI = MBB->getIterator(); 1814 // Is this live segment the beginning of a non-PHIDef VN? 1815 if (S.start == VNI->def && !VNI->isPHIDef()) { 1816 // Not live-in to any blocks. 1817 if (MBB == EndMBB) 1818 return; 1819 // Skip this block. 1820 ++MFI; 1821 } 1822 for (;;) { 1823 assert(LiveInts->isLiveInToMBB(LR, &*MFI)); 1824 // We don't know how to track physregs into a landing pad. 1825 if (!TargetRegisterInfo::isVirtualRegister(Reg) && 1826 MFI->isEHPad()) { 1827 if (&*MFI == EndMBB) 1828 break; 1829 ++MFI; 1830 continue; 1831 } 1832 1833 // Is VNI a PHI-def in the current block? 1834 bool IsPHI = VNI->isPHIDef() && 1835 VNI->def == LiveInts->getMBBStartIdx(&*MFI); 1836 1837 // Check that VNI is live-out of all predecessors. 1838 for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(), 1839 PE = MFI->pred_end(); PI != PE; ++PI) { 1840 SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI); 1841 const VNInfo *PVNI = LR.getVNInfoBefore(PEnd); 1842 1843 // All predecessors must have a live-out value if this is not a 1844 // subregister liverange. 1845 if (!PVNI && LaneMask == 0) { 1846 report("Register not marked live out of predecessor", *PI); 1847 report_context(LR, Reg, LaneMask); 1848 report_context(*VNI); 1849 errs() << " live into BB#" << MFI->getNumber() 1850 << '@' << LiveInts->getMBBStartIdx(&*MFI) << ", not live before " 1851 << PEnd << '\n'; 1852 continue; 1853 } 1854 1855 // Only PHI-defs can take different predecessor values. 1856 if (!IsPHI && PVNI != VNI) { 1857 report("Different value live out of predecessor", *PI); 1858 report_context(LR, Reg, LaneMask); 1859 errs() << "Valno #" << PVNI->id << " live out of BB#" 1860 << (*PI)->getNumber() << '@' << PEnd << "\nValno #" << VNI->id 1861 << " live into BB#" << MFI->getNumber() << '@' 1862 << LiveInts->getMBBStartIdx(&*MFI) << '\n'; 1863 } 1864 } 1865 if (&*MFI == EndMBB) 1866 break; 1867 ++MFI; 1868 } 1869 } 1870 1871 void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg, 1872 LaneBitmask LaneMask) { 1873 for (const VNInfo *VNI : LR.valnos) 1874 verifyLiveRangeValue(LR, VNI, Reg, LaneMask); 1875 1876 for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I) 1877 verifyLiveRangeSegment(LR, I, Reg, LaneMask); 1878 } 1879 1880 void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) { 1881 unsigned Reg = LI.reg; 1882 assert(TargetRegisterInfo::isVirtualRegister(Reg)); 1883 verifyLiveRange(LI, Reg); 1884 1885 LaneBitmask Mask = 0; 1886 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg); 1887 for (const LiveInterval::SubRange &SR : LI.subranges()) { 1888 if ((Mask & SR.LaneMask) != 0) { 1889 report("Lane masks of sub ranges overlap in live interval", MF); 1890 report_context(LI); 1891 } 1892 if ((SR.LaneMask & ~MaxMask) != 0) { 1893 report("Subrange lanemask is invalid", MF); 1894 report_context(LI); 1895 } 1896 if (SR.empty()) { 1897 report("Subrange must not be empty", MF); 1898 report_context(SR, LI.reg, SR.LaneMask); 1899 } 1900 Mask |= SR.LaneMask; 1901 verifyLiveRange(SR, LI.reg, SR.LaneMask); 1902 if (!LI.covers(SR)) { 1903 report("A Subrange is not covered by the main range", MF); 1904 report_context(LI); 1905 } 1906 } 1907 1908 // Check the LI only has one connected component. 1909 ConnectedVNInfoEqClasses ConEQ(*LiveInts); 1910 unsigned NumComp = ConEQ.Classify(LI); 1911 if (NumComp > 1) { 1912 report("Multiple connected components in live interval", MF); 1913 report_context(LI); 1914 for (unsigned comp = 0; comp != NumComp; ++comp) { 1915 errs() << comp << ": valnos"; 1916 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), 1917 E = LI.vni_end(); I!=E; ++I) 1918 if (comp == ConEQ.getEqClass(*I)) 1919 errs() << ' ' << (*I)->id; 1920 errs() << '\n'; 1921 } 1922 } 1923 } 1924 1925 namespace { 1926 // FrameSetup and FrameDestroy can have zero adjustment, so using a single 1927 // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the 1928 // value is zero. 1929 // We use a bool plus an integer to capture the stack state. 1930 struct StackStateOfBB { 1931 StackStateOfBB() : EntryValue(0), ExitValue(0), EntryIsSetup(false), 1932 ExitIsSetup(false) { } 1933 StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) : 1934 EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup), 1935 ExitIsSetup(ExitSetup) { } 1936 // Can be negative, which means we are setting up a frame. 1937 int EntryValue; 1938 int ExitValue; 1939 bool EntryIsSetup; 1940 bool ExitIsSetup; 1941 }; 1942 } 1943 1944 /// Make sure on every path through the CFG, a FrameSetup <n> is always followed 1945 /// by a FrameDestroy <n>, stack adjustments are identical on all 1946 /// CFG edges to a merge point, and frame is destroyed at end of a return block. 1947 void MachineVerifier::verifyStackFrame() { 1948 unsigned FrameSetupOpcode = TII->getCallFrameSetupOpcode(); 1949 unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode(); 1950 1951 SmallVector<StackStateOfBB, 8> SPState; 1952 SPState.resize(MF->getNumBlockIDs()); 1953 SmallPtrSet<const MachineBasicBlock*, 8> Reachable; 1954 1955 // Visit the MBBs in DFS order. 1956 for (df_ext_iterator<const MachineFunction*, 1957 SmallPtrSet<const MachineBasicBlock*, 8> > 1958 DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable); 1959 DFI != DFE; ++DFI) { 1960 const MachineBasicBlock *MBB = *DFI; 1961 1962 StackStateOfBB BBState; 1963 // Check the exit state of the DFS stack predecessor. 1964 if (DFI.getPathLength() >= 2) { 1965 const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); 1966 assert(Reachable.count(StackPred) && 1967 "DFS stack predecessor is already visited.\n"); 1968 BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue; 1969 BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup; 1970 BBState.ExitValue = BBState.EntryValue; 1971 BBState.ExitIsSetup = BBState.EntryIsSetup; 1972 } 1973 1974 // Update stack state by checking contents of MBB. 1975 for (const auto &I : *MBB) { 1976 if (I.getOpcode() == FrameSetupOpcode) { 1977 // The first operand of a FrameOpcode should be i32. 1978 int Size = I.getOperand(0).getImm(); 1979 assert(Size >= 0 && 1980 "Value should be non-negative in FrameSetup and FrameDestroy.\n"); 1981 1982 if (BBState.ExitIsSetup) 1983 report("FrameSetup is after another FrameSetup", &I); 1984 BBState.ExitValue -= Size; 1985 BBState.ExitIsSetup = true; 1986 } 1987 1988 if (I.getOpcode() == FrameDestroyOpcode) { 1989 // The first operand of a FrameOpcode should be i32. 1990 int Size = I.getOperand(0).getImm(); 1991 assert(Size >= 0 && 1992 "Value should be non-negative in FrameSetup and FrameDestroy.\n"); 1993 1994 if (!BBState.ExitIsSetup) 1995 report("FrameDestroy is not after a FrameSetup", &I); 1996 int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue : 1997 BBState.ExitValue; 1998 if (BBState.ExitIsSetup && AbsSPAdj != Size) { 1999 report("FrameDestroy <n> is after FrameSetup <m>", &I); 2000 errs() << "FrameDestroy <" << Size << "> is after FrameSetup <" 2001 << AbsSPAdj << ">.\n"; 2002 } 2003 BBState.ExitValue += Size; 2004 BBState.ExitIsSetup = false; 2005 } 2006 } 2007 SPState[MBB->getNumber()] = BBState; 2008 2009 // Make sure the exit state of any predecessor is consistent with the entry 2010 // state. 2011 for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(), 2012 E = MBB->pred_end(); I != E; ++I) { 2013 if (Reachable.count(*I) && 2014 (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue || 2015 SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) { 2016 report("The exit stack state of a predecessor is inconsistent.", MBB); 2017 errs() << "Predecessor BB#" << (*I)->getNumber() << " has exit state (" 2018 << SPState[(*I)->getNumber()].ExitValue << ", " 2019 << SPState[(*I)->getNumber()].ExitIsSetup 2020 << "), while BB#" << MBB->getNumber() << " has entry state (" 2021 << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n"; 2022 } 2023 } 2024 2025 // Make sure the entry state of any successor is consistent with the exit 2026 // state. 2027 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 2028 E = MBB->succ_end(); I != E; ++I) { 2029 if (Reachable.count(*I) && 2030 (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue || 2031 SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) { 2032 report("The entry stack state of a successor is inconsistent.", MBB); 2033 errs() << "Successor BB#" << (*I)->getNumber() << " has entry state (" 2034 << SPState[(*I)->getNumber()].EntryValue << ", " 2035 << SPState[(*I)->getNumber()].EntryIsSetup 2036 << "), while BB#" << MBB->getNumber() << " has exit state (" 2037 << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n"; 2038 } 2039 } 2040 2041 // Make sure a basic block with return ends with zero stack adjustment. 2042 if (!MBB->empty() && MBB->back().isReturn()) { 2043 if (BBState.ExitIsSetup) 2044 report("A return block ends with a FrameSetup.", MBB); 2045 if (BBState.ExitValue) 2046 report("A return block ends with a nonzero stack adjustment.", MBB); 2047 } 2048 } 2049 } 2050