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