contrib/llvm/lib/CodeGen/MachineVerifier.cpp

   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 }