LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineVerifier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 774 1131 68.4 %
Date: 2018-02-20 16:54:40 Functions: 52 61 85.2 %
Legend: Lines: hit not hit

          Line data    Source code
       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/ADT/BitVector.h"
      27             : #include "llvm/ADT/DenseMap.h"
      28             : #include "llvm/ADT/DenseSet.h"
      29             : #include "llvm/ADT/DepthFirstIterator.h"
      30             : #include "llvm/ADT/STLExtras.h"
      31             : #include "llvm/ADT/SetOperations.h"
      32             : #include "llvm/ADT/SmallPtrSet.h"
      33             : #include "llvm/ADT/SmallVector.h"
      34             : #include "llvm/ADT/StringRef.h"
      35             : #include "llvm/ADT/Twine.h"
      36             : #include "llvm/Analysis/EHPersonalities.h"
      37             : #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
      38             : #include "llvm/CodeGen/LiveInterval.h"
      39             : #include "llvm/CodeGen/LiveIntervals.h"
      40             : #include "llvm/CodeGen/LiveStacks.h"
      41             : #include "llvm/CodeGen/LiveVariables.h"
      42             : #include "llvm/CodeGen/MachineBasicBlock.h"
      43             : #include "llvm/CodeGen/MachineFrameInfo.h"
      44             : #include "llvm/CodeGen/MachineFunction.h"
      45             : #include "llvm/CodeGen/MachineFunctionPass.h"
      46             : #include "llvm/CodeGen/MachineInstr.h"
      47             : #include "llvm/CodeGen/MachineInstrBundle.h"
      48             : #include "llvm/CodeGen/MachineMemOperand.h"
      49             : #include "llvm/CodeGen/MachineOperand.h"
      50             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      51             : #include "llvm/CodeGen/PseudoSourceValue.h"
      52             : #include "llvm/CodeGen/SlotIndexes.h"
      53             : #include "llvm/CodeGen/StackMaps.h"
      54             : #include "llvm/CodeGen/TargetInstrInfo.h"
      55             : #include "llvm/CodeGen/TargetOpcodes.h"
      56             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      57             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      58             : #include "llvm/IR/BasicBlock.h"
      59             : #include "llvm/IR/Function.h"
      60             : #include "llvm/IR/InlineAsm.h"
      61             : #include "llvm/IR/Instructions.h"
      62             : #include "llvm/MC/LaneBitmask.h"
      63             : #include "llvm/MC/MCAsmInfo.h"
      64             : #include "llvm/MC/MCInstrDesc.h"
      65             : #include "llvm/MC/MCRegisterInfo.h"
      66             : #include "llvm/MC/MCTargetOptions.h"
      67             : #include "llvm/Pass.h"
      68             : #include "llvm/Support/Casting.h"
      69             : #include "llvm/Support/ErrorHandling.h"
      70             : #include "llvm/Support/LowLevelTypeImpl.h"
      71             : #include "llvm/Support/MathExtras.h"
      72             : #include "llvm/Support/raw_ostream.h"
      73             : #include "llvm/Target/TargetMachine.h"
      74             : #include <algorithm>
      75             : #include <cassert>
      76             : #include <cstddef>
      77             : #include <cstdint>
      78             : #include <iterator>
      79             : #include <string>
      80             : #include <utility>
      81             : 
      82             : using namespace llvm;
      83             : 
      84             : namespace {
      85             : 
      86     2679304 :   struct MachineVerifier {
      87     4018956 :     MachineVerifier(Pass *pass, const char *b) : PASS(pass), Banner(b) {}
      88             : 
      89             :     unsigned verify(MachineFunction &MF);
      90             : 
      91             :     Pass *const PASS;
      92             :     const char *Banner;
      93             :     const MachineFunction *MF;
      94             :     const TargetMachine *TM;
      95             :     const TargetInstrInfo *TII;
      96             :     const TargetRegisterInfo *TRI;
      97             :     const MachineRegisterInfo *MRI;
      98             : 
      99             :     unsigned foundErrors;
     100             : 
     101             :     // Avoid querying the MachineFunctionProperties for each operand.
     102             :     bool isFunctionRegBankSelected;
     103             :     bool isFunctionSelected;
     104             : 
     105             :     using RegVector = SmallVector<unsigned, 16>;
     106             :     using RegMaskVector = SmallVector<const uint32_t *, 4>;
     107             :     using RegSet = DenseSet<unsigned>;
     108             :     using RegMap = DenseMap<unsigned, const MachineInstr *>;
     109             :     using BlockSet = SmallPtrSet<const MachineBasicBlock *, 8>;
     110             : 
     111             :     const MachineInstr *FirstTerminator;
     112             :     BlockSet FunctionBlocks;
     113             : 
     114             :     BitVector regsReserved;
     115             :     RegSet regsLive;
     116             :     RegVector regsDefined, regsDead, regsKilled;
     117             :     RegMaskVector regMasks;
     118             : 
     119             :     SlotIndex lastIndex;
     120             : 
     121             :     // Add Reg and any sub-registers to RV
     122    26857233 :     void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
     123    26857233 :       RV.push_back(Reg);
     124    53714466 :       if (TargetRegisterInfo::isPhysicalRegister(Reg))
     125    39862837 :         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
     126    11529173 :           RV.push_back(*SubRegs);
     127    26857233 :     }
     128             : 
     129     3359364 :     struct BBInfo {
     130             :       // Is this MBB reachable from the MF entry point?
     131             :       bool reachable = false;
     132             : 
     133             :       // Vregs that must be live in because they are used without being
     134             :       // defined. Map value is the user.
     135             :       RegMap vregsLiveIn;
     136             : 
     137             :       // Regs killed in MBB. They may be defined again, and will then be in both
     138             :       // regsKilled and regsLiveOut.
     139             :       RegSet regsKilled;
     140             : 
     141             :       // Regs defined in MBB and live out. Note that vregs passing through may
     142             :       // be live out without being mentioned here.
     143             :       RegSet regsLiveOut;
     144             : 
     145             :       // Vregs that pass through MBB untouched. This set is disjoint from
     146             :       // regsKilled and regsLiveOut.
     147             :       RegSet vregsPassed;
     148             : 
     149             :       // Vregs that must pass through MBB because they are needed by a successor
     150             :       // block. This set is disjoint from regsLiveOut.
     151             :       RegSet vregsRequired;
     152             : 
     153             :       // Set versions of block's predecessor and successor lists.
     154             :       BlockSet Preds, Succs;
     155             : 
     156     3328672 :       BBInfo() = default;
     157             : 
     158             :       // Add register to vregsPassed if it belongs there. Return true if
     159             :       // anything changed.
     160    15119909 :       bool addPassed(unsigned Reg) {
     161    30239818 :         if (!TargetRegisterInfo::isVirtualRegister(Reg))
     162             :           return false;
     163             :         if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
     164             :           return false;
     165             :         return vregsPassed.insert(Reg).second;
     166             :       }
     167             : 
     168             :       // Same for a full set.
     169      640779 :       bool addPassed(const RegSet &RS) {
     170             :         bool changed = false;
     171    15760688 :         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
     172    15119909 :           if (addPassed(*I))
     173             :             changed = true;
     174      640779 :         return changed;
     175             :       }
     176             : 
     177             :       // Add register to vregsRequired if it belongs there. Return true if
     178             :       // anything changed.
     179     1140927 :       bool addRequired(unsigned Reg) {
     180     2281854 :         if (!TargetRegisterInfo::isVirtualRegister(Reg))
     181             :           return false;
     182             :         if (regsLiveOut.count(Reg))
     183             :           return false;
     184             :         return vregsRequired.insert(Reg).second;
     185             :       }
     186             : 
     187             :       // Same for a full set.
     188      101529 :       bool addRequired(const RegSet &RS) {
     189             :         bool changed = false;
     190      928348 :         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
     191      826819 :           if (addRequired(*I))
     192             :             changed = true;
     193      101529 :         return changed;
     194             :       }
     195             : 
     196             :       // Same for a full map.
     197      460231 :       bool addRequired(const RegMap &RM) {
     198             :         bool changed = false;
     199     1234570 :         for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
     200      314108 :           if (addRequired(I->first))
     201             :             changed = true;
     202      460231 :         return changed;
     203             :       }
     204             : 
     205             :       // Live-out registers are either in regsLiveOut or vregsPassed.
     206      157056 :       bool isLiveOut(unsigned Reg) const {
     207      157056 :         return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
     208             :       }
     209             :     };
     210             : 
     211             :     // Extra register info per MBB.
     212             :     DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
     213             : 
     214             :     bool isReserved(unsigned Reg) {
     215    21437912 :       return Reg < regsReserved.size() && regsReserved.test(Reg);
     216             :     }
     217             : 
     218      811965 :     bool isAllocatable(unsigned Reg) const {
     219     2435686 :       return Reg < TRI->getNumRegs() && TRI->isInAllocatableClass(Reg) &&
     220      811965 :         !regsReserved.test(Reg);
     221             :     }
     222             : 
     223             :     // Analysis information if available
     224             :     LiveVariables *LiveVars;
     225             :     LiveIntervals *LiveInts;
     226             :     LiveStacks *LiveStks;
     227             :     SlotIndexes *Indexes;
     228             : 
     229             :     void visitMachineFunctionBefore();
     230             :     void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
     231             :     void visitMachineBundleBefore(const MachineInstr *MI);
     232             :     void visitMachineInstrBefore(const MachineInstr *MI);
     233             :     void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
     234             :     void visitMachineInstrAfter(const MachineInstr *MI);
     235             :     void visitMachineBundleAfter(const MachineInstr *MI);
     236             :     void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
     237             :     void visitMachineFunctionAfter();
     238             : 
     239             :     void report(const char *msg, const MachineFunction *MF);
     240             :     void report(const char *msg, const MachineBasicBlock *MBB);
     241             :     void report(const char *msg, const MachineInstr *MI);
     242             :     void report(const char *msg, const MachineOperand *MO, unsigned MONum);
     243             : 
     244             :     void report_context(const LiveInterval &LI) const;
     245             :     void report_context(const LiveRange &LR, unsigned VRegUnit,
     246             :                         LaneBitmask LaneMask) const;
     247             :     void report_context(const LiveRange::Segment &S) const;
     248             :     void report_context(const VNInfo &VNI) const;
     249             :     void report_context(SlotIndex Pos) const;
     250             :     void report_context_liverange(const LiveRange &LR) const;
     251             :     void report_context_lanemask(LaneBitmask LaneMask) const;
     252             :     void report_context_vreg(unsigned VReg) const;
     253             :     void report_context_vreg_regunit(unsigned VRegOrRegUnit) const;
     254             : 
     255             :     void verifyInlineAsm(const MachineInstr *MI);
     256             : 
     257             :     void checkLiveness(const MachineOperand *MO, unsigned MONum);
     258             :     void checkLivenessAtUse(const MachineOperand *MO, unsigned MONum,
     259             :                             SlotIndex UseIdx, const LiveRange &LR, unsigned Reg,
     260             :                             LaneBitmask LaneMask = LaneBitmask::getNone());
     261             :     void checkLivenessAtDef(const MachineOperand *MO, unsigned MONum,
     262             :                             SlotIndex DefIdx, const LiveRange &LR, unsigned Reg,
     263             :                             LaneBitmask LaneMask = LaneBitmask::getNone());
     264             : 
     265             :     void markReachable(const MachineBasicBlock *MBB);
     266             :     void calcRegsPassed();
     267             :     void checkPHIOps(const MachineBasicBlock &MBB);
     268             : 
     269             :     void calcRegsRequired();
     270             :     void verifyLiveVariables();
     271             :     void verifyLiveIntervals();
     272             :     void verifyLiveInterval(const LiveInterval&);
     273             :     void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned,
     274             :                               LaneBitmask);
     275             :     void verifyLiveRangeSegment(const LiveRange&,
     276             :                                 const LiveRange::const_iterator I, unsigned,
     277             :                                 LaneBitmask);
     278             :     void verifyLiveRange(const LiveRange&, unsigned,
     279             :                          LaneBitmask LaneMask = LaneBitmask::getNone());
     280             : 
     281             :     void verifyStackFrame();
     282             : 
     283             :     void verifySlotIndexes() const;
     284             :     void verifyProperties(const MachineFunction &MF);
     285             :   };
     286             : 
     287      408579 :   struct MachineVerifierPass : public MachineFunctionPass {
     288             :     static char ID; // Pass ID, replacement for typeid
     289             : 
     290             :     const std::string Banner;
     291             : 
     292      136441 :     MachineVerifierPass(std::string banner = std::string())
     293      136441 :       : MachineFunctionPass(ID), Banner(std::move(banner)) {
     294      136441 :         initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
     295      136441 :       }
     296             : 
     297      136441 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
     298             :       AU.setPreservesAll();
     299      136441 :       MachineFunctionPass::getAnalysisUsage(AU);
     300      136441 :     }
     301             : 
     302     1336553 :     bool runOnMachineFunction(MachineFunction &MF) override {
     303     1336553 :       unsigned FoundErrors = MachineVerifier(this, Banner.c_str()).verify(MF);
     304     1336553 :       if (FoundErrors)
     305           1 :         report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
     306     1336552 :       return false;
     307             :     }
     308             :   };
     309             : 
     310             : } // end anonymous namespace
     311             : 
     312             : char MachineVerifierPass::ID = 0;
     313             : 
     314      407498 : INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
     315             :                 "Verify generated machine code", false, false)
     316             : 
     317      136440 : FunctionPass *llvm::createMachineVerifierPass(const std::string &Banner) {
     318      272880 :   return new MachineVerifierPass(Banner);
     319             : }
     320             : 
     321        3099 : bool MachineFunction::verify(Pass *p, const char *Banner, bool AbortOnErrors)
     322             :     const {
     323             :   MachineFunction &MF = const_cast<MachineFunction&>(*this);
     324        3099 :   unsigned FoundErrors = MachineVerifier(p, Banner).verify(MF);
     325        3099 :   if (AbortOnErrors && FoundErrors)
     326          31 :     report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
     327        3068 :   return FoundErrors == 0;
     328             : }
     329             : 
     330             : void MachineVerifier::verifySlotIndexes() const {
     331             :   if (Indexes == nullptr)
     332             :     return;
     333             : 
     334             :   // Ensure the IdxMBB list is sorted by slot indexes.
     335             :   SlotIndex Last;
     336             :   for (SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(),
     337             :        E = Indexes->MBBIndexEnd(); I != E; ++I) {
     338             :     assert(!Last.isValid() || I->first > Last);
     339             :     Last = I->first;
     340             :   }
     341             : }
     342             : 
     343     1339652 : void MachineVerifier::verifyProperties(const MachineFunction &MF) {
     344             :   // If a pass has introduced virtual registers without clearing the
     345             :   // NoVRegs property (or set it without allocating the vregs)
     346             :   // then report an error.
     347             :   if (MF.getProperties().hasProperty(
     348     1987696 :           MachineFunctionProperties::Property::NoVRegs) &&
     349      648044 :       MRI->getNumVirtRegs())
     350           0 :     report("Function has NoVRegs property but there are VReg operands", &MF);
     351     1339652 : }
     352             : 
     353     1339652 : unsigned MachineVerifier::verify(MachineFunction &MF) {
     354     1339652 :   foundErrors = 0;
     355             : 
     356     1339652 :   this->MF = &MF;
     357     1339652 :   TM = &MF.getTarget();
     358     1339652 :   TII = MF.getSubtarget().getInstrInfo();
     359     1339652 :   TRI = MF.getSubtarget().getRegisterInfo();
     360     1339652 :   MRI = &MF.getRegInfo();
     361             : 
     362     1339652 :   isFunctionRegBankSelected = MF.getProperties().hasProperty(
     363             :       MachineFunctionProperties::Property::RegBankSelected);
     364     1339652 :   isFunctionSelected = MF.getProperties().hasProperty(
     365             :       MachineFunctionProperties::Property::Selected);
     366             : 
     367     1339652 :   LiveVars = nullptr;
     368     1339652 :   LiveInts = nullptr;
     369     1339652 :   LiveStks = nullptr;
     370     1339652 :   Indexes = nullptr;
     371     1339652 :   if (PASS) {
     372     1336732 :     LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
     373             :     // We don't want to verify LiveVariables if LiveIntervals is available.
     374     1336732 :     if (!LiveInts)
     375     1180278 :       LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
     376     1336732 :     LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
     377     1336732 :     Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
     378             :   }
     379             : 
     380             :   verifySlotIndexes();
     381             : 
     382     1339652 :   verifyProperties(MF);
     383             : 
     384     1339652 :   visitMachineFunctionBefore();
     385             :   for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
     386     3003988 :        MFI!=MFE; ++MFI) {
     387     1664336 :     visitMachineBasicBlockBefore(&*MFI);
     388             :     // Keep track of the current bundle header.
     389             :     const MachineInstr *CurBundle = nullptr;
     390             :     // Do we expect the next instruction to be part of the same bundle?
     391             :     bool InBundle = false;
     392             : 
     393             :     for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
     394    22075203 :            MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
     395    20410867 :       if (MBBI->getParent() != &*MFI) {
     396           0 :         report("Bad instruction parent pointer", &*MFI);
     397           0 :         errs() << "Instruction: " << *MBBI;
     398           0 :         continue;
     399             :       }
     400             : 
     401             :       // Check for consistent bundle flags.
     402    20434157 :       if (InBundle && !MBBI->isBundledWithPred())
     403           0 :         report("Missing BundledPred flag, "
     404             :                "BundledSucc was set on predecessor",
     405             :                &*MBBI);
     406    40798444 :       if (!InBundle && MBBI->isBundledWithPred())
     407           0 :         report("BundledPred flag is set, "
     408             :                "but BundledSucc not set on predecessor",
     409             :                &*MBBI);
     410             : 
     411             :       // Is this a bundle header?
     412    20410867 :       if (!MBBI->isInsideBundle()) {
     413    20387577 :         if (CurBundle)
     414    18738325 :           visitMachineBundleAfter(CurBundle);
     415             :         CurBundle = &*MBBI;
     416    20387577 :         visitMachineBundleBefore(CurBundle);
     417       23290 :       } else if (!CurBundle)
     418           0 :         report("No bundle header", &*MBBI);
     419    20410867 :       visitMachineInstrBefore(&*MBBI);
     420   103293875 :       for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) {
     421             :         const MachineInstr &MI = *MBBI;
     422    82883008 :         const MachineOperand &Op = MI.getOperand(I);
     423    82883008 :         if (Op.getParent() != &MI) {
     424             :           // Make sure to use correct addOperand / RemoveOperand / ChangeTo
     425             :           // functions when replacing operands of a MachineInstr.
     426           0 :           report("Instruction has operand with wrong parent set", &MI);
     427             :         }
     428             : 
     429    82883008 :         visitMachineOperand(&Op, I);
     430             :       }
     431             : 
     432             :       visitMachineInstrAfter(&*MBBI);
     433             : 
     434             :       // Was this the last bundled instruction?
     435             :       InBundle = MBBI->isBundledWithSucc();
     436             :     }
     437     1664336 :     if (CurBundle)
     438     1649252 :       visitMachineBundleAfter(CurBundle);
     439     1664336 :     if (InBundle)
     440           0 :       report("BundledSucc flag set on last instruction in block", &MFI->back());
     441     1664336 :     visitMachineBasicBlockAfter(&*MFI);
     442             :   }
     443     1339652 :   visitMachineFunctionAfter();
     444             : 
     445             :   // Clean up.
     446             :   regsLive.clear();
     447             :   regsDefined.clear();
     448             :   regsDead.clear();
     449             :   regsKilled.clear();
     450             :   regMasks.clear();
     451     1339652 :   MBBInfoMap.clear();
     452             : 
     453     1339652 :   return foundErrors;
     454             : }
     455             : 
     456          45 : void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
     457             :   assert(MF);
     458          45 :   errs() << '\n';
     459          45 :   if (!foundErrors++) {
     460          32 :     if (Banner)
     461           1 :       errs() << "# " << Banner << '\n';
     462          32 :     if (LiveInts != nullptr)
     463           0 :       LiveInts->print(errs());
     464             :     else
     465          32 :       MF->print(errs(), Indexes);
     466             :   }
     467          45 :   errs() << "*** Bad machine code: " << msg << " ***\n"
     468          45 :       << "- function:    " << MF->getName() << "\n";
     469          45 : }
     470             : 
     471          45 : void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
     472             :   assert(MBB);
     473          45 :   report(msg, MBB->getParent());
     474          90 :   errs() << "- basic block: " << printMBBReference(*MBB) << ' '
     475          45 :          << MBB->getName() << " (" << (const void *)MBB << ')';
     476          45 :   if (Indexes)
     477           0 :     errs() << " [" << Indexes->getMBBStartIdx(MBB)
     478           0 :         << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
     479          45 :   errs() << '\n';
     480          45 : }
     481             : 
     482          45 : void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
     483             :   assert(MI);
     484          45 :   report(msg, MI->getParent());
     485          45 :   errs() << "- instruction: ";
     486          45 :   if (Indexes && Indexes->hasIndex(*MI))
     487           0 :     errs() << Indexes->getInstructionIndex(*MI) << '\t';
     488          45 :   MI->print(errs(), /*SkipOpers=*/true);
     489          45 :   errs() << '\n';
     490          45 : }
     491             : 
     492           5 : void MachineVerifier::report(const char *msg,
     493             :                              const MachineOperand *MO, unsigned MONum) {
     494             :   assert(MO);
     495           5 :   report(msg, MO->getParent());
     496          10 :   errs() << "- operand " << MONum << ":   ";
     497           5 :   MO->print(errs(), TRI);
     498           5 :   errs() << "\n";
     499           5 : }
     500             : 
     501           0 : void MachineVerifier::report_context(SlotIndex Pos) const {
     502           0 :   errs() << "- at:          " << Pos << '\n';
     503           0 : }
     504             : 
     505           0 : void MachineVerifier::report_context(const LiveInterval &LI) const {
     506           0 :   errs() << "- interval:    " << LI << '\n';
     507           0 : }
     508             : 
     509           0 : void MachineVerifier::report_context(const LiveRange &LR, unsigned VRegUnit,
     510             :                                      LaneBitmask LaneMask) const {
     511           0 :   report_context_liverange(LR);
     512           0 :   report_context_vreg_regunit(VRegUnit);
     513           0 :   if (LaneMask.any())
     514           0 :     report_context_lanemask(LaneMask);
     515           0 : }
     516             : 
     517           0 : void MachineVerifier::report_context(const LiveRange::Segment &S) const {
     518           0 :   errs() << "- segment:     " << S << '\n';
     519           0 : }
     520             : 
     521           0 : void MachineVerifier::report_context(const VNInfo &VNI) const {
     522           0 :   errs() << "- ValNo:       " << VNI.id << " (def " << VNI.def << ")\n";
     523           0 : }
     524             : 
     525           0 : void MachineVerifier::report_context_liverange(const LiveRange &LR) const {
     526           0 :   errs() << "- liverange:   " << LR << '\n';
     527           0 : }
     528             : 
     529           0 : void MachineVerifier::report_context_vreg(unsigned VReg) const {
     530           0 :   errs() << "- v. register: " << printReg(VReg, TRI) << '\n';
     531           0 : }
     532             : 
     533           0 : void MachineVerifier::report_context_vreg_regunit(unsigned VRegOrUnit) const {
     534           0 :   if (TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) {
     535           0 :     report_context_vreg(VRegOrUnit);
     536             :   } else {
     537           0 :     errs() << "- regunit:     " << printRegUnit(VRegOrUnit, TRI) << '\n';
     538             :   }
     539           0 : }
     540             : 
     541           0 : void MachineVerifier::report_context_lanemask(LaneBitmask LaneMask) const {
     542           0 :   errs() << "- lanemask:    " << PrintLaneMask(LaneMask) << '\n';
     543           0 : }
     544             : 
     545     1799607 : void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
     546     1799607 :   BBInfo &MInfo = MBBInfoMap[MBB];
     547     1799607 :   if (!MInfo.reachable) {
     548     1663057 :     MInfo.reachable = true;
     549     1663057 :     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
     550     2123031 :            SuE = MBB->succ_end(); SuI != SuE; ++SuI)
     551      459974 :       markReachable(*SuI);
     552             :   }
     553     1799607 : }
     554             : 
     555     1339652 : void MachineVerifier::visitMachineFunctionBefore() {
     556     1339652 :   lastIndex = SlotIndex();
     557     6698260 :   regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs()
     558     1339912 :                                            : TRI->getReservedRegs(*MF);
     559             : 
     560     2679304 :   if (!MF->empty())
     561     1339633 :     markReachable(&MF->front());
     562             : 
     563             :   // Build a set of the basic blocks in the function.
     564     1339652 :   FunctionBlocks.clear();
     565     4343640 :   for (const auto &MBB : *MF) {
     566     1664336 :     FunctionBlocks.insert(&MBB);
     567     3328672 :     BBInfo &MInfo = MBBInfoMap[&MBB];
     568             : 
     569     1664336 :     MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end());
     570     3328672 :     if (MInfo.Preds.size() != MBB.pred_size())
     571           0 :       report("MBB has duplicate entries in its predecessor list.", &MBB);
     572             : 
     573     1664336 :     MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end());
     574     3328672 :     if (MInfo.Succs.size() != MBB.succ_size())
     575           0 :       report("MBB has duplicate entries in its successor list.", &MBB);
     576             :   }
     577             : 
     578             :   // Check that the register use lists are sane.
     579     1339652 :   MRI->verifyUseLists();
     580             : 
     581     2679304 :   if (!MF->empty())
     582     1339633 :     verifyStackFrame();
     583     1339652 : }
     584             : 
     585             : // Does iterator point to a and b as the first two elements?
     586             : static bool matchPair(MachineBasicBlock::const_succ_iterator i,
     587             :                       const MachineBasicBlock *a, const MachineBasicBlock *b) {
     588      137018 :   if (*i == a)
     589       73010 :     return *++i == b;
     590       64008 :   if (*i == b)
     591       64008 :     return *++i == a;
     592             :   return false;
     593             : }
     594             : 
     595             : void
     596     1664336 : MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
     597     1664336 :   FirstTerminator = nullptr;
     598             : 
     599     1664336 :   if (!MF->getProperties().hasProperty(
     600     2312961 :       MachineFunctionProperties::Property::NoPHIs) && MRI->tracksLiveness()) {
     601             :     // If this block has allocatable physical registers live-in, check that
     602             :     // it is an entry block or landing pad.
     603     1460590 :     for (const auto &LI : MBB->liveins()) {
     604     1622302 :       if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() &&
     605     1620674 :           MBB->getIterator() != MBB->getParent()->begin()) {
     606           0 :         report("MBB has allocatable live-in, but isn't entry or landing-pad.", MBB);
     607             :       }
     608             :     }
     609             :   }
     610             : 
     611             :   // Count the number of landing pad successors.
     612             :   SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
     613             :   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
     614     2124567 :        E = MBB->succ_end(); I != E; ++I) {
     615      460231 :     if ((*I)->isEHPad())
     616        6876 :       LandingPadSuccs.insert(*I);
     617      460231 :     if (!FunctionBlocks.count(*I))
     618           0 :       report("MBB has successor that isn't part of the function.", MBB);
     619      920462 :     if (!MBBInfoMap[*I].Preds.count(MBB)) {
     620           0 :       report("Inconsistent CFG", MBB);
     621           0 :       errs() << "MBB is not in the predecessor list of the successor "
     622           0 :              << printMBBReference(*(*I)) << ".\n";
     623             :     }
     624             :   }
     625             : 
     626             :   // Check the predecessor list.
     627             :   for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
     628     2124567 :        E = MBB->pred_end(); I != E; ++I) {
     629      460231 :     if (!FunctionBlocks.count(*I))
     630           0 :       report("MBB has predecessor that isn't part of the function.", MBB);
     631      920462 :     if (!MBBInfoMap[*I].Succs.count(MBB)) {
     632           0 :       report("Inconsistent CFG", MBB);
     633           0 :       errs() << "MBB is not in the successor list of the predecessor "
     634           0 :              << printMBBReference(*(*I)) << ".\n";
     635             :     }
     636             :   }
     637             : 
     638     1664336 :   const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
     639     1664336 :   const BasicBlock *BB = MBB->getBasicBlock();
     640     1664336 :   const Function &F = MF->getFunction();
     641     1664551 :   if (LandingPadSuccs.size() > 1 &&
     642         215 :       !(AsmInfo &&
     643         215 :         AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
     644     1664336 :         BB && isa<SwitchInst>(BB->getTerminator())) &&
     645         215 :       !isFuncletEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
     646           0 :     report("MBB has more than one landing pad successor", MBB);
     647             : 
     648             :   // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
     649     1664336 :   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     650             :   SmallVector<MachineOperand, 4> Cond;
     651     3328672 :   if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB,
     652     1664336 :                           Cond)) {
     653             :     // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
     654             :     // check whether its answers match up with reality.
     655      311005 :     if (!TBB && !FBB) {
     656             :       // Block falls through to its successor.
     657      138642 :       MachineFunction::const_iterator MBBI = MBB->getIterator();
     658             :       ++MBBI;
     659      277284 :       if (MBBI == MF->end()) {
     660             :         // It's possible that the block legitimately ends with a noreturn
     661             :         // call or an unreachable, in which case it won't actually fall
     662             :         // out the bottom of the function.
     663      221436 :       } else if (MBB->succ_size() == LandingPadSuccs.size()) {
     664             :         // It's possible that the block legitimately ends with a noreturn
     665             :         // call or an unreachable, in which case it won't actuall fall
     666             :         // out of the block.
     667      101754 :       } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
     668           0 :         report("MBB exits via unconditional fall-through but doesn't have "
     669             :                "exactly one CFG successor!", MBB);
     670      101754 :       } else if (!MBB->isSuccessor(&*MBBI)) {
     671           0 :         report("MBB exits via unconditional fall-through but its successor "
     672             :                "differs from its CFG successor!", MBB);
     673             :       }
     674      262218 :       if (!MBB->empty() && MBB->back().isBarrier() &&
     675          36 :           !TII->isPredicated(MBB->back())) {
     676           0 :         report("MBB exits via unconditional fall-through but ends with a "
     677             :                "barrier instruction!", MBB);
     678             :       }
     679      138642 :       if (!Cond.empty()) {
     680           0 :         report("MBB exits via unconditional fall-through but has a condition!",
     681             :                MBB);
     682             :       }
     683      172363 :     } else if (TBB && !FBB && Cond.empty()) {
     684             :       // Block unconditionally branches somewhere.
     685             :       // If the block has exactly one successor, that happens to be a
     686             :       // landingpad, accept it as valid control flow.
     687       70498 :       if (MBB->succ_size() != 1+LandingPadSuccs.size() &&
     688           0 :           (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 ||
     689       35249 :            *MBB->succ_begin() != *LandingPadSuccs.begin())) {
     690           0 :         report("MBB exits via unconditional branch but doesn't have "
     691             :                "exactly one CFG successor!", MBB);
     692       35249 :       } else if (!MBB->isSuccessor(TBB)) {
     693           0 :         report("MBB exits via unconditional branch but the CFG "
     694             :                "successor doesn't match the actual successor!", MBB);
     695             :       }
     696       35249 :       if (MBB->empty()) {
     697           0 :         report("MBB exits via unconditional branch but doesn't contain "
     698             :                "any instructions!", MBB);
     699       35249 :       } else if (!MBB->back().isBarrier()) {
     700           0 :         report("MBB exits via unconditional branch but doesn't end with a "
     701             :                "barrier instruction!", MBB);
     702       35249 :       } else if (!MBB->back().isTerminator()) {
     703           0 :         report("MBB exits via unconditional branch but the branch isn't a "
     704             :                "terminator instruction!", MBB);
     705             :       }
     706      274228 :     } else if (TBB && !FBB && !Cond.empty()) {
     707             :       // Block conditionally branches somewhere, otherwise falls through.
     708       64940 :       MachineFunction::const_iterator MBBI = MBB->getIterator();
     709             :       ++MBBI;
     710      129880 :       if (MBBI == MF->end()) {
     711           0 :         report("MBB conditionally falls through out of function!", MBB);
     712       64940 :       } else if (MBB->succ_size() == 1) {
     713             :         // A conditional branch with only one successor is weird, but allowed.
     714          49 :         if (&*MBBI != TBB)
     715           0 :           report("MBB exits via conditional branch/fall-through but only has "
     716             :                  "one CFG successor!", MBB);
     717          49 :         else if (TBB != *MBB->succ_begin())
     718           0 :           report("MBB exits via conditional branch/fall-through but the CFG "
     719             :                  "successor don't match the actual successor!", MBB);
     720       64891 :       } else if (MBB->succ_size() != 2) {
     721           0 :         report("MBB exits via conditional branch/fall-through but doesn't have "
     722             :                "exactly two CFG successors!", MBB);
     723       64891 :       } else if (!matchPair(MBB->succ_begin(), TBB, &*MBBI)) {
     724           0 :         report("MBB exits via conditional branch/fall-through but the CFG "
     725             :                "successors don't match the actual successors!", MBB);
     726             :       }
     727       64940 :       if (MBB->empty()) {
     728           0 :         report("MBB exits via conditional branch/fall-through but doesn't "
     729             :                "contain any instructions!", MBB);
     730       64940 :       } else if (MBB->back().isBarrier()) {
     731           0 :         report("MBB exits via conditional branch/fall-through but ends with a "
     732             :                "barrier instruction!", MBB);
     733       64940 :       } else if (!MBB->back().isTerminator()) {
     734           0 :         report("MBB exits via conditional branch/fall-through but the branch "
     735             :                "isn't a terminator instruction!", MBB);
     736             :       }
     737      144348 :     } else if (TBB && FBB) {
     738             :       // Block conditionally branches somewhere, otherwise branches
     739             :       // somewhere else.
     740       72174 :       if (MBB->succ_size() == 1) {
     741             :         // A conditional branch with only one successor is weird, but allowed.
     742          47 :         if (FBB != TBB)
     743           0 :           report("MBB exits via conditional branch/branch through but only has "
     744             :                  "one CFG successor!", MBB);
     745          47 :         else if (TBB != *MBB->succ_begin())
     746           0 :           report("MBB exits via conditional branch/branch through but the CFG "
     747             :                  "successor don't match the actual successor!", MBB);
     748       72127 :       } else if (MBB->succ_size() != 2) {
     749           0 :         report("MBB exits via conditional branch/branch but doesn't have "
     750             :                "exactly two CFG successors!", MBB);
     751       72127 :       } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
     752           0 :         report("MBB exits via conditional branch/branch but the CFG "
     753             :                "successors don't match the actual successors!", MBB);
     754             :       }
     755       72174 :       if (MBB->empty()) {
     756           0 :         report("MBB exits via conditional branch/branch but doesn't "
     757             :                "contain any instructions!", MBB);
     758       72174 :       } else if (!MBB->back().isBarrier()) {
     759           0 :         report("MBB exits via conditional branch/branch but doesn't end with a "
     760             :                "barrier instruction!", MBB);
     761       72174 :       } else if (!MBB->back().isTerminator()) {
     762           0 :         report("MBB exits via conditional branch/branch but the branch "
     763             :                "isn't a terminator instruction!", MBB);
     764             :       }
     765       72174 :       if (Cond.empty()) {
     766           0 :         report("MBB exits via conditinal branch/branch but there's no "
     767             :                "condition!", MBB);
     768             :       }
     769             :     } else {
     770           0 :       report("AnalyzeBranch returned invalid data!", MBB);
     771             :     }
     772             :   }
     773             : 
     774             :   regsLive.clear();
     775     3328672 :   if (MRI->tracksLiveness()) {
     776     4308314 :     for (const auto &LI : MBB->liveins()) {
     777     2665475 :       if (!TargetRegisterInfo::isPhysicalRegister(LI.PhysReg)) {
     778           0 :         report("MBB live-in list contains non-physical register", MBB);
     779           0 :         continue;
     780             :       }
     781     2665475 :       for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true);
     782     8809876 :            SubRegs.isValid(); ++SubRegs)
     783    12288802 :         regsLive.insert(*SubRegs);
     784             :     }
     785             :   }
     786             : 
     787     1664336 :   const MachineFrameInfo &MFI = MF->getFrameInfo();
     788     1664336 :   BitVector PR = MFI.getPristineRegs(*MF);
     789    14442212 :   for (unsigned I : PR.set_bits()) {
     790    12777876 :     for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
     791    34186243 :          SubRegs.isValid(); ++SubRegs)
     792    42816734 :       regsLive.insert(*SubRegs);
     793             :   }
     794             : 
     795             :   regsKilled.clear();
     796             :   regsDefined.clear();
     797             : 
     798     1664336 :   if (Indexes)
     799      238996 :     lastIndex = Indexes->getMBBStartIdx(MBB);
     800     1664336 : }
     801             : 
     802             : // This function gets called for all bundle headers, including normal
     803             : // stand-alone unbundled instructions.
     804    20387577 : void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
     805    20387577 :   if (Indexes && Indexes->hasIndex(*MI)) {
     806     2582725 :     SlotIndex idx = Indexes->getInstructionIndex(*MI);
     807     2582725 :     if (!(idx > lastIndex)) {
     808           0 :       report("Instruction index out of order", MI);
     809           0 :       errs() << "Last instruction was at " << lastIndex << '\n';
     810             :     }
     811     2582725 :     lastIndex = idx;
     812             :   }
     813             : 
     814             :   // Ensure non-terminators don't follow terminators.
     815             :   // Ignore predicated terminators formed by if conversion.
     816             :   // FIXME: If conversion shouldn't need to violate this rule.
     817    20387577 :   if (MI->isTerminator() && !TII->isPredicated(*MI)) {
     818     1613545 :     if (!FirstTerminator)
     819     1533042 :       FirstTerminator = MI;
     820    18774032 :   } else if (FirstTerminator) {
     821           0 :     report("Non-terminator instruction after the first terminator", MI);
     822           0 :     errs() << "First terminator was:\t" << *FirstTerminator;
     823             :   }
     824    20387577 : }
     825             : 
     826             : // The operands on an INLINEASM instruction must follow a template.
     827             : // Verify that the flag operands make sense.
     828      109711 : void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
     829             :   // The first two operands on INLINEASM are the asm string and global flags.
     830      109711 :   if (MI->getNumOperands() < 2) {
     831           0 :     report("Too few operands on inline asm", MI);
     832           0 :     return;
     833             :   }
     834      219422 :   if (!MI->getOperand(0).isSymbol())
     835           0 :     report("Asm string must be an external symbol", MI);
     836      219422 :   if (!MI->getOperand(1).isImm())
     837           0 :     report("Asm flags must be an immediate", MI);
     838             :   // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
     839             :   // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16,
     840             :   // and Extra_IsConvergent = 32.
     841      109711 :   if (!isUInt<6>(MI->getOperand(1).getImm()))
     842           0 :     report("Unknown asm flags", &MI->getOperand(1), 1);
     843             : 
     844             :   static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed");
     845             : 
     846             :   unsigned OpNo = InlineAsm::MIOp_FirstOperand;
     847             :   unsigned NumOps;
     848      508894 :   for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
     849      399732 :     const MachineOperand &MO = MI->getOperand(OpNo);
     850             :     // There may be implicit ops after the fixed operands.
     851      399732 :     if (!MO.isImm())
     852             :       break;
     853      798366 :     NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
     854             :   }
     855             : 
     856      109711 :   if (OpNo > MI->getNumOperands())
     857           0 :     report("Missing operands in last group", MI);
     858             : 
     859             :   // An optional MDNode follows the groups.
     860      110260 :   if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
     861         234 :     ++OpNo;
     862             : 
     863             :   // All trailing operands must be implicit registers.
     864      110581 :   for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
     865         435 :     const MachineOperand &MO = MI->getOperand(OpNo);
     866         870 :     if (!MO.isReg() || !MO.isImplicit())
     867           0 :       report("Expected implicit register after groups", &MO, OpNo);
     868             :   }
     869             : }
     870             : 
     871    20410867 : void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
     872    20410867 :   const MCInstrDesc &MCID = MI->getDesc();
     873    40821734 :   if (MI->getNumOperands() < MCID.getNumOperands()) {
     874          10 :     report("Too few operands", MI);
     875          20 :     errs() << MCID.getNumOperands() << " operands expected, but "
     876          20 :         << MI->getNumOperands() << " given.\n";
     877             :   }
     878             : 
     879      154764 :   if (MI->isPHI() && MF->getProperties().hasProperty(
     880             :           MachineFunctionProperties::Property::NoPHIs))
     881           0 :     report("Found PHI instruction with NoPHIs property set", MI);
     882             : 
     883             :   // Check the tied operands.
     884    20410867 :   if (MI->isInlineAsm())
     885      109711 :     verifyInlineAsm(MI);
     886             : 
     887             :   // Check the MachineMemOperands for basic consistency.
     888    24894865 :   for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
     889    45305732 :        E = MI->memoperands_end(); I != E; ++I) {
     890     8967996 :     if ((*I)->isLoad() && !MI->mayLoad())
     891           0 :       report("Missing mayLoad flag", MI);
     892     8967996 :     if ((*I)->isStore() && !MI->mayStore())
     893           0 :       report("Missing mayStore flag", MI);
     894             :   }
     895             : 
     896             :   // Debug values must not have a slot index.
     897             :   // Other instructions must have one, unless they are inside a bundle.
     898    20410867 :   if (LiveInts) {
     899     2189616 :     bool mapped = !LiveInts->isNotInMIMap(*MI);
     900     2189616 :     if (MI->isDebugValue()) {
     901         103 :       if (mapped)
     902           0 :         report("Debug instruction has a slot index", MI);
     903     2189513 :     } else if (MI->isInsideBundle()) {
     904           7 :       if (mapped)
     905           0 :         report("Instruction inside bundle has a slot index", MI);
     906             :     } else {
     907     2189506 :       if (!mapped)
     908           0 :         report("Missing slot index", MI);
     909             :     }
     910             :   }
     911             : 
     912             :   // Check types.
     913    40821734 :   if (isPreISelGenericOpcode(MCID.getOpcode())) {
     914        7355 :     if (isFunctionSelected)
     915           1 :       report("Unexpected generic instruction in a Selected function", MI);
     916             : 
     917             :     // Generic instructions specify equality constraints between some
     918             :     // of their operands. Make sure these are consistent.
     919             :     SmallVector<LLT, 4> Types;
     920       66349 :     for (unsigned i = 0; i < MCID.getNumOperands(); ++i) {
     921       34426 :       if (!MCID.OpInfo[i].isGenericType())
     922        2058 :         continue;
     923       15155 :       size_t TypeIdx = MCID.OpInfo[i].getGenericTypeIndex();
     924       30310 :       Types.resize(std::max(TypeIdx + 1, Types.size()));
     925             : 
     926       30310 :       LLT OpTy = MRI->getType(MI->getOperand(i).getReg());
     927       15155 :       if (Types[TypeIdx].isValid() && Types[TypeIdx] != OpTy)
     928           0 :         report("type mismatch in generic instruction", MI);
     929       15155 :       Types[TypeIdx] = OpTy;
     930             :     }
     931             :   }
     932             : 
     933             :   // Generic opcodes must not have physical register operands.
     934    40821734 :   if (isPreISelGenericOpcode(MCID.getOpcode())) {
     935       43699 :     for (auto &Op : MI->operands()) {
     936       34142 :       if (Op.isReg() && TargetRegisterInfo::isPhysicalRegister(Op.getReg()))
     937           0 :         report("Generic instruction cannot have physical register", MI);
     938             :     }
     939             :   }
     940             : 
     941    20410867 :   StringRef ErrorInfo;
     942    20410867 :   if (!TII->verifyInstruction(*MI, ErrorInfo))
     943          23 :     report(ErrorInfo.data(), MI);
     944             : 
     945             :   // Verify properties of various specific instruction types
     946    40821734 :   switch(MI->getOpcode()) {
     947             :   default:
     948             :     break;
     949        1107 :   case TargetOpcode::G_LOAD:
     950             :   case TargetOpcode::G_STORE:
     951             :     // Generic loads and stores must have a single MachineMemOperand
     952             :     // describing that access.
     953        1107 :     if (!MI->hasOneMemOperand())
     954           0 :       report("Generic instruction accessing memory must have one mem operand",
     955             :              MI);
     956             :     break;
     957          71 :   case TargetOpcode::G_PHI: {
     958          71 :     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
     959         142 :     if (!DstTy.isValid() ||
     960         142 :         !std::all_of(MI->operands_begin() + 1, MI->operands_end(),
     961         571 :                      [this, &DstTy](const MachineOperand &MO) {
     962         285 :                        if (!MO.isReg())
     963             :                          return true;
     964         143 :                        LLT Ty = MRI->getType(MO.getReg());
     965         143 :                        if (!Ty.isValid() || (Ty != DstTy))
     966             :                          return false;
     967             :                        return true;
     968             :                      }))
     969           1 :       report("Generic Instruction G_PHI has operands with incompatible/missing "
     970             :              "types",
     971             :              MI);
     972             :     break;
     973             :   }
     974     4239548 :   case TargetOpcode::COPY: {
     975     4239548 :     if (foundErrors)
     976             :       break;
     977     4239516 :     const MachineOperand &DstOp = MI->getOperand(0);
     978             :     const MachineOperand &SrcOp = MI->getOperand(1);
     979     4239516 :     LLT DstTy = MRI->getType(DstOp.getReg());
     980     4239516 :     LLT SrcTy = MRI->getType(SrcOp.getReg());
     981     4242582 :     if (SrcTy.isValid() && DstTy.isValid()) {
     982             :       // If both types are valid, check that the types are the same.
     983             :       if (SrcTy != DstTy) {
     984           1 :         report("Copy Instruction is illegal with mismatching types", MI);
     985           3 :         errs() << "Def = " << DstTy << ", Src = " << SrcTy << "\n";
     986             :       }
     987             :     }
     988     8475966 :     if (SrcTy.isValid() || DstTy.isValid()) {
     989             :       // If one of them have valid types, let's just check they have the same
     990             :       // size.
     991        7624 :       unsigned SrcSize = TRI->getRegSizeInBits(SrcOp.getReg(), *MRI);
     992        7624 :       unsigned DstSize = TRI->getRegSizeInBits(DstOp.getReg(), *MRI);
     993             :       assert(SrcSize && "Expecting size here");
     994             :       assert(DstSize && "Expecting size here");
     995        7624 :       if (SrcSize != DstSize)
     996           2 :         if (!DstOp.getSubReg() && !SrcOp.getSubReg()) {
     997           1 :           report("Copy Instruction is illegal with mismatching sizes", MI);
     998           2 :           errs() << "Def Size = " << DstSize << ", Src Size = " << SrcSize
     999           1 :                  << "\n";
    1000             :         }
    1001             :     }
    1002             :     break;
    1003             :   }
    1004        2583 :   case TargetOpcode::STATEPOINT:
    1005        5166 :     if (!MI->getOperand(StatepointOpers::IDPos).isImm() ||
    1006        5166 :         !MI->getOperand(StatepointOpers::NBytesPos).isImm() ||
    1007             :         !MI->getOperand(StatepointOpers::NCallArgsPos).isImm())
    1008           0 :       report("meta operands to STATEPOINT not constant!", MI);
    1009             :     break;
    1010             : 
    1011             :     auto VerifyStackMapConstant = [&](unsigned Offset) {
    1012             :       if (!MI->getOperand(Offset).isImm() ||
    1013             :           MI->getOperand(Offset).getImm() != StackMaps::ConstantOp || 
    1014             :           !MI->getOperand(Offset + 1).isImm()) 
    1015             :         report("stack map constant to STATEPOINT not well formed!", MI);
    1016             :     };
    1017             :     const unsigned VarStart = StatepointOpers(MI).getVarIdx();
    1018             :     VerifyStackMapConstant(VarStart + StatepointOpers::CCOffset);
    1019             :     VerifyStackMapConstant(VarStart + StatepointOpers::FlagsOffset);
    1020             :     VerifyStackMapConstant(VarStart + StatepointOpers::NumDeoptOperandsOffset);
    1021             : 
    1022             :     // TODO: verify we have properly encoded deopt arguments
    1023             :   };
    1024    20410867 : }
    1025             : 
    1026             : void
    1027    82883008 : MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
    1028    82883008 :   const MachineInstr *MI = MO->getParent();
    1029    82883008 :   const MCInstrDesc &MCID = MI->getDesc();
    1030    82883008 :   unsigned NumDefs = MCID.getNumDefs();
    1031    82883008 :   if (MCID.getOpcode() == TargetOpcode::PATCHPOINT)
    1032          39 :     NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0;
    1033             : 
    1034             :   // The first MCID.NumDefs operands must be explicit register defines
    1035    82883008 :   if (MONum < NumDefs) {
    1036    16398848 :     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
    1037    16398848 :     if (!MO->isReg())
    1038           0 :       report("Explicit definition must be a register", MO, MONum);
    1039    16398848 :     else if (!MO->isDef() && !MCOI.isOptionalDef())
    1040           0 :       report("Explicit definition marked as use", MO, MONum);
    1041    16398848 :     else if (MO->isImplicit())
    1042           0 :       report("Explicit definition marked as implicit", MO, MONum);
    1043   132968320 :   } else if (MONum < MCID.getNumOperands()) {
    1044    50144203 :     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
    1045             :     // Don't check if it's the last operand in a variadic instruction. See,
    1046             :     // e.g., LDM_RET in the arm back end.
    1047    73542609 :     if (MO->isReg() &&
    1048     1605730 :         !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
    1049    22660764 :       if (MO->isDef() && !MCOI.isOptionalDef())
    1050           0 :         report("Explicit operand marked as def", MO, MONum);
    1051    22660764 :       if (MO->isImplicit())
    1052           0 :         report("Explicit operand marked as implicit", MO, MONum);
    1053             :     }
    1054             : 
    1055    50144203 :     int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
    1056             :     if (TiedTo != -1) {
    1057      574718 :       if (!MO->isReg())
    1058           0 :         report("Tied use must be a register", MO, MONum);
    1059      574718 :       else if (!MO->isTied())
    1060           0 :         report("Operand should be tied", MO, MONum);
    1061      574718 :       else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
    1062           0 :         report("Tied def doesn't match MCInstrDesc", MO, MONum);
    1063     1149436 :       else if (TargetRegisterInfo::isPhysicalRegister(MO->getReg())) {
    1064      318119 :         const MachineOperand &MOTied = MI->getOperand(TiedTo);
    1065      318119 :         if (!MOTied.isReg())
    1066           0 :           report("Tied counterpart must be a register", &MOTied, TiedTo);
    1067      636238 :         else if (TargetRegisterInfo::isPhysicalRegister(MOTied.getReg()) &&
    1068             :                  MO->getReg() != MOTied.getReg())
    1069           1 :           report("Tied physical registers must match.", &MOTied, TiedTo);
    1070             :       }
    1071    72393173 :     } else if (MO->isReg() && MO->isTied())
    1072           0 :       report("Explicit operand should not be tied", MO, MONum);
    1073             :   } else {
    1074             :     // ARM adds %reg0 operands to indicate predicates. We'll allow that.
    1075    31424954 :     if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
    1076           0 :       report("Extra explicit operand on non-variadic instruction", MO, MONum);
    1077             :   }
    1078             : 
    1079    82883008 :   switch (MO->getType()) {
    1080    53064610 :   case MachineOperand::MO_Register: {
    1081    53064610 :     const unsigned Reg = MO->getReg();
    1082    53064610 :     if (!Reg)
    1083    12584027 :       return;
    1084   154046882 :     if (MRI->tracksLiveness() && !MI->isDebugValue())
    1085    50871534 :       checkLiveness(MO, MONum);
    1086             : 
    1087             :     // Verify the consistency of tied operands.
    1088    51587070 :     if (MO->isTied()) {
    1089     1161618 :       unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
    1090     1161618 :       const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
    1091     1161618 :       if (!OtherMO.isReg())
    1092           0 :         report("Must be tied to a register", MO, MONum);
    1093     1161618 :       if (!OtherMO.isTied())
    1094           0 :         report("Missing tie flags on tied operand", MO, MONum);
    1095     1161618 :       if (MI->findTiedOperandIdx(OtherIdx) != MONum)
    1096           0 :         report("Inconsistent tie links", MO, MONum);
    1097     2323236 :       if (MONum < MCID.getNumDefs()) {
    1098     1151058 :         if (OtherIdx < MCID.getNumOperands()) {
    1099             :           if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
    1100           0 :             report("Explicit def tied to explicit use without tie constraint",
    1101             :                    MO, MONum);
    1102             :         } else {
    1103         811 :           if (!OtherMO.isImplicit())
    1104           0 :             report("Explicit def should be tied to implicit use", MO, MONum);
    1105             :         }
    1106             :       }
    1107             :     }
    1108             : 
    1109             :     // Verify two-address constraints after leaving SSA form.
    1110             :     unsigned DefIdx;
    1111    96418906 :     if (!MRI->isSSA() && MO->isUse() &&
    1112    69490547 :         MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
    1113      748454 :         Reg != MI->getOperand(DefIdx).getReg())
    1114           0 :       report("Two-address instruction operands must be identical", MO, MONum);
    1115             : 
    1116             :     // Check register classes.
    1117             :     unsigned SubIdx = MO->getSubReg();
    1118             : 
    1119    51587070 :     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    1120    29890354 :       if (SubIdx) {
    1121           0 :         report("Illegal subregister index for physical register", MO, MONum);
    1122           0 :         return;
    1123             :       }
    1124    59780708 :       if (MONum < MCID.getNumOperands()) {
    1125    18164730 :         if (const TargetRegisterClass *DRC =
    1126    18164730 :               TII->getRegClass(MCID, MONum, TRI, *MF)) {
    1127    30901066 :           if (!DRC->contains(Reg)) {
    1128           0 :             report("Illegal physical register for instruction", MO, MONum);
    1129           0 :             errs() << printReg(Reg, TRI) << " is not a "
    1130           0 :                    << TRI->getRegClassName(DRC) << " register.\n";
    1131             :           }
    1132             :         }
    1133             :       }
    1134    29890354 :       if (MO->isRenamable()) {
    1135    27356833 :         if ((MO->isDef() && MI->hasExtraDefRegAllocReq()) ||
    1136     5962622 :             (MO->isUse() && MI->hasExtraSrcRegAllocReq()))
    1137           0 :           report("Illegal isRenamable setting for opcode with extra regalloc "
    1138             :                  "requirements",
    1139             :                  MO, MONum);
    1140    22212970 :         if (MRI->isReserved(Reg))
    1141           0 :           report("isRenamable set on reserved register", MO, MONum);
    1142             :         return;
    1143             :       }
    1144             :     } else {
    1145             :       // Virtual register.
    1146    21696716 :       const TargetRegisterClass *RC = MRI->getRegClassOrNull(Reg);
    1147    21680613 :       if (!RC) {
    1148             :         // This is a generic virtual register.
    1149             : 
    1150             :         // If we're post-Select, we can't have gvregs anymore.
    1151       23998 :         if (isFunctionSelected) {
    1152           1 :           report("Generic virtual register invalid in a Selected function",
    1153             :                  MO, MONum);
    1154           3 :           return;
    1155             :         }
    1156             : 
    1157             :         // The gvreg must have a type and it must not have a SubIdx.
    1158       23997 :         LLT Ty = MRI->getType(Reg);
    1159       23997 :         if (!Ty.isValid()) {
    1160           0 :           report("Generic virtual register must have a valid type", MO,
    1161             :                  MONum);
    1162           0 :           return;
    1163             :         }
    1164             : 
    1165       23997 :         const RegisterBank *RegBank = MRI->getRegBankOrNull(Reg);
    1166             : 
    1167             :         // If we're post-RegBankSelect, the gvreg must have a bank.
    1168       16102 :         if (!RegBank && isFunctionRegBankSelected) {
    1169           1 :           report("Generic virtual register must have a bank in a "
    1170             :                  "RegBankSelected function",
    1171             :                  MO, MONum);
    1172           1 :           return;
    1173             :         }
    1174             : 
    1175             :         // Make sure the register fits into its register bank if any.
    1176       35701 :         if (RegBank && Ty.isValid() &&
    1177       11705 :             RegBank->getSize() < Ty.getSizeInBits()) {
    1178           0 :           report("Register bank is too small for virtual register", MO,
    1179             :                  MONum);
    1180           0 :           errs() << "Register bank " << RegBank->getName() << " too small("
    1181           0 :                  << RegBank->getSize() << ") to fit " << Ty.getSizeInBits()
    1182           0 :                  << "-bits\n";
    1183           0 :           return;
    1184             :         }
    1185       23996 :         if (SubIdx)  {
    1186           0 :           report("Generic virtual register does not subregister index", MO,
    1187             :                  MONum);
    1188           0 :           return;
    1189             :         }
    1190             : 
    1191             :         // If this is a target specific instruction and this operand
    1192             :         // has register class constraint, the virtual register must
    1193             :         // comply to it.
    1194       32032 :         if (!isPreISelGenericOpcode(MCID.getOpcode()) &&
    1195       31989 :             MONum < MCID.getNumOperands() &&
    1196        7993 :             TII->getRegClass(MCID, MONum, TRI, *MF)) {
    1197           0 :           report("Virtual register does not match instruction constraint", MO,
    1198             :                  MONum);
    1199           0 :           errs() << "Expect register class "
    1200           0 :                  << TRI->getRegClassName(
    1201           0 :                         TII->getRegClass(MCID, MONum, TRI, *MF))
    1202           0 :                  << " but got nothing\n";
    1203           0 :           return;
    1204             :         }
    1205             : 
    1206       23996 :         break;
    1207             :       }
    1208    21672718 :       if (SubIdx) {
    1209             :         const TargetRegisterClass *SRC =
    1210     2089553 :           TRI->getSubClassWithSubReg(RC, SubIdx);
    1211     2089553 :         if (!SRC) {
    1212           0 :           report("Invalid subregister index for virtual register", MO, MONum);
    1213           0 :           errs() << "Register class " << TRI->getRegClassName(RC)
    1214           0 :               << " does not support subreg index " << SubIdx << "\n";
    1215           0 :           return;
    1216             :         }
    1217     2089553 :         if (RC != SRC) {
    1218           0 :           report("Invalid register class for subregister index", MO, MONum);
    1219           0 :           errs() << "Register class " << TRI->getRegClassName(RC)
    1220           0 :               << " does not fully support subreg index " << SubIdx << "\n";
    1221           0 :           return;
    1222             :         }
    1223             :       }
    1224    43345436 :       if (MONum < MCID.getNumOperands()) {
    1225    20133647 :         if (const TargetRegisterClass *DRC =
    1226    20133647 :               TII->getRegClass(MCID, MONum, TRI, *MF)) {
    1227    12467566 :           if (SubIdx) {
    1228             :             const TargetRegisterClass *SuperRC =
    1229      832266 :                 TRI->getLargestLegalSuperClass(RC, *MF);
    1230      832266 :             if (!SuperRC) {
    1231           0 :               report("No largest legal super class exists.", MO, MONum);
    1232           0 :               return;
    1233             :             }
    1234      832266 :             DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
    1235      832266 :             if (!DRC) {
    1236           0 :               report("No matching super-reg register class.", MO, MONum);
    1237           0 :               return;
    1238             :             }
    1239             :           }
    1240    12467566 :           if (!RC->hasSuperClassEq(DRC)) {
    1241           0 :             report("Illegal virtual register for instruction", MO, MONum);
    1242           0 :             errs() << "Expected a " << TRI->getRegClassName(DRC)
    1243           0 :                 << " register, but got a " << TRI->getRegClassName(RC)
    1244           0 :                 << " register\n";
    1245             :           }
    1246             :         }
    1247             :       }
    1248             :     }
    1249             :     break;
    1250             :   }
    1251             : 
    1252      187321 :   case MachineOperand::MO_RegisterMask:
    1253      187321 :     regMasks.push_back(MO->getRegMask());
    1254      187321 :     break;
    1255             : 
    1256             :   case MachineOperand::MO_MachineBasicBlock:
    1257      157064 :     if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
    1258           0 :       report("PHI operand is not in the CFG", MO, MONum);
    1259             :     break;
    1260             : 
    1261      356712 :   case MachineOperand::MO_FrameIndex:
    1262      434208 :     if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
    1263      369089 :         LiveInts && !LiveInts->isNotInMIMap(*MI)) {
    1264        4855 :       int FI = MO->getIndex();
    1265        4855 :       LiveInterval &LI = LiveStks->getInterval(FI);
    1266        4855 :       SlotIndex Idx = LiveInts->getInstructionIndex(*MI);
    1267             : 
    1268        4855 :       bool stores = MI->mayStore();
    1269        4855 :       bool loads = MI->mayLoad();
    1270             :       // For a memory-to-memory move, we need to check if the frame
    1271             :       // index is used for storing or loading, by inspecting the
    1272             :       // memory operands.
    1273        4855 :       if (stores && loads) {
    1274          68 :         for (auto *MMO : MI->memoperands()) {
    1275             :           const PseudoSourceValue *PSV = MMO->getPseudoValue();
    1276          27 :           if (PSV == nullptr) continue;
    1277             :           const FixedStackPseudoSourceValue *Value =
    1278             :             dyn_cast<FixedStackPseudoSourceValue>(PSV);
    1279           0 :           if (Value == nullptr) continue;
    1280          27 :           if (Value->getFrameIndex() != FI) continue;
    1281             : 
    1282          48 :           if (MMO->isStore())
    1283             :             loads = false;
    1284             :           else
    1285             :             stores = false;
    1286             :           break;
    1287             :         }
    1288          24 :         if (loads == stores)
    1289           0 :           report("Missing fixed stack memoperand.", MI);
    1290             :       }
    1291        7595 :       if (loads && !LI.liveAt(Idx.getRegSlot(true))) {
    1292           0 :         report("Instruction loads from dead spill slot", MO, MONum);
    1293           0 :         errs() << "Live stack: " << LI << '\n';
    1294             :       }
    1295        6970 :       if (stores && !LI.liveAt(Idx.getRegSlot())) {
    1296           0 :         report("Instruction stores to dead spill slot", MO, MONum);
    1297           0 :         errs() << "Live stack: " << LI << '\n';
    1298             :       }
    1299             :     }
    1300             :     break;
    1301             : 
    1302             :   default:
    1303             :     break;
    1304             :   }
    1305             : }
    1306             : 
    1307     3599496 : void MachineVerifier::checkLivenessAtUse(const MachineOperand *MO,
    1308             :     unsigned MONum, SlotIndex UseIdx, const LiveRange &LR, unsigned VRegOrUnit,
    1309             :     LaneBitmask LaneMask) {
    1310     3599496 :   LiveQueryResult LRQ = LR.Query(UseIdx);
    1311             :   // Check if we have a segment at the use, note however that we only need one
    1312             :   // live subregister range, the others may be dead.
    1313     3599496 :   if (!LRQ.valueIn() && LaneMask.none()) {
    1314           0 :     report("No live segment at use", MO, MONum);
    1315           0 :     report_context_liverange(LR);
    1316           0 :     report_context_vreg_regunit(VRegOrUnit);
    1317           0 :     report_context(UseIdx);
    1318             :   }
    1319     3599496 :   if (MO->isKill() && !LRQ.isKill()) {
    1320           0 :     report("Live range continues after kill flag", MO, MONum);
    1321           0 :     report_context_liverange(LR);
    1322           0 :     report_context_vreg_regunit(VRegOrUnit);
    1323           0 :     if (LaneMask.any())
    1324           0 :       report_context_lanemask(LaneMask);
    1325           0 :     report_context(UseIdx);
    1326             :   }
    1327     3599496 : }
    1328             : 
    1329     2263193 : void MachineVerifier::checkLivenessAtDef(const MachineOperand *MO,
    1330             :     unsigned MONum, SlotIndex DefIdx, const LiveRange &LR, unsigned VRegOrUnit,
    1331             :     LaneBitmask LaneMask) {
    1332     2263193 :   if (const VNInfo *VNI = LR.getVNInfoAt(DefIdx)) {
    1333             :     assert(VNI && "NULL valno is not allowed");
    1334     2263193 :     if (VNI->def != DefIdx) {
    1335           0 :       report("Inconsistent valno->def", MO, MONum);
    1336           0 :       report_context_liverange(LR);
    1337           0 :       report_context_vreg_regunit(VRegOrUnit);
    1338           0 :       if (LaneMask.any())
    1339           0 :         report_context_lanemask(LaneMask);
    1340           0 :       report_context(*VNI);
    1341           0 :       report_context(DefIdx);
    1342             :     }
    1343             :   } else {
    1344           0 :     report("No live segment at def", MO, MONum);
    1345           0 :     report_context_liverange(LR);
    1346           0 :     report_context_vreg_regunit(VRegOrUnit);
    1347           0 :     if (LaneMask.any())
    1348           0 :       report_context_lanemask(LaneMask);
    1349           0 :     report_context(DefIdx);
    1350             :   }
    1351             :   // Check that, if the dead def flag is present, LiveInts agree.
    1352     2263193 :   if (MO->isDead()) {
    1353       29661 :     LiveQueryResult LRQ = LR.Query(DefIdx);
    1354       29661 :     if (!LRQ.isDeadDef()) {
    1355             :       // In case of physregs we can have a non-dead definition on another
    1356             :       // operand.
    1357             :       bool otherDef = false;
    1358           0 :       if (!TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) {
    1359           0 :         const MachineInstr &MI = *MO->getParent();
    1360           0 :         for (const MachineOperand &MO : MI.operands()) {
    1361           0 :           if (!MO.isReg() || !MO.isDef() || MO.isDead())
    1362           0 :             continue;
    1363           0 :           unsigned Reg = MO.getReg();
    1364           0 :           for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
    1365           0 :             if (*Units == VRegOrUnit) {
    1366             :               otherDef = true;
    1367             :               break;
    1368             :             }
    1369             :           }
    1370             :         }
    1371             :       }
    1372             : 
    1373           0 :       if (!otherDef) {
    1374           0 :         report("Live range continues after dead def flag", MO, MONum);
    1375           0 :         report_context_liverange(LR);
    1376           0 :         report_context_vreg_regunit(VRegOrUnit);
    1377           0 :         if (LaneMask.any())
    1378           0 :           report_context_lanemask(LaneMask);
    1379             :       }
    1380             :     }
    1381             :   }
    1382     2263193 : }
    1383             : 
    1384    50871534 : void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
    1385    50871534 :   const MachineInstr *MI = MO->getParent();
    1386    50871534 :   const unsigned Reg = MO->getReg();
    1387             : 
    1388             :   // Both use and def operands can read a register.
    1389             :   if (MO->readsReg()) {
    1390    32220451 :     if (MO->isKill())
    1391     8086690 :       addRegWithSubRegs(regsKilled, Reg);
    1392             : 
    1393             :     // Check that LiveVars knows this kill.
    1394    32221639 :     if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
    1395             :         MO->isKill()) {
    1396         507 :       LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
    1397         507 :       if (!is_contained(VI.Kills, MI))
    1398           0 :         report("Kill missing from LiveVariables", MO, MONum);
    1399             :     }
    1400             : 
    1401             :     // Check LiveInts liveness and kill.
    1402    32220451 :     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
    1403     7247026 :       SlotIndex UseIdx = LiveInts->getInstructionIndex(*MI);
    1404             :       // Check the cached regunit intervals.
    1405     7247026 :       if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
    1406     1333252 :         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
    1407     1029528 :           if (MRI->isReservedRegUnit(*Units))
    1408          34 :             continue;
    1409     1029460 :           if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units))
    1410      434434 :             checkLivenessAtUse(MO, MONum, UseIdx, *LR, *Units);
    1411             :         }
    1412             :       }
    1413             : 
    1414     7247026 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1415     2179886 :         if (LiveInts->hasInterval(Reg)) {
    1416             :           // This is a virtual register interval.
    1417     2179886 :           const LiveInterval &LI = LiveInts->getInterval(Reg);
    1418     2179886 :           checkLivenessAtUse(MO, MONum, UseIdx, LI, Reg);
    1419             : 
    1420     2959830 :           if (LI.hasSubRanges() && !MO->isDef()) {
    1421             :             unsigned SubRegIdx = MO->getSubReg();
    1422             :             LaneBitmask MOMask = SubRegIdx != 0
    1423      287557 :                                ? TRI->getSubRegIndexLaneMask(SubRegIdx)
    1424     1006862 :                                : MRI->getMaxLaneMaskForVReg(Reg);
    1425             :             LaneBitmask LiveInMask;
    1426     2307195 :             for (const LiveInterval::SubRange &SR : LI.subranges()) {
    1427     1803764 :               if ((MOMask & SR.LaneMask).none())
    1428      818588 :                 continue;
    1429      985176 :               checkLivenessAtUse(MO, MONum, UseIdx, SR, Reg, SR.LaneMask);
    1430      985176 :               LiveQueryResult LRQ = SR.Query(UseIdx);
    1431      985176 :               if (LRQ.valueIn())
    1432             :                 LiveInMask |= SR.LaneMask;
    1433             :             }
    1434             :             // At least parts of the register has to be live at the use.
    1435      503431 :             if ((LiveInMask & MOMask).none()) {
    1436           0 :               report("No live subrange at use", MO, MONum);
    1437           0 :               report_context(LI);
    1438           0 :               report_context(UseIdx);
    1439             :             }
    1440             :           }
    1441             :         } else {
    1442           0 :           report("Virtual register has no live interval", MO, MONum);
    1443             :         }
    1444             :       }
    1445             :     }
    1446             : 
    1447             :     // Use of a dead register.
    1448             :     if (!regsLive.count(Reg)) {
    1449    19416532 :       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    1450             :         // Reserved registers may be used even when 'dead'.
    1451     9275329 :         bool Bad = !isReserved(Reg);
    1452             :         // We are fine if just any subregister has a defined value.
    1453     9275329 :         if (Bad) {
    1454     1707293 :           for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid();
    1455             :                ++SubRegs) {
    1456     1769788 :             if (regsLive.count(*SubRegs)) {
    1457             :               Bad = false;
    1458             :               break;
    1459             :             }
    1460             :           }
    1461             :         }
    1462             :         // If there is an additional implicit-use of a super register we stop
    1463             :         // here. By definition we are fine if the super register is not
    1464             :         // (completely) dead, if the complete super register is dead we will
    1465             :         // get a report for its operand.
    1466     9275329 :         if (Bad) {
    1467        2332 :           for (const MachineOperand &MOP : MI->uses()) {
    1468         917 :             if (!MOP.isReg())
    1469          60 :               continue;
    1470         857 :             if (!MOP.isImplicit())
    1471         279 :               continue;
    1472        4042 :             for (MCSubRegIterator SubRegs(MOP.getReg(), TRI); SubRegs.isValid();
    1473             :                  ++SubRegs) {
    1474        3146 :               if (*SubRegs == Reg) {
    1475             :                 Bad = false;
    1476             :                 break;
    1477             :               }
    1478             :             }
    1479             :           }
    1480             :         }
    1481     9275329 :         if (Bad)
    1482           0 :           report("Using an undefined physical register", MO, MONum);
    1483      865874 :       } else if (MRI->def_empty(Reg)) {
    1484           0 :         report("Reading virtual register without a def", MO, MONum);
    1485             :       } else {
    1486      865874 :         BBInfo &MInfo = MBBInfoMap[MI->getParent()];
    1487             :         // We don't know which virtual registers are live in, so only complain
    1488             :         // if vreg was killed in this MBB. Otherwise keep track of vregs that
    1489             :         // must be live in. PHI instructions are handled separately.
    1490             :         if (MInfo.regsKilled.count(Reg))
    1491           0 :           report("Using a killed virtual register", MO, MONum);
    1492      432937 :         else if (!MI->isPHI())
    1493      551860 :           MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
    1494             :       }
    1495             :     }
    1496             :   }
    1497             : 
    1498    50871534 :   if (MO->isDef()) {
    1499             :     // Register defined.
    1500             :     // TODO: verify that earlyclobber ops are not used.
    1501    18770543 :     if (MO->isDead())
    1502     1576556 :       addRegWithSubRegs(regsDead, Reg);
    1503             :     else
    1504    17193987 :       addRegWithSubRegs(regsDefined, Reg);
    1505             : 
    1506             :     // Verify SSA form.
    1507    54576529 :     if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
    1508     7834688 :         std::next(MRI->def_begin(Reg)) != MRI->def_end())
    1509           0 :       report("Multiple virtual register defs in SSA form", MO, MONum);
    1510             : 
    1511             :     // Check LiveInts for a live segment, but only for virtual registers.
    1512    18770543 :     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
    1513     2028045 :       SlotIndex DefIdx = LiveInts->getInstructionIndex(*MI);
    1514             :       DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
    1515             : 
    1516     4056090 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1517     1614182 :         if (LiveInts->hasInterval(Reg)) {
    1518     1614182 :           const LiveInterval &LI = LiveInts->getInterval(Reg);
    1519     1614182 :           checkLivenessAtDef(MO, MONum, DefIdx, LI, Reg);
    1520             : 
    1521     1614182 :           if (LI.hasSubRanges()) {
    1522             :             unsigned SubRegIdx = MO->getSubReg();
    1523             :             LaneBitmask MOMask = SubRegIdx != 0
    1524      436738 :               ? TRI->getSubRegIndexLaneMask(SubRegIdx)
    1525      984244 :               : MRI->getMaxLaneMaskForVReg(Reg);
    1526     2139841 :             for (const LiveInterval::SubRange &SR : LI.subranges()) {
    1527     1647719 :               if ((SR.LaneMask & MOMask).none())
    1528      998708 :                 continue;
    1529      649011 :               checkLivenessAtDef(MO, MONum, DefIdx, SR, Reg, SR.LaneMask);
    1530             :             }
    1531             :           }
    1532             :         } else {
    1533           0 :           report("Virtual register has no Live interval", MO, MONum);
    1534             :         }
    1535             :       }
    1536             :     }
    1537             :   }
    1538    50871534 : }
    1539             : 
    1540             : void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {}
    1541             : 
    1542             : // This function gets called after visiting all instructions in a bundle. The
    1543             : // argument points to the bundle header.
    1544             : // Normal stand-alone instructions are also considered 'bundles', and this
    1545             : // function is called for all of them.
    1546    20387577 : void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
    1547    40775154 :   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
    1548    20387577 :   set_union(MInfo.regsKilled, regsKilled);
    1549             :   set_subtract(regsLive, regsKilled); regsKilled.clear();
    1550             :   // Kill any masked registers.
    1551    20574898 :   while (!regMasks.empty()) {
    1552             :     const uint32_t *Mask = regMasks.pop_back_val();
    1553     4804880 :     for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
    1554    13085262 :       if (TargetRegisterInfo::isPhysicalRegister(*I) &&
    1555             :           MachineOperand::clobbersPhysReg(Mask, *I))
    1556     1581176 :         regsDead.push_back(*I);
    1557             :   }
    1558             :   set_subtract(regsLive, regsDead);   regsDead.clear();
    1559    20387577 :   set_union(regsLive, regsDefined);   regsDefined.clear();
    1560    20387577 : }
    1561             : 
    1562             : void
    1563     1664336 : MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
    1564     1664336 :   MBBInfoMap[MBB].regsLiveOut = regsLive;
    1565             :   regsLive.clear();
    1566             : 
    1567     1664336 :   if (Indexes) {
    1568      238996 :     SlotIndex stop = Indexes->getMBBEndIdx(MBB);
    1569      238996 :     if (!(stop > lastIndex)) {
    1570           0 :       report("Block ends before last instruction index", MBB);
    1571           0 :       errs() << "Block ends at " << stop
    1572           0 :           << " last instruction was at " << lastIndex << '\n';
    1573             :     }
    1574      238996 :     lastIndex = stop;
    1575             :   }
    1576     1664336 : }
    1577             : 
    1578             : // Calculate the largest possible vregsPassed sets. These are the registers that
    1579             : // can pass through an MBB live, but may not be live every time. It is assumed
    1580             : // that all vregsPassed sets are empty before the call.
    1581     1339652 : void MachineVerifier::calcRegsPassed() {
    1582             :   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
    1583             :   // have any vregsPassed.
    1584             :   SmallPtrSet<const MachineBasicBlock*, 8> todo;
    1585     4343640 :   for (const auto &MBB : *MF) {
    1586     3328672 :     BBInfo &MInfo = MBBInfoMap[&MBB];
    1587     1664336 :     if (!MInfo.reachable)
    1588        1279 :       continue;
    1589             :     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
    1590     2123031 :            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
    1591      919948 :       BBInfo &SInfo = MBBInfoMap[*SuI];
    1592      459974 :       if (SInfo.addPassed(MInfo.regsLiveOut))
    1593      163810 :         todo.insert(*SuI);
    1594             :     }
    1595             :   }
    1596             : 
    1597             :   // Iteratively push vregsPassed to successors. This will converge to the same
    1598             :   // final state regardless of DenseSet iteration order.
    1599     1741196 :   while (!todo.empty()) {
    1600      401544 :     const MachineBasicBlock *MBB = *todo.begin();
    1601             :     todo.erase(MBB);
    1602      200772 :     BBInfo &MInfo = MBBInfoMap[MBB];
    1603      200772 :     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
    1604      403811 :            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
    1605      203039 :       if (*SuI == MBB)
    1606       22234 :         continue;
    1607      361610 :       BBInfo &SInfo = MBBInfoMap[*SuI];
    1608      180805 :       if (SInfo.addPassed(MInfo.vregsPassed))
    1609      123182 :         todo.insert(*SuI);
    1610             :     }
    1611             :   }
    1612     1339652 : }
    1613             : 
    1614             : // Calculate the set of virtual registers that must be passed through each basic
    1615             : // block in order to satisfy the requirements of successor blocks. This is very
    1616             : // similar to calcRegsPassed, only backwards.
    1617     1339652 : void MachineVerifier::calcRegsRequired() {
    1618             :   // First push live-in regs to predecessors' vregsRequired.
    1619             :   SmallPtrSet<const MachineBasicBlock*, 8> todo;
    1620     4343640 :   for (const auto &MBB : *MF) {
    1621     3328672 :     BBInfo &MInfo = MBBInfoMap[&MBB];
    1622             :     for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
    1623     2124567 :            PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
    1624      920462 :       BBInfo &PInfo = MBBInfoMap[*PrI];
    1625      460231 :       if (PInfo.addRequired(MInfo.vregsLiveIn))
    1626       60352 :         todo.insert(*PrI);
    1627             :     }
    1628             :   }
    1629             : 
    1630             :   // Iteratively push vregsRequired to predecessors. This will converge to the
    1631             :   // same final state regardless of DenseSet iteration order.
    1632     1503026 :   while (!todo.empty()) {
    1633      163374 :     const MachineBasicBlock *MBB = *todo.begin();
    1634             :     todo.erase(MBB);
    1635       81687 :     BBInfo &MInfo = MBBInfoMap[MBB];
    1636       81687 :     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
    1637      199604 :            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
    1638      117917 :       if (*PrI == MBB)
    1639       16388 :         continue;
    1640      203058 :       BBInfo &SInfo = MBBInfoMap[*PrI];
    1641      101529 :       if (SInfo.addRequired(MInfo.vregsRequired))
    1642       40057 :         todo.insert(*PrI);
    1643             :     }
    1644             :   }
    1645     1339652 : }
    1646             : 
    1647             : // Check PHI instructions at the beginning of MBB. It is assumed that
    1648             : // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
    1649     1664336 : void MachineVerifier::checkPHIOps(const MachineBasicBlock &MBB) {
    1650     3328672 :   BBInfo &MInfo = MBBInfoMap[&MBB];
    1651             : 
    1652             :   SmallPtrSet<const MachineBasicBlock*, 8> seen;
    1653     3406054 :   for (const MachineInstr &Phi : MBB) {
    1654             :     if (!Phi.isPHI())
    1655             :       break;
    1656       77382 :     seen.clear();
    1657             : 
    1658       77382 :     const MachineOperand &MODef = Phi.getOperand(0);
    1659      154764 :     if (!MODef.isReg() || !MODef.isDef()) {
    1660           0 :       report("Expected first PHI operand to be a register def", &MODef, 0);
    1661           0 :       continue;
    1662             :     }
    1663      232146 :     if (MODef.isTied() || MODef.isImplicit() || MODef.isInternalRead() ||
    1664      154764 :         MODef.isEarlyClobber() || MODef.isDebug())
    1665           0 :       report("Unexpected flag on PHI operand", &MODef, 0);
    1666       77382 :     unsigned DefReg = MODef.getReg();
    1667       77382 :     if (!TargetRegisterInfo::isVirtualRegister(DefReg))
    1668           0 :       report("Expected first PHI operand to be a virtual register", &MODef, 0);
    1669             : 
    1670      234446 :     for (unsigned I = 1, E = Phi.getNumOperands(); I != E; I += 2) {
    1671      157064 :       const MachineOperand &MO0 = Phi.getOperand(I);
    1672      157064 :       if (!MO0.isReg()) {
    1673           0 :         report("Expected PHI operand to be a register", &MO0, I);
    1674           0 :         continue;
    1675             :       }
    1676      314128 :       if (MO0.isImplicit() || MO0.isInternalRead() || MO0.isEarlyClobber() ||
    1677      314128 :           MO0.isDebug() || MO0.isTied())
    1678           0 :         report("Unexpected flag on PHI operand", &MO0, I);
    1679             : 
    1680      157064 :       const MachineOperand &MO1 = Phi.getOperand(I + 1);
    1681      157064 :       if (!MO1.isMBB()) {
    1682           0 :         report("Expected PHI operand to be a basic block", &MO1, I + 1);
    1683           0 :         continue;
    1684             :       }
    1685             : 
    1686      157064 :       const MachineBasicBlock &Pre = *MO1.getMBB();
    1687      157064 :       if (!Pre.isSuccessor(&MBB)) {
    1688           0 :         report("PHI input is not a predecessor block", &MO1, I + 1);
    1689           0 :         continue;
    1690             :       }
    1691             : 
    1692      157064 :       if (MInfo.reachable) {
    1693      157064 :         seen.insert(&Pre);
    1694      314128 :         BBInfo &PrInfo = MBBInfoMap[&Pre];
    1695      314120 :         if (!MO0.isUndef() && PrInfo.reachable &&
    1696      157056 :             !PrInfo.isLiveOut(MO0.getReg()))
    1697           2 :           report("PHI operand is not live-out from predecessor", &MO0, I);
    1698             :       }
    1699             :     }
    1700             : 
    1701             :     // Did we see all predecessors?
    1702       77382 :     if (MInfo.reachable) {
    1703      234346 :       for (MachineBasicBlock *Pred : MBB.predecessors()) {
    1704      156964 :         if (!seen.count(Pred)) {
    1705           0 :           report("Missing PHI operand", &Phi);
    1706           0 :           errs() << printMBBReference(*Pred)
    1707           0 :                  << " is a predecessor according to the CFG.\n";
    1708             :         }
    1709             :       }
    1710             :     }
    1711             :   }
    1712     1664336 : }
    1713             : 
    1714     1339652 : void MachineVerifier::visitMachineFunctionAfter() {
    1715     1339652 :   calcRegsPassed();
    1716             : 
    1717     4343640 :   for (const MachineBasicBlock &MBB : *MF)
    1718     1664336 :     checkPHIOps(MBB);
    1719             : 
    1720             :   // Now check liveness info if available
    1721     1339652 :   calcRegsRequired();
    1722             : 
    1723             :   // Check for killed virtual registers that should be live out.
    1724     4343640 :   for (const auto &MBB : *MF) {
    1725     3328672 :     BBInfo &MInfo = MBBInfoMap[&MBB];
    1726             :     for (RegSet::iterator
    1727     2047554 :          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
    1728             :          ++I)
    1729             :       if (MInfo.regsKilled.count(*I)) {
    1730           0 :         report("Virtual register killed in block, but needed live out.", &MBB);
    1731           0 :         errs() << "Virtual register " << printReg(*I)
    1732           0 :                << " is used after the block.\n";
    1733             :       }
    1734             :   }
    1735             : 
    1736     2679304 :   if (!MF->empty()) {
    1737     2679266 :     BBInfo &MInfo = MBBInfoMap[&MF->front()];
    1738             :     for (RegSet::iterator
    1739     1339633 :          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
    1740             :          ++I) {
    1741           0 :       report("Virtual register defs don't dominate all uses.", MF);
    1742           0 :       report_context_vreg(*I);
    1743             :     }
    1744             :   }
    1745             : 
    1746     1339652 :   if (LiveVars)
    1747         117 :     verifyLiveVariables();
    1748     1339652 :   if (LiveInts)
    1749      156454 :     verifyLiveIntervals();
    1750     1339652 : }
    1751             : 
    1752         117 : void MachineVerifier::verifyLiveVariables() {
    1753             :   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
    1754        1284 :   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    1755         525 :     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    1756         525 :     LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
    1757        1836 :     for (const auto &MBB : *MF) {
    1758        1572 :       BBInfo &MInfo = MBBInfoMap[&MBB];
    1759             : 
    1760             :       // Our vregsRequired should be identical to LiveVariables' AliveBlocks
    1761             :       if (MInfo.vregsRequired.count(Reg)) {
    1762           0 :         if (!VI.AliveBlocks.test(MBB.getNumber())) {
    1763           0 :           report("LiveVariables: Block missing from AliveBlocks", &MBB);
    1764           0 :           errs() << "Virtual register " << printReg(Reg)
    1765           0 :                  << " must be live through the block.\n";
    1766             :         }
    1767             :       } else {
    1768         786 :         if (VI.AliveBlocks.test(MBB.getNumber())) {
    1769           0 :           report("LiveVariables: Block should not be in AliveBlocks", &MBB);
    1770           0 :           errs() << "Virtual register " << printReg(Reg)
    1771           0 :                  << " is not needed live through the block.\n";
    1772             :         }
    1773             :       }
    1774             :     }
    1775             :   }
    1776         117 : }
    1777             : 
    1778      156454 : void MachineVerifier::verifyLiveIntervals() {
    1779             :   assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
    1780     7036198 :   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    1781             :     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    1782             : 
    1783             :     // Spilling and splitting may leave unused registers around. Skip them.
    1784     6723290 :     if (MRI->reg_nodbg_empty(Reg))
    1785     2087259 :       continue;
    1786             : 
    1787     1274386 :     if (!LiveInts->hasInterval(Reg)) {
    1788           0 :       report("Missing live interval for virtual register", MF);
    1789           0 :       errs() << printReg(Reg, TRI) << " still has defs or uses\n";
    1790           0 :       continue;
    1791             :     }
    1792             : 
    1793     1274386 :     const LiveInterval &LI = LiveInts->getInterval(Reg);
    1794             :     assert(Reg == LI.reg && "Invalid reg to interval mapping");
    1795     1274386 :     verifyLiveInterval(LI);
    1796             :   }
    1797             : 
    1798             :   // Verify all the cached regunit intervals.
    1799   155388190 :   for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
    1800   310463472 :     if (const LiveRange *LR = LiveInts->getCachedRegUnit(i))
    1801      519898 :       verifyLiveRange(*LR, i);
    1802      156454 : }
    1803             : 
    1804     2787827 : void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR,
    1805             :                                            const VNInfo *VNI, unsigned Reg,
    1806             :                                            LaneBitmask LaneMask) {
    1807     2787827 :   if (VNI->isUnused())
    1808             :     return;
    1809             : 
    1810             :   const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def);
    1811             : 
    1812     2787047 :   if (!DefVNI) {
    1813           0 :     report("Value not live at VNInfo def and not marked unused", MF);
    1814           0 :     report_context(LR, Reg, LaneMask);
    1815           0 :     report_context(*VNI);
    1816           0 :     return;
    1817             :   }
    1818             : 
    1819     2787047 :   if (DefVNI != VNI) {
    1820           0 :     report("Live segment at def has different VNInfo", MF);
    1821           0 :     report_context(LR, Reg, LaneMask);
    1822           0 :     report_context(*VNI);
    1823           0 :     return;
    1824             :   }
    1825             : 
    1826     2787047 :   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
    1827     2787047 :   if (!MBB) {
    1828           0 :     report("Invalid VNInfo definition index", MF);
    1829           0 :     report_context(LR, Reg, LaneMask);
    1830           0 :     report_context(*VNI);
    1831           0 :     return;
    1832             :   }
    1833             : 
    1834     2787047 :   if (VNI->isPHIDef()) {
    1835      693332 :     if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
    1836           0 :       report("PHIDef VNInfo is not defined at MBB start", MBB);
    1837           0 :       report_context(LR, Reg, LaneMask);
    1838           0 :       report_context(*VNI);
    1839             :     }
    1840             :     return;
    1841             :   }
    1842             : 
    1843             :   // Non-PHI def.
    1844             :   const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
    1845     2440381 :   if (!MI) {
    1846           0 :     report("No instruction at VNInfo def index", MBB);
    1847           0 :     report_context(LR, Reg, LaneMask);
    1848           0 :     report_context(*VNI);
    1849           0 :     return;
    1850             :   }
    1851             : 
    1852     2440381 :   if (Reg != 0) {
    1853             :     bool hasDef = false;
    1854             :     bool isEarlyClobber = false;
    1855    12994330 :     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
    1856    24827800 :       if (!MOI->isReg() || !MOI->isDef())
    1857     7595400 :         continue;
    1858     2960640 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1859     2577974 :         if (MOI->getReg() != Reg)
    1860      314683 :           continue;
    1861             :       } else {
    1862     1103510 :         if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
    1863      338178 :             !TRI->hasRegUnit(MOI->getReg(), Reg))
    1864      207008 :           continue;
    1865             :       }
    1866     3088020 :       if (LaneMask.any() &&
    1867     1298114 :           (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
    1868          14 :         continue;
    1869             :       hasDef = true;
    1870     2438935 :       if (MOI->isEarlyClobber())
    1871             :         isEarlyClobber = true;
    1872             :     }
    1873             : 
    1874     2438290 :     if (!hasDef) {
    1875           0 :       report("Defining instruction does not modify register", MI);
    1876           0 :       report_context(LR, Reg, LaneMask);
    1877           0 :       report_context(*VNI);
    1878             :     }
    1879             : 
    1880             :     // Early clobber defs begin at USE slots, but other defs must begin at
    1881             :     // DEF slots.
    1882     2438290 :     if (isEarlyClobber) {
    1883       13743 :       if (!VNI->def.isEarlyClobber()) {
    1884           0 :         report("Early clobber def must be at an early-clobber slot", MBB);
    1885           0 :         report_context(LR, Reg, LaneMask);
    1886           0 :         report_context(*VNI);
    1887             :       }
    1888     2424547 :     } else if (!VNI->def.isRegister()) {
    1889           0 :       report("Non-PHI, non-early clobber def must be at a register slot", MBB);
    1890           0 :       report_context(LR, Reg, LaneMask);
    1891           0 :       report_context(*VNI);
    1892             :     }
    1893             :   }
    1894             : }
    1895             : 
    1896     2805109 : void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
    1897             :                                              const LiveRange::const_iterator I,
    1898             :                                              unsigned Reg, LaneBitmask LaneMask)
    1899             : {
    1900             :   const LiveRange::Segment &S = *I;
    1901     2805109 :   const VNInfo *VNI = S.valno;
    1902             :   assert(VNI && "Live segment has no valno");
    1903             : 
    1904     8415327 :   if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) {
    1905           0 :     report("Foreign valno in live segment", MF);
    1906           0 :     report_context(LR, Reg, LaneMask);
    1907           0 :     report_context(S);
    1908           0 :     report_context(*VNI);
    1909             :   }
    1910             : 
    1911     2805109 :   if (VNI->isUnused()) {
    1912           0 :     report("Live segment valno is marked unused", MF);
    1913           0 :     report_context(LR, Reg, LaneMask);
    1914           0 :     report_context(S);
    1915             :   }
    1916             : 
    1917     2805109 :   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start);
    1918     2805109 :   if (!MBB) {
    1919           0 :     report("Bad start of live segment, no basic block", MF);
    1920           0 :     report_context(LR, Reg, LaneMask);
    1921           0 :     report_context(S);
    1922           0 :     return;
    1923             :   }
    1924     2805109 :   SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
    1925     2805109 :   if (S.start != MBBStartIdx && S.start != VNI->def) {
    1926           0 :     report("Live segment must begin at MBB entry or valno def", MBB);
    1927           0 :     report_context(LR, Reg, LaneMask);
    1928           0 :     report_context(S);
    1929             :   }
    1930             : 
    1931             :   const MachineBasicBlock *EndMBB =
    1932     5610218 :     LiveInts->getMBBFromIndex(S.end.getPrevSlot());
    1933     2805109 :   if (!EndMBB) {
    1934           0 :     report("Bad end of live segment, no basic block", MF);
    1935           0 :     report_context(LR, Reg, LaneMask);
    1936           0 :     report_context(S);
    1937           0 :     return;
    1938             :   }
    1939             : 
    1940             :   // No more checks for live-out segments.
    1941     5610218 :   if (S.end == LiveInts->getMBBEndIdx(EndMBB))
    1942             :     return;
    1943             : 
    1944             :   // RegUnit intervals are allowed dead phis.
    1945      819879 :   if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() &&
    1946     3052506 :       S.start == VNI->def && S.end == VNI->def.getDeadSlot())
    1947             :     return;
    1948             : 
    1949             :   // The live segment is ending inside EndMBB
    1950             :   const MachineInstr *MI =
    1951             :     LiveInts->getInstructionFromIndex(S.end.getPrevSlot());
    1952     2730303 :   if (!MI) {
    1953           0 :     report("Live segment doesn't end at a valid instruction", EndMBB);
    1954           0 :     report_context(LR, Reg, LaneMask);
    1955           0 :     report_context(S);
    1956           0 :     return;
    1957             :   }
    1958             : 
    1959             :   // The block slot must refer to a basic block boundary.
    1960     2730303 :   if (S.end.isBlock()) {
    1961           0 :     report("Live segment ends at B slot of an instruction", EndMBB);
    1962           0 :     report_context(LR, Reg, LaneMask);
    1963           0 :     report_context(S);
    1964             :   }
    1965             : 
    1966     2730303 :   if (S.end.isDead()) {
    1967             :     // Segment ends on the dead slot.
    1968             :     // That means there must be a dead def.
    1969       97482 :     if (!SlotIndex::isSameInstr(S.start, S.end)) {
    1970           0 :       report("Live segment ending at dead slot spans instructions", EndMBB);
    1971           0 :       report_context(LR, Reg, LaneMask);
    1972           0 :       report_context(S);
    1973             :     }
    1974             :   }
    1975             : 
    1976             :   // A live segment can only end at an early-clobber slot if it is being
    1977             :   // redefined by an early-clobber def.
    1978     2730303 :   if (S.end.isEarlyClobber()) {
    1979       16296 :     if (I+1 == LR.end() || (I+1)->start != S.end) {
    1980           0 :       report("Live segment ending at early clobber slot must be "
    1981             :              "redefined by an EC def in the same instruction", EndMBB);
    1982           0 :       report_context(LR, Reg, LaneMask);
    1983           0 :       report_context(S);
    1984             :     }
    1985             :   }
    1986             : 
    1987             :   // The following checks only apply to virtual registers. Physreg liveness
    1988             :   // is too weird to check.
    1989     2730303 :   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1990             :     // A live segment can end with either a redefinition, a kill flag on a
    1991             :     // use, or a dead flag on a def.
    1992             :     bool hasRead = false;
    1993             :     bool hasSubRegDef = false;
    1994             :     bool hasDeadDef = false;
    1995    14584125 :     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
    1996    22358602 :       if (!MOI->isReg() || MOI->getReg() != Reg)
    1997    10007104 :         continue;
    1998             :       unsigned Sub = MOI->getSubReg();
    1999      553533 :       LaneBitmask SLM = Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
    2000     2897927 :                                  : LaneBitmask::getAll();
    2001     2344394 :       if (MOI->isDef()) {
    2002      373269 :         if (Sub != 0) {
    2003             :           hasSubRegDef = true;
    2004             :           // An operand %0:sub0 reads %0:sub1..n. Invert the lane
    2005             :           // mask for subregister defs. Read-undef defs will be handled by
    2006             :           // readsReg below.
    2007             :           SLM = ~SLM;
    2008             :         }
    2009      373269 :         if (MOI->isDead())
    2010             :           hasDeadDef = true;
    2011             :       }
    2012     3019337 :       if (LaneMask.any() && (LaneMask & SLM).none())
    2013       11193 :         continue;
    2014             :       if (MOI->readsReg())
    2015             :         hasRead = true;
    2016             :     }
    2017     2232627 :     if (S.end.isDead()) {
    2018             :       // Make sure that the corresponding machine operand for a "dead" live
    2019             :       // range has the dead flag. We cannot perform this check for subregister
    2020             :       // liveranges as partially dead values are allowed.
    2021       34195 :       if (LaneMask.none() && !hasDeadDef) {
    2022           0 :         report("Instruction ending live segment on dead slot has no dead flag",
    2023             :                MI);
    2024           0 :         report_context(LR, Reg, LaneMask);
    2025           0 :         report_context(S);
    2026             :       }
    2027             :     } else {
    2028     2198432 :       if (!hasRead) {
    2029             :         // When tracking subregister liveness, the main range must start new
    2030             :         // values on partial register writes, even if there is no read.
    2031           2 :         if (!MRI->shouldTrackSubRegLiveness(Reg) || LaneMask.any() ||
    2032             :             !hasSubRegDef) {
    2033           0 :           report("Instruction ending live segment doesn't read the register",
    2034             :                  MI);
    2035           0 :           report_context(LR, Reg, LaneMask);
    2036           0 :           report_context(S);
    2037             :         }
    2038             :       }
    2039             :     }
    2040             :   }
    2041             : 
    2042             :   // Now check all the basic blocks in this live segment.
    2043     2730303 :   MachineFunction::const_iterator MFI = MBB->getIterator();
    2044             :   // Is this live segment the beginning of a non-PHIDef VN?
    2045     5455034 :   if (S.start == VNI->def && !VNI->isPHIDef()) {
    2046             :     // Not live-in to any blocks.
    2047     2386896 :     if (MBB == EndMBB)
    2048             :       return;
    2049             :     // Skip this block.
    2050             :     ++MFI;
    2051             :   }
    2052             :   while (true) {
    2053             :     assert(LiveInts->isLiveInToMBB(LR, &*MFI));
    2054             :     // We don't know how to track physregs into a landing pad.
    2055      746950 :     if (!TargetRegisterInfo::isVirtualRegister(Reg) &&
    2056      320559 :         MFI->isEHPad()) {
    2057          44 :       if (&*MFI == EndMBB)
    2058             :         break;
    2059             :       ++MFI;
    2060           0 :       continue;
    2061             :     }
    2062             : 
    2063             :     // Is VNI a PHI-def in the current block?
    2064      770624 :     bool IsPHI = VNI->isPHIDef() &&
    2065      344277 :       VNI->def == LiveInts->getMBBStartIdx(&*MFI);
    2066             : 
    2067             :     // Check that VNI is live-out of all predecessors.
    2068             :     for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
    2069      585267 :          PE = MFI->pred_end(); PI != PE; ++PI) {
    2070      158920 :       SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
    2071      158920 :       const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
    2072             : 
    2073             :       // All predecessors must have a live-out value. However for a phi
    2074             :       // instruction with subregister intervals
    2075             :       // only one of the subregisters (not necessarily the current one) needs to
    2076             :       // be defined.
    2077      158920 :       if (!PVNI && (LaneMask.none() || !IsPHI) ) {
    2078           0 :         report("Register not marked live out of predecessor", *PI);
    2079           0 :         report_context(LR, Reg, LaneMask);
    2080           0 :         report_context(*VNI);
    2081           0 :         errs() << " live into " << printMBBReference(*MFI) << '@'
    2082           0 :                << LiveInts->getMBBStartIdx(&*MFI) << ", not live before "
    2083           0 :                << PEnd << '\n';
    2084             :         continue;
    2085             :       }
    2086             : 
    2087             :       // Only PHI-defs can take different predecessor values.
    2088      158920 :       if (!IsPHI && PVNI != VNI) {
    2089           0 :         report("Different value live out of predecessor", *PI);
    2090           0 :         report_context(LR, Reg, LaneMask);
    2091           0 :         errs() << "Valno #" << PVNI->id << " live out of "
    2092           0 :                << printMBBReference(*(*PI)) << '@' << PEnd << "\nValno #"
    2093           0 :                << VNI->id << " live into " << printMBBReference(*MFI) << '@'
    2094           0 :                << LiveInts->getMBBStartIdx(&*MFI) << '\n';
    2095             :       }
    2096             :     }
    2097      426347 :     if (&*MFI == EndMBB)
    2098             :       break;
    2099             :     ++MFI;
    2100             :   }
    2101             : }
    2102             : 
    2103     2429231 : void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg,
    2104             :                                       LaneBitmask LaneMask) {
    2105     8004885 :   for (const VNInfo *VNI : LR.valnos)
    2106     2787827 :     verifyLiveRangeValue(LR, VNI, Reg, LaneMask);
    2107             : 
    2108     8039449 :   for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I)
    2109     2805109 :     verifyLiveRangeSegment(LR, I, Reg, LaneMask);
    2110     2429231 : }
    2111             : 
    2112     1274386 : void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
    2113     1274386 :   unsigned Reg = LI.reg;
    2114             :   assert(TargetRegisterInfo::isVirtualRegister(Reg));
    2115     1274386 :   verifyLiveRange(LI, Reg);
    2116             : 
    2117             :   LaneBitmask Mask;
    2118     1274386 :   LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
    2119     1909333 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
    2120      634947 :     if ((Mask & SR.LaneMask).any()) {
    2121           0 :       report("Lane masks of sub ranges overlap in live interval", MF);
    2122           0 :       report_context(LI);
    2123             :     }
    2124      634947 :     if ((SR.LaneMask & ~MaxMask).any()) {
    2125           0 :       report("Subrange lanemask is invalid", MF);
    2126           0 :       report_context(LI);
    2127             :     }
    2128      634947 :     if (SR.empty()) {
    2129           0 :       report("Subrange must not be empty", MF);
    2130           0 :       report_context(SR, LI.reg, SR.LaneMask);
    2131             :     }
    2132             :     Mask |= SR.LaneMask;
    2133      634947 :     verifyLiveRange(SR, LI.reg, SR.LaneMask);
    2134      634947 :     if (!LI.covers(SR)) {
    2135           0 :       report("A Subrange is not covered by the main range", MF);
    2136           0 :       report_context(LI);
    2137             :     }
    2138             :   }
    2139             : 
    2140             :   // Check the LI only has one connected component.
    2141     1274386 :   ConnectedVNInfoEqClasses ConEQ(*LiveInts);
    2142     1274386 :   unsigned NumComp = ConEQ.Classify(LI);
    2143     1274386 :   if (NumComp > 1) {
    2144           0 :     report("Multiple connected components in live interval", MF);
    2145           0 :     report_context(LI);
    2146           0 :     for (unsigned comp = 0; comp != NumComp; ++comp) {
    2147           0 :       errs() << comp << ": valnos";
    2148           0 :       for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
    2149           0 :            E = LI.vni_end(); I!=E; ++I)
    2150           0 :         if (comp == ConEQ.getEqClass(*I))
    2151           0 :           errs() << ' ' << (*I)->id;
    2152           0 :       errs() << '\n';
    2153             :     }
    2154             :   }
    2155     1274386 : }
    2156             : 
    2157             : namespace {
    2158             : 
    2159             :   // FrameSetup and FrameDestroy can have zero adjustment, so using a single
    2160             :   // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
    2161             :   // value is zero.
    2162             :   // We use a bool plus an integer to capture the stack state.
    2163             :   struct StackStateOfBB {
    2164             :     StackStateOfBB() = default;
    2165             :     StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
    2166             :       EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
    2167             :       ExitIsSetup(ExitSetup) {}
    2168             : 
    2169             :     // Can be negative, which means we are setting up a frame.
    2170             :     int EntryValue = 0;
    2171             :     int ExitValue = 0;
    2172             :     bool EntryIsSetup = false;
    2173             :     bool ExitIsSetup = false;
    2174             :   };
    2175             : 
    2176             : } // end anonymous namespace
    2177             : 
    2178             : /// Make sure on every path through the CFG, a FrameSetup <n> is always followed
    2179             : /// by a FrameDestroy <n>, stack adjustments are identical on all
    2180             : /// CFG edges to a merge point, and frame is destroyed at end of a return block.
    2181     1339633 : void MachineVerifier::verifyStackFrame() {
    2182     1339633 :   unsigned FrameSetupOpcode   = TII->getCallFrameSetupOpcode();
    2183     1339633 :   unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
    2184     1339633 :   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
    2185        3497 :     return;
    2186             : 
    2187             :   SmallVector<StackStateOfBB, 8> SPState;
    2188     2672272 :   SPState.resize(MF->getNumBlockIDs());
    2189             :   df_iterator_default_set<const MachineBasicBlock*> Reachable;
    2190             : 
    2191             :   // Visit the MBBs in DFS order.
    2192             :   for (df_ext_iterator<const MachineFunction *,
    2193             :                        df_iterator_default_set<const MachineBasicBlock *>>
    2194     1336136 :        DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
    2195     2995401 :        DFI != DFE; ++DFI) {
    2196     1659265 :     const MachineBasicBlock *MBB = *DFI;
    2197             : 
    2198             :     StackStateOfBB BBState;
    2199             :     // Check the exit state of the DFS stack predecessor.
    2200     1659265 :     if (DFI.getPathLength() >= 2) {
    2201      323129 :       const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
    2202             :       assert(Reachable.count(StackPred) &&
    2203             :              "DFS stack predecessor is already visited.\n");
    2204      646258 :       BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
    2205      323129 :       BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
    2206             :       BBState.ExitValue = BBState.EntryValue;
    2207             :       BBState.ExitIsSetup = BBState.EntryIsSetup;
    2208             :     }
    2209             : 
    2210             :     // Update stack state by checking contents of MBB.
    2211    23670950 :     for (const auto &I : *MBB) {
    2212    40704840 :       if (I.getOpcode() == FrameSetupOpcode) {
    2213      102127 :         if (BBState.ExitIsSetup)
    2214           1 :           report("FrameSetup is after another FrameSetup", &I);
    2215      204254 :         BBState.ExitValue -= TII->getFrameTotalSize(I);
    2216             :         BBState.ExitIsSetup = true;
    2217             :       }
    2218             : 
    2219    40704840 :       if (I.getOpcode() == FrameDestroyOpcode) {
    2220      204254 :         int Size = TII->getFrameTotalSize(I);
    2221      102127 :         if (!BBState.ExitIsSetup)
    2222           1 :           report("FrameDestroy is not after a FrameSetup", &I);
    2223      102127 :         int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
    2224             :                                                BBState.ExitValue;
    2225      102127 :         if (BBState.ExitIsSetup && AbsSPAdj != Size) {
    2226           1 :           report("FrameDestroy <n> is after FrameSetup <m>", &I);
    2227           2 :           errs() << "FrameDestroy <" << Size << "> is after FrameSetup <"
    2228           1 :               << AbsSPAdj << ">.\n";
    2229             :         }
    2230      102127 :         BBState.ExitValue += Size;
    2231             :         BBState.ExitIsSetup = false;
    2232             :       }
    2233             :     }
    2234     3318530 :     SPState[MBB->getNumber()] = BBState;
    2235             : 
    2236             :     // Make sure the exit state of any predecessor is consistent with the entry
    2237             :     // state.
    2238             :     for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
    2239     2118908 :          E = MBB->pred_end(); I != E; ++I) {
    2240      857302 :       if (Reachable.count(*I) &&
    2241     1192977 :           (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue ||
    2242      397659 :            SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
    2243           0 :         report("The exit stack state of a predecessor is inconsistent.", MBB);
    2244           0 :         errs() << "Predecessor " << printMBBReference(*(*I))
    2245           0 :                << " has exit state (" << SPState[(*I)->getNumber()].ExitValue
    2246           0 :                << ", " << SPState[(*I)->getNumber()].ExitIsSetup << "), while "
    2247           0 :                << printMBBReference(*MBB) << " has entry state ("
    2248           0 :                << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
    2249             :       }
    2250             :     }
    2251             : 
    2252             :     // Make sure the entry state of any successor is consistent with the exit
    2253             :     // state.
    2254             :     for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
    2255     2118841 :          E = MBB->succ_end(); I != E; ++I) {
    2256      561706 :       if (Reachable.count(*I) &&
    2257      306390 :           (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue ||
    2258      102130 :            SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
    2259           0 :         report("The entry stack state of a successor is inconsistent.", MBB);
    2260           0 :         errs() << "Successor " << printMBBReference(*(*I))
    2261           0 :                << " has entry state (" << SPState[(*I)->getNumber()].EntryValue
    2262           0 :                << ", " << SPState[(*I)->getNumber()].EntryIsSetup << "), while "
    2263           0 :                << printMBBReference(*MBB) << " has exit state ("
    2264           0 :                << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
    2265             :       }
    2266             :     }
    2267             : 
    2268             :     // Make sure a basic block with return ends with zero stack adjustment.
    2269     3303770 :     if (!MBB->empty() && MBB->back().isReturn()) {
    2270     1350990 :       if (BBState.ExitIsSetup)
    2271           0 :         report("A return block ends with a FrameSetup.", MBB);
    2272     1350990 :       if (BBState.ExitValue)
    2273           0 :         report("A return block ends with a nonzero stack adjustment.", MBB);
    2274             :     }
    2275             :   }
    2276             : }

Generated by: LCOV version 1.13