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