LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineVerifier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 829 1190 69.7 %
Date: 2017-09-14 15:23:50 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/LiveIntervalAnalysis.h"
      40             : #include "llvm/CodeGen/LiveStackAnalysis.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/IR/BasicBlock.h"
      55             : #include "llvm/IR/Function.h"
      56             : #include "llvm/IR/InlineAsm.h"
      57             : #include "llvm/IR/Instructions.h"
      58             : #include "llvm/MC/LaneBitmask.h"
      59             : #include "llvm/MC/MCAsmInfo.h"
      60             : #include "llvm/MC/MCInstrDesc.h"
      61             : #include "llvm/MC/MCRegisterInfo.h"
      62             : #include "llvm/MC/MCTargetOptions.h"
      63             : #include "llvm/Pass.h"
      64             : #include "llvm/Support/Casting.h"
      65             : #include "llvm/Support/ErrorHandling.h"
      66             : #include "llvm/Support/LowLevelTypeImpl.h"
      67             : #include "llvm/Support/MathExtras.h"
      68             : #include "llvm/Support/raw_ostream.h"
      69             : #include "llvm/Target/TargetInstrInfo.h"
      70             : #include "llvm/Target/TargetMachine.h"
      71             : #include "llvm/Target/TargetOpcodes.h"
      72             : #include "llvm/Target/TargetRegisterInfo.h"
      73             : #include "llvm/Target/TargetSubtargetInfo.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    10152351 :   struct MachineVerifier {
      87    11280390 :     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    24109457 :     void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
     123    24109457 :       RV.push_back(Reg);
     124    48218914 :       if (TargetRegisterInfo::isPhysicalRegister(Reg))
     125    35343191 :         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
     126    20168962 :           RV.push_back(*SubRegs);
     127    24109457 :     }
     128             : 
     129    11504848 :     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    11385840 :       BBInfo() = default;
     157             : 
     158             :       // Add register to vregsPassed if it belongs there. Return true if
     159             :       // anything changed.
     160    13108434 :       bool addPassed(unsigned Reg) {
     161    26216868 :         if (!TargetRegisterInfo::isVirtualRegister(Reg))
     162             :           return false;
     163    17415126 :         if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
     164             :           return false;
     165    11011410 :         return vregsPassed.insert(Reg).second;
     166             :       }
     167             : 
     168             :       // Same for a full set.
     169      579004 :       bool addPassed(const RegSet &RS) {
     170      579004 :         bool changed = false;
     171    15424450 :         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
     172    13108434 :           if (addPassed(*I))
     173     2864997 :             changed = true;
     174      579004 :         return changed;
     175             :       }
     176             : 
     177             :       // Add register to vregsRequired if it belongs there. Return true if
     178             :       // anything changed.
     179     1099431 :       bool addRequired(unsigned Reg) {
     180     2198862 :         if (!TargetRegisterInfo::isVirtualRegister(Reg))
     181             :           return false;
     182     2198862 :         if (regsLiveOut.count(Reg))
     183             :           return false;
     184     1448880 :         return vregsRequired.insert(Reg).second;
     185             :       }
     186             : 
     187             :       // Same for a full set.
     188       92915 :       bool addRequired(const RegSet &RS) {
     189       92915 :         bool changed = false;
     190     1176756 :         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
     191      805096 :           if (addRequired(*I))
     192      220622 :             changed = true;
     193       92915 :         return changed;
     194             :       }
     195             : 
     196             :       // Same for a full map.
     197      417802 :       bool addRequired(const RegMap &RM) {
     198      417802 :         bool changed = false;
     199      835604 :         for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
     200      294335 :           if (addRequired(I->first))
     201      150953 :             changed = true;
     202      417802 :         return changed;
     203             :       }
     204             : 
     205             :       // Live-out registers are either in regsLiveOut or vregsPassed.
     206      144993 :       bool isLiveOut(unsigned Reg) const {
     207      312886 :         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    19197832 :       return Reg < regsReserved.size() && regsReserved.test(Reg);
     216             :     }
     217             : 
     218      671286 :     bool isAllocatable(unsigned Reg) const {
     219     2013680 :       return Reg < TRI->getNumRegs() && TRI->isInAllocatableClass(Reg) &&
     220     2013502 :         !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      351195 :   struct MachineVerifierPass : public MachineFunctionPass {
     288             :     static char ID; // Pass ID, replacement for typeid
     289             : 
     290             :     const std::string Banner;
     291             : 
     292      117243 :     MachineVerifierPass(std::string banner = std::string())
     293      234486 :       : MachineFunctionPass(ID), Banner(std::move(banner)) {
     294      117243 :         initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
     295      117243 :       }
     296             : 
     297      117243 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
     298      117243 :       AU.setPreservesAll();
     299      117243 :       MachineFunctionPass::getAnalysisUsage(AU);
     300      117243 :     }
     301             : 
     302     1125718 :     bool runOnMachineFunction(MachineFunction &MF) override {
     303     2251436 :       unsigned FoundErrors = MachineVerifier(this, Banner.c_str()).verify(MF);
     304     1125718 :       if (FoundErrors)
     305           0 :         report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
     306     1125718 :       return false;
     307             :     }
     308             :   };
     309             : 
     310             : } // end anonymous namespace
     311             : 
     312             : char MachineVerifierPass::ID = 0;
     313             : 
     314      502928 : INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
     315             :                 "Verify generated machine code", false, false)
     316             : 
     317      117242 : FunctionPass *llvm::createMachineVerifierPass(const std::string &Banner) {
     318      234484 :   return new MachineVerifierPass(Banner);
     319             : }
     320             : 
     321        2321 : bool MachineFunction::verify(Pass *p, const char *Banner, bool AbortOnErrors)
     322             :     const {
     323        2321 :   MachineFunction &MF = const_cast<MachineFunction&>(*this);
     324        2321 :   unsigned FoundErrors = MachineVerifier(p, Banner).verify(MF);
     325        2321 :   if (AbortOnErrors && FoundErrors)
     326          20 :     report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
     327        2316 :   return FoundErrors == 0;
     328             : }
     329             : 
     330             : void MachineVerifier::verifySlotIndexes() const {
     331     1128039 :   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     1128039 : 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     2256078 :   if (MF.getProperties().hasProperty(
     348     1670341 :           MachineFunctionProperties::Property::NoVRegs) &&
     349     1084604 :       MRI->getNumVirtRegs())
     350           0 :     report("Function has NoVRegs property but there are VReg operands", &MF);
     351     1128039 : }
     352             : 
     353     1128039 : unsigned MachineVerifier::verify(MachineFunction &MF) {
     354     1128039 :   foundErrors = 0;
     355             : 
     356     1128039 :   this->MF = &MF;
     357     1128039 :   TM = &MF.getTarget();
     358     1128039 :   TII = MF.getSubtarget().getInstrInfo();
     359     1128039 :   TRI = MF.getSubtarget().getRegisterInfo();
     360     1128039 :   MRI = &MF.getRegInfo();
     361             : 
     362     2256078 :   isFunctionRegBankSelected = MF.getProperties().hasProperty(
     363             :       MachineFunctionProperties::Property::RegBankSelected);
     364     2256078 :   isFunctionSelected = MF.getProperties().hasProperty(
     365             :       MachineFunctionProperties::Property::Selected);
     366             : 
     367     1128039 :   LiveVars = nullptr;
     368     1128039 :   LiveInts = nullptr;
     369     1128039 :   LiveStks = nullptr;
     370     1128039 :   Indexes = nullptr;
     371     1128039 :   if (PASS) {
     372     1125895 :     LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
     373             :     // We don't want to verify LiveVariables if LiveIntervals is available.
     374     1125895 :     if (!LiveInts)
     375      989339 :       LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
     376     1125895 :     LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
     377     1125895 :     Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
     378             :   }
     379             : 
     380     1128039 :   verifySlotIndexes();
     381             : 
     382     1128039 :   verifyProperties(MF);
     383             : 
     384     1128039 :   visitMachineFunctionBefore();
     385     4512156 :   for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
     386     2551269 :        MFI!=MFE; ++MFI) {
     387     1423230 :     visitMachineBasicBlockBefore(&*MFI);
     388             :     // Keep track of the current bundle header.
     389     1423230 :     const MachineInstr *CurBundle = nullptr;
     390             :     // Do we expect the next instruction to be part of the same bundle?
     391     1423230 :     bool InBundle = false;
     392             : 
     393     2846460 :     for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
     394     2846460 :            MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
     395    36398440 :       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    18241892 :       if (InBundle && !MBBI->isBundledWithPred())
     403           0 :         report("Missing BundledPred flag, "
     404             :                "BundledSucc was set on predecessor",
     405           0 :                &*MBBI);
     406    54554988 :       if (!InBundle && MBBI->isBundledWithPred())
     407           0 :         report("BundledPred flag is set, "
     408             :                "but BundledSucc not set on predecessor",
     409           0 :                &*MBBI);
     410             : 
     411             :       // Is this a bundle header?
     412    36398440 :       if (!MBBI->isInsideBundle()) {
     413    18177884 :         if (CurBundle)
     414    16768902 :           visitMachineBundleAfter(CurBundle);
     415    18177884 :         CurBundle = &*MBBI;
     416    18177884 :         visitMachineBundleBefore(CurBundle);
     417       21336 :       } else if (!CurBundle)
     418           0 :         report("No bundle header", &*MBBI);
     419    18199220 :       visitMachineInstrBefore(&*MBBI);
     420   111053133 :       for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) {
     421    74654693 :         const MachineInstr &MI = *MBBI;
     422   149309386 :         const MachineOperand &Op = MI.getOperand(I);
     423    74654693 :         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    74654693 :         visitMachineOperand(&Op, I);
     430             :       }
     431             : 
     432    18199220 :       visitMachineInstrAfter(&*MBBI);
     433             : 
     434             :       // Was this the last bundled instruction?
     435    36398440 :       InBundle = MBBI->isBundledWithSucc();
     436             :     }
     437     1423230 :     if (CurBundle)
     438     1408982 :       visitMachineBundleAfter(CurBundle);
     439     1423230 :     if (InBundle)
     440           0 :       report("BundledSucc flag set on last instruction in block", &MFI->back());
     441     1423230 :     visitMachineBasicBlockAfter(&*MFI);
     442             :   }
     443     1128039 :   visitMachineFunctionAfter();
     444             : 
     445             :   // Clean up.
     446     2256078 :   regsLive.clear();
     447     2256078 :   regsDefined.clear();
     448     2256078 :   regsDead.clear();
     449     2256078 :   regsKilled.clear();
     450     2256078 :   regMasks.clear();
     451     1128039 :   MBBInfoMap.clear();
     452             : 
     453     1128039 :   return foundErrors;
     454             : }
     455             : 
     456           6 : void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
     457             :   assert(MF);
     458          12 :   errs() << '\n';
     459           6 :   if (!foundErrors++) {
     460           5 :     if (Banner)
     461           0 :       errs() << "# " << Banner << '\n';
     462           5 :     if (LiveInts != nullptr)
     463           0 :       LiveInts->print(errs());
     464             :     else
     465           5 :       MF->print(errs(), Indexes);
     466             :   }
     467           6 :   errs() << "*** Bad machine code: " << msg << " ***\n"
     468           6 :       << "- function:    " << MF->getName() << "\n";
     469           6 : }
     470             : 
     471           6 : void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
     472             :   assert(MBB);
     473           6 :   report(msg, MBB->getParent());
     474          12 :   errs() << "- basic block: BB#" << MBB->getNumber()
     475           6 :       << ' ' << MBB->getName()
     476          12 :       << " (" << (const void*)MBB << ')';
     477           6 :   if (Indexes)
     478           0 :     errs() << " [" << Indexes->getMBBStartIdx(MBB)
     479           0 :         << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
     480          12 :   errs() << '\n';
     481           6 : }
     482             : 
     483           6 : void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
     484             :   assert(MI);
     485           6 :   report(msg, MI->getParent());
     486           6 :   errs() << "- instruction: ";
     487           6 :   if (Indexes && Indexes->hasIndex(*MI))
     488           0 :     errs() << Indexes->getInstructionIndex(*MI) << '\t';
     489           6 :   MI->print(errs(), /*SkipOpers=*/true);
     490          12 :   errs() << '\n';
     491           6 : }
     492             : 
     493           3 : void MachineVerifier::report(const char *msg,
     494             :                              const MachineOperand *MO, unsigned MONum) {
     495             :   assert(MO);
     496           3 :   report(msg, MO->getParent());
     497           6 :   errs() << "- operand " << MONum << ":   ";
     498           3 :   MO->print(errs(), TRI);
     499           3 :   errs() << "\n";
     500           3 : }
     501             : 
     502           0 : void MachineVerifier::report_context(SlotIndex Pos) const {
     503           0 :   errs() << "- at:          " << Pos << '\n';
     504           0 : }
     505             : 
     506           0 : void MachineVerifier::report_context(const LiveInterval &LI) const {
     507           0 :   errs() << "- interval:    " << LI << '\n';
     508           0 : }
     509             : 
     510           0 : void MachineVerifier::report_context(const LiveRange &LR, unsigned VRegUnit,
     511             :                                      LaneBitmask LaneMask) const {
     512           0 :   report_context_liverange(LR);
     513           0 :   report_context_vreg_regunit(VRegUnit);
     514           0 :   if (LaneMask.any())
     515           0 :     report_context_lanemask(LaneMask);
     516           0 : }
     517             : 
     518           0 : void MachineVerifier::report_context(const LiveRange::Segment &S) const {
     519           0 :   errs() << "- segment:     " << S << '\n';
     520           0 : }
     521             : 
     522           0 : void MachineVerifier::report_context(const VNInfo &VNI) const {
     523           0 :   errs() << "- ValNo:       " << VNI.id << " (def " << VNI.def << ")\n";
     524           0 : }
     525             : 
     526           0 : void MachineVerifier::report_context_liverange(const LiveRange &LR) const {
     527           0 :   errs() << "- liverange:   " << LR << '\n';
     528           0 : }
     529             : 
     530           0 : void MachineVerifier::report_context_vreg(unsigned VReg) const {
     531           0 :   errs() << "- v. register: " << PrintReg(VReg, TRI) << '\n';
     532           0 : }
     533             : 
     534           0 : void MachineVerifier::report_context_vreg_regunit(unsigned VRegOrUnit) const {
     535           0 :   if (TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) {
     536           0 :     report_context_vreg(VRegOrUnit);
     537             :   } else {
     538           0 :     errs() << "- regunit:     " << PrintRegUnit(VRegOrUnit, TRI) << '\n';
     539             :   }
     540           0 : }
     541             : 
     542           0 : void MachineVerifier::report_context_lanemask(LaneBitmask LaneMask) const {
     543           0 :   errs() << "- lanemask:    " << PrintLaneMask(LaneMask) << '\n';
     544           0 : }
     545             : 
     546     1545581 : void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
     547     3091162 :   BBInfo &MInfo = MBBInfoMap[MBB];
     548     1545581 :   if (!MInfo.reachable) {
     549     1421984 :     MInfo.reachable = true;
     550     2843968 :     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
     551     4683505 :            SuE = MBB->succ_end(); SuI != SuE; ++SuI)
     552      417553 :       markReachable(*SuI);
     553             :   }
     554     1545581 : }
     555             : 
     556     1128039 : void MachineVerifier::visitMachineFunctionBefore() {
     557     1128039 :   lastIndex = SlotIndex();
     558     5640195 :   regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs()
     559     1128288 :                                            : TRI->getReservedRegs(*MF);
     560             : 
     561     2256078 :   if (!MF->empty())
     562     2256056 :     markReachable(&MF->front());
     563             : 
     564             :   // Build a set of the basic blocks in the function.
     565     1128039 :   FunctionBlocks.clear();
     566     4807347 :   for (const auto &MBB : *MF) {
     567     1423230 :     FunctionBlocks.insert(&MBB);
     568     2846460 :     BBInfo &MInfo = MBBInfoMap[&MBB];
     569             : 
     570     5692920 :     MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end());
     571     4269690 :     if (MInfo.Preds.size() != MBB.pred_size())
     572           0 :       report("MBB has duplicate entries in its predecessor list.", &MBB);
     573             : 
     574     5692920 :     MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end());
     575     4269690 :     if (MInfo.Succs.size() != MBB.succ_size())
     576           0 :       report("MBB has duplicate entries in its successor list.", &MBB);
     577             :   }
     578             : 
     579             :   // Check that the register use lists are sane.
     580     1128039 :   MRI->verifyUseLists();
     581             : 
     582     2256078 :   if (!MF->empty())
     583     1128028 :     verifyStackFrame();
     584     1128039 : }
     585             : 
     586             : // Does iterator point to a and b as the first two elements?
     587             : static bool matchPair(MachineBasicBlock::const_succ_iterator i,
     588             :                       const MachineBasicBlock *a, const MachineBasicBlock *b) {
     589      125009 :   if (*i == a)
     590       66400 :     return *++i == b;
     591       58609 :   if (*i == b)
     592       58609 :     return *++i == a;
     593             :   return false;
     594             : }
     595             : 
     596             : void
     597     1423230 : MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
     598     1423230 :   FirstTerminator = nullptr;
     599             : 
     600     2846460 :   if (!MF->getProperties().hasProperty(
     601     1977053 :       MachineFunctionProperties::Property::NoPHIs) && MRI->tracksLiveness()) {
     602             :     // If this block has allocatable physical registers live-in, check that
     603             :     // it is an entry block or landing pad.
     604     1778932 :     for (const auto &LI : MBB->liveins()) {
     605     1330207 :       if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() &&
     606     1976763 :           MBB->getIterator() != MBB->getParent()->begin()) {
     607           0 :         report("MBB has allocatable live-in, but isn't entry or landing-pad.", MBB);
     608             :       }
     609             :     }
     610             :   }
     611             : 
     612             :   // Count the number of landing pad successors.
     613     2846460 :   SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
     614     1423230 :   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
     615     3264262 :        E = MBB->succ_end(); I != E; ++I) {
     616      417802 :     if ((*I)->isEHPad())
     617        6457 :       LandingPadSuccs.insert(*I);
     618      417802 :     if (!FunctionBlocks.count(*I))
     619           0 :       report("MBB has successor that isn't part of the function.", MBB);
     620      835604 :     if (!MBBInfoMap[*I].Preds.count(MBB)) {
     621           0 :       report("Inconsistent CFG", MBB);
     622           0 :       errs() << "MBB is not in the predecessor list of the successor BB#"
     623           0 :           << (*I)->getNumber() << ".\n";
     624             :     }
     625             :   }
     626             : 
     627             :   // Check the predecessor list.
     628     1423230 :   for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
     629     3264262 :        E = MBB->pred_end(); I != E; ++I) {
     630      417802 :     if (!FunctionBlocks.count(*I))
     631           0 :       report("MBB has predecessor that isn't part of the function.", MBB);
     632      835604 :     if (!MBBInfoMap[*I].Succs.count(MBB)) {
     633           0 :       report("Inconsistent CFG", MBB);
     634           0 :       errs() << "MBB is not in the successor list of the predecessor BB#"
     635           0 :           << (*I)->getNumber() << ".\n";
     636             :     }
     637             :   }
     638             : 
     639     1423230 :   const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
     640     1423230 :   const BasicBlock *BB = MBB->getBasicBlock();
     641     1423230 :   const Function *Fn = MF->getFunction();
     642     1423420 :   if (LandingPadSuccs.size() > 1 &&
     643         190 :       !(AsmInfo &&
     644           0 :         AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
     645     1423230 :         BB && isa<SwitchInst>(BB->getTerminator())) &&
     646         190 :       !isFuncletEHPersonality(classifyEHPersonality(Fn->getPersonalityFn())))
     647           0 :     report("MBB has more than one landing pad successor", MBB);
     648             : 
     649             :   // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
     650     1423230 :   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     651     2846460 :   SmallVector<MachineOperand, 4> Cond;
     652     2846460 :   if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB,
     653     1423230 :                           Cond)) {
     654             :     // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
     655             :     // check whether its answers match up with reality.
     656      285762 :     if (!TBB && !FBB) {
     657             :       // Block falls through to its successor.
     658      258468 :       MachineFunction::const_iterator MBBI = MBB->getIterator();
     659      129234 :       ++MBBI;
     660      258468 :       if (MBBI == MF->end()) {
     661             :         // It's possible that the block legitimately ends with a noreturn
     662             :         // call or an unreachable, in which case it won't actually fall
     663             :         // out the bottom of the function.
     664      206376 :       } else if (MBB->succ_size() == LandingPadSuccs.size()) {
     665             :         // It's possible that the block legitimately ends with a noreturn
     666             :         // call or an unreachable, in which case it won't actuall fall
     667             :         // out of the block.
     668       94675 :       } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
     669           0 :         report("MBB exits via unconditional fall-through but doesn't have "
     670             :                "exactly one CFG successor!", MBB);
     671       94675 :       } else if (!MBB->isSuccessor(&*MBBI)) {
     672           0 :         report("MBB exits via unconditional fall-through but its successor "
     673             :                "differs from its CFG successor!", MBB);
     674             :       }
     675      359221 :       if (!MBB->empty() && MBB->back().isBarrier() &&
     676          30 :           !TII->isPredicated(MBB->back())) {
     677           0 :         report("MBB exits via unconditional fall-through but ends with a "
     678             :                "barrier instruction!", MBB);
     679             :       }
     680      129234 :       if (!Cond.empty()) {
     681           0 :         report("MBB exits via unconditional fall-through but has a condition!",
     682             :                MBB);
     683             :       }
     684      156528 :     } else if (TBB && !FBB && Cond.empty()) {
     685             :       // Block unconditionally branches somewhere.
     686             :       // If the block has exactly one successor, that happens to be a
     687             :       // landingpad, accept it as valid control flow.
     688       62860 :       if (MBB->succ_size() != 1+LandingPadSuccs.size() &&
     689           0 :           (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 ||
     690       31430 :            *MBB->succ_begin() != *LandingPadSuccs.begin())) {
     691           0 :         report("MBB exits via unconditional branch but doesn't have "
     692             :                "exactly one CFG successor!", MBB);
     693       31430 :       } else if (!MBB->isSuccessor(TBB)) {
     694           0 :         report("MBB exits via unconditional branch but the CFG "
     695             :                "successor doesn't match the actual successor!", MBB);
     696             :       }
     697       31430 :       if (MBB->empty()) {
     698           0 :         report("MBB exits via unconditional branch but doesn't contain "
     699             :                "any instructions!", MBB);
     700       62860 :       } else if (!MBB->back().isBarrier()) {
     701           0 :         report("MBB exits via unconditional branch but doesn't end with a "
     702             :                "barrier instruction!", MBB);
     703       62860 :       } else if (!MBB->back().isTerminator()) {
     704           0 :         report("MBB exits via unconditional branch but the branch isn't a "
     705             :                "terminator instruction!", MBB);
     706             :       }
     707      250196 :     } else if (TBB && !FBB && !Cond.empty()) {
     708             :       // Block conditionally branches somewhere, otherwise falls through.
     709      115322 :       MachineFunction::const_iterator MBBI = MBB->getIterator();
     710       57661 :       ++MBBI;
     711      115322 :       if (MBBI == MF->end()) {
     712           0 :         report("MBB conditionally falls through out of function!", MBB);
     713       57661 :       } else if (MBB->succ_size() == 1) {
     714             :         // A conditional branch with only one successor is weird, but allowed.
     715          52 :         if (&*MBBI != TBB)
     716           0 :           report("MBB exits via conditional branch/fall-through but only has "
     717             :                  "one CFG successor!", MBB);
     718          52 :         else if (TBB != *MBB->succ_begin())
     719           0 :           report("MBB exits via conditional branch/fall-through but the CFG "
     720             :                  "successor don't match the actual successor!", MBB);
     721       57609 :       } else if (MBB->succ_size() != 2) {
     722           0 :         report("MBB exits via conditional branch/fall-through but doesn't have "
     723             :                "exactly two CFG successors!", MBB);
     724      172827 :       } else if (!matchPair(MBB->succ_begin(), TBB, &*MBBI)) {
     725           0 :         report("MBB exits via conditional branch/fall-through but the CFG "
     726             :                "successors don't match the actual successors!", MBB);
     727             :       }
     728       57661 :       if (MBB->empty()) {
     729           0 :         report("MBB exits via conditional branch/fall-through but doesn't "
     730             :                "contain any instructions!", MBB);
     731      115322 :       } else if (MBB->back().isBarrier()) {
     732           0 :         report("MBB exits via conditional branch/fall-through but ends with a "
     733             :                "barrier instruction!", MBB);
     734      115322 :       } else if (!MBB->back().isTerminator()) {
     735           0 :         report("MBB exits via conditional branch/fall-through but the branch "
     736             :                "isn't a terminator instruction!", MBB);
     737             :       }
     738      134874 :     } else if (TBB && FBB) {
     739             :       // Block conditionally branches somewhere, otherwise branches
     740             :       // somewhere else.
     741       67437 :       if (MBB->succ_size() == 1) {
     742             :         // A conditional branch with only one successor is weird, but allowed.
     743          37 :         if (FBB != TBB)
     744           0 :           report("MBB exits via conditional branch/branch through but only has "
     745             :                  "one CFG successor!", MBB);
     746          37 :         else if (TBB != *MBB->succ_begin())
     747           0 :           report("MBB exits via conditional branch/branch through but the CFG "
     748             :                  "successor don't match the actual successor!", MBB);
     749       67400 :       } else if (MBB->succ_size() != 2) {
     750           0 :         report("MBB exits via conditional branch/branch but doesn't have "
     751             :                "exactly two CFG successors!", MBB);
     752      202200 :       } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
     753           0 :         report("MBB exits via conditional branch/branch but the CFG "
     754             :                "successors don't match the actual successors!", MBB);
     755             :       }
     756       67437 :       if (MBB->empty()) {
     757           0 :         report("MBB exits via conditional branch/branch but doesn't "
     758             :                "contain any instructions!", MBB);
     759      134874 :       } else if (!MBB->back().isBarrier()) {
     760           0 :         report("MBB exits via conditional branch/branch but doesn't end with a "
     761             :                "barrier instruction!", MBB);
     762      134874 :       } else if (!MBB->back().isTerminator()) {
     763           0 :         report("MBB exits via conditional branch/branch but the branch "
     764             :                "isn't a terminator instruction!", MBB);
     765             :       }
     766       67437 :       if (Cond.empty()) {
     767           0 :         report("MBB exits via conditinal branch/branch but there's no "
     768             :                "condition!", MBB);
     769             :       }
     770             :     } else {
     771           0 :       report("AnalyzeBranch returned invalid data!", MBB);
     772             :     }
     773             :   }
     774             : 
     775     2846460 :   regsLive.clear();
     776     2846460 :   if (MRI->tracksLiveness()) {
     777     5069163 :     for (const auto &LI : MBB->liveins()) {
     778     2261667 :       if (!TargetRegisterInfo::isPhysicalRegister(LI.PhysReg)) {
     779           0 :         report("MBB live-in list contains non-physical register", MBB);
     780           0 :         continue;
     781             :       }
     782     2261667 :       for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true);
     783     7471246 :            SubRegs.isValid(); ++SubRegs)
     784    15628737 :         regsLive.insert(*SubRegs);
     785             :     }
     786             :   }
     787             : 
     788     1423230 :   const MachineFrameInfo &MFI = MF->getFrameInfo();
     789     2846460 :   BitVector PR = MFI.getPristineRegs(*MF);
     790    10262349 :   for (unsigned I : PR.set_bits()) {
     791     8839119 :     for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
     792    24638120 :          SubRegs.isValid(); ++SubRegs)
     793    47397003 :       regsLive.insert(*SubRegs);
     794             :   }
     795             : 
     796     2846460 :   regsKilled.clear();
     797     2846460 :   regsDefined.clear();
     798             : 
     799     1423230 :   if (Indexes)
     800      423800 :     lastIndex = Indexes->getMBBStartIdx(MBB);
     801     1423230 : }
     802             : 
     803             : // This function gets called for all bundle headers, including normal
     804             : // stand-alone unbundled instructions.
     805    18177884 : void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
     806    20563823 :   if (Indexes && Indexes->hasIndex(*MI)) {
     807     2385883 :     SlotIndex idx = Indexes->getInstructionIndex(*MI);
     808     2385883 :     if (!(idx > lastIndex)) {
     809           0 :       report("Instruction index out of order", MI);
     810           0 :       errs() << "Last instruction was at " << lastIndex << '\n';
     811             :     }
     812     2385883 :     lastIndex = idx;
     813             :   }
     814             : 
     815             :   // Ensure non-terminators don't follow terminators.
     816             :   // Ignore predicated terminators formed by if conversion.
     817             :   // FIXME: If conversion shouldn't need to violate this rule.
     818    18177884 :   if (MI->isTerminator() && !TII->isPredicated(*MI)) {
     819     1374165 :     if (!FirstTerminator)
     820     1300626 :       FirstTerminator = MI;
     821    16803719 :   } else if (FirstTerminator) {
     822           0 :     report("Non-terminator instruction after the first terminator", MI);
     823           0 :     errs() << "First terminator was:\t" << *FirstTerminator;
     824             :   }
     825    18177884 : }
     826             : 
     827             : // The operands on an INLINEASM instruction must follow a template.
     828             : // Verify that the flag operands make sense.
     829      104972 : void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
     830             :   // The first two operands on INLINEASM are the asm string and global flags.
     831      104972 :   if (MI->getNumOperands() < 2) {
     832           0 :     report("Too few operands on inline asm", MI);
     833           0 :     return;
     834             :   }
     835      209944 :   if (!MI->getOperand(0).isSymbol())
     836           0 :     report("Asm string must be an external symbol", MI);
     837      209944 :   if (!MI->getOperand(1).isImm())
     838           0 :     report("Asm flags must be an immediate", MI);
     839             :   // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
     840             :   // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16,
     841             :   // and Extra_IsConvergent = 32.
     842      104972 :   if (!isUInt<6>(MI->getOperand(1).getImm()))
     843           0 :     report("Unknown asm flags", &MI->getOperand(1), 1);
     844             : 
     845             :   static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed");
     846             : 
     847      104972 :   unsigned OpNo = InlineAsm::MIOp_FirstOperand;
     848             :   unsigned NumOps;
     849      460306 :   for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
     850      711630 :     const MachineOperand &MO = MI->getOperand(OpNo);
     851             :     // There may be implicit ops after the fixed operands.
     852      355815 :     if (!MO.isImm())
     853             :       break;
     854      710668 :     NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
     855             :   }
     856             : 
     857      104972 :   if (OpNo > MI->getNumOperands())
     858           0 :     report("Missing operands in last group", MI);
     859             : 
     860             :   // An optional MDNode follows the groups.
     861      105934 :   if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
     862         229 :     ++OpNo;
     863             : 
     864             :   // All trailing operands must be implicit registers.
     865      105616 :   for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
     866         644 :     const MachineOperand &MO = MI->getOperand(OpNo);
     867         644 :     if (!MO.isReg() || !MO.isImplicit())
     868           0 :       report("Expected implicit register after groups", &MO, OpNo);
     869             :   }
     870             : }
     871             : 
     872    18199220 : void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
     873    18199220 :   const MCInstrDesc &MCID = MI->getDesc();
     874    36398440 :   if (MI->getNumOperands() < MCID.getNumOperands()) {
     875           1 :     report("Too few operands", MI);
     876           2 :     errs() << MCID.getNumOperands() << " operands expected, but "
     877           2 :         << MI->getNumOperands() << " given.\n";
     878             :   }
     879             : 
     880    18342308 :   if (MI->isPHI() && MF->getProperties().hasProperty(
     881             :           MachineFunctionProperties::Property::NoPHIs))
     882           0 :     report("Found PHI instruction with NoPHIs property set", MI);
     883             : 
     884             :   // Check the tied operands.
     885    36398440 :   if (MI->isInlineAsm())
     886      104972 :     verifyInlineAsm(MI);
     887             : 
     888             :   // Check the MachineMemOperands for basic consistency.
     889    22126361 :   for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
     890    36398440 :        E = MI->memoperands_end(); I != E; ++I) {
     891     7854282 :     if ((*I)->isLoad() && !MI->mayLoad())
     892           0 :       report("Missing mayLoad flag", MI);
     893     7854282 :     if ((*I)->isStore() && !MI->mayStore())
     894           0 :       report("Missing mayStore flag", MI);
     895             :   }
     896             : 
     897             :   // Debug values must not have a slot index.
     898             :   // Other instructions must have one, unless they are inside a bundle.
     899    18199220 :   if (LiveInts) {
     900     4037510 :     bool mapped = !LiveInts->isNotInMIMap(*MI);
     901     4037510 :     if (MI->isDebugValue()) {
     902          49 :       if (mapped)
     903           0 :         report("Debug instruction has a slot index", MI);
     904     4037412 :     } else if (MI->isInsideBundle()) {
     905           7 :       if (mapped)
     906           0 :         report("Instruction inside bundle has a slot index", MI);
     907             :     } else {
     908     2018699 :       if (!mapped)
     909           0 :         report("Missing slot index", MI);
     910             :     }
     911             :   }
     912             : 
     913             :   // Check types.
     914    36398440 :   if (isPreISelGenericOpcode(MCID.getOpcode())) {
     915        5522 :     if (isFunctionSelected)
     916           1 :       report("Unexpected generic instruction in a Selected function", MI);
     917             : 
     918             :     // Generic instructions specify equality constraints between some
     919             :     // of their operands. Make sure these are consistent.
     920       11044 :     SmallVector<LLT, 4> Types;
     921       36690 :     for (unsigned i = 0; i < MCID.getNumOperands(); ++i) {
     922       25646 :       if (!MCID.OpInfo[i].isGenericType())
     923        1751 :         continue;
     924       22144 :       size_t TypeIdx = MCID.OpInfo[i].getGenericTypeIndex();
     925       22144 :       Types.resize(std::max(TypeIdx + 1, Types.size()));
     926             : 
     927       22144 :       LLT OpTy = MRI->getType(MI->getOperand(i).getReg());
     928       25022 :       if (Types[TypeIdx].isValid() && Types[TypeIdx] != OpTy)
     929           0 :         report("type mismatch in generic instruction", MI);
     930       11072 :       Types[TypeIdx] = OpTy;
     931             :     }
     932             :   }
     933             : 
     934             :   // Generic opcodes must not have physical register operands.
     935    36398440 :   if (isPreISelGenericOpcode(MCID.getOpcode())) {
     936       25007 :     for (auto &Op : MI->operands()) {
     937       26063 :       if (Op.isReg() && TargetRegisterInfo::isPhysicalRegister(Op.getReg()))
     938           0 :         report("Generic instruction cannot have physical register", MI);
     939             :     }
     940             :   }
     941             : 
     942    18199220 :   StringRef ErrorInfo;
     943    18199220 :   if (!TII->verifyInstruction(*MI, ErrorInfo))
     944           0 :     report(ErrorInfo.data(), MI);
     945             : 
     946             :   // Verify properties of various specific instruction types
     947    36398440 :   switch(MI->getOpcode()) {
     948             :   default:
     949             :     break;
     950        1004 :   case TargetOpcode::G_LOAD:
     951             :   case TargetOpcode::G_STORE:
     952             :     // Generic loads and stores must have a single MachineMemOperand
     953             :     // describing that access.
     954        1004 :     if (!MI->hasOneMemOperand())
     955           0 :       report("Generic instruction accessing memory must have one mem operand",
     956             :              MI);
     957             :     break;
     958          55 :   case TargetOpcode::G_PHI: {
     959          55 :     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
     960         110 :     if (!DstTy.isValid() ||
     961         165 :         !std::all_of(MI->operands_begin() + 1, MI->operands_end(),
     962         443 :                      [this, &DstTy](const MachineOperand &MO) {
     963         221 :                        if (!MO.isReg())
     964             :                          return true;
     965         111 :                        LLT Ty = MRI->getType(MO.getReg());
     966         111 :                        if (!Ty.isValid() || (Ty != DstTy))
     967             :                          return false;
     968             :                        return true;
     969             :                      }))
     970           1 :       report("Generic Instruction G_PHI has operands with incompatible/missing "
     971             :              "types",
     972             :              MI);
     973             :     break;
     974             :   }
     975        2283 :   case TargetOpcode::STATEPOINT:
     976        6849 :     if (!MI->getOperand(StatepointOpers::IDPos).isImm() ||
     977        6849 :         !MI->getOperand(StatepointOpers::NBytesPos).isImm() ||
     978        4566 :         !MI->getOperand(StatepointOpers::NCallArgsPos).isImm())
     979           0 :       report("meta operands to STATEPOINT not constant!", MI);
     980             :     break;
     981             : 
     982             :     auto VerifyStackMapConstant = [&](unsigned Offset) {
     983             :       if (!MI->getOperand(Offset).isImm() ||
     984             :           MI->getOperand(Offset).getImm() != StackMaps::ConstantOp || 
     985             :           !MI->getOperand(Offset + 1).isImm()) 
     986             :         report("stack map constant to STATEPOINT not well formed!", MI);
     987             :     };
     988             :     const unsigned VarStart = StatepointOpers(MI).getVarIdx();
     989             :     VerifyStackMapConstant(VarStart + StatepointOpers::CCOffset);
     990             :     VerifyStackMapConstant(VarStart + StatepointOpers::FlagsOffset);
     991             :     VerifyStackMapConstant(VarStart + StatepointOpers::NumDeoptOperandsOffset);
     992             : 
     993             :     // TODO: verify we have properly encoded deopt arguments
     994             :   };
     995    18199220 : }
     996             : 
     997             : void
     998    74654693 : MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
     999    74654693 :   const MachineInstr *MI = MO->getParent();
    1000    74654693 :   const MCInstrDesc &MCID = MI->getDesc();
    1001    74654693 :   unsigned NumDefs = MCID.getNumDefs();
    1002    74654693 :   if (MCID.getOpcode() == TargetOpcode::PATCHPOINT)
    1003          39 :     NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0;
    1004             : 
    1005             :   // The first MCID.NumDefs operands must be explicit register defines
    1006    74654693 :   if (MONum < NumDefs) {
    1007    14434138 :     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
    1008    14434138 :     if (!MO->isReg())
    1009           0 :       report("Explicit definition must be a register", MO, MONum);
    1010    14434138 :     else if (!MO->isDef() && !MCOI.isOptionalDef())
    1011           0 :       report("Explicit definition marked as use", MO, MONum);
    1012    14434138 :     else if (MO->isImplicit())
    1013           0 :       report("Explicit definition marked as implicit", MO, MONum);
    1014    60220555 :   } else if (MONum < MCID.getNumOperands()) {
    1015    45339861 :     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
    1016             :     // Don't check if it's the last operand in a variadic instruction. See,
    1017             :     // e.g., LDM_RET in the arm back end.
    1018    66314354 :     if (MO->isReg() &&
    1019    21710287 :         !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
    1020    20300021 :       if (MO->isDef() && !MCOI.isOptionalDef())
    1021           0 :         report("Explicit operand marked as def", MO, MONum);
    1022    20300021 :       if (MO->isImplicit())
    1023           0 :         report("Explicit operand marked as implicit", MO, MONum);
    1024             :     }
    1025             : 
    1026    45842183 :     int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
    1027             :     if (TiedTo != -1) {
    1028      502322 :       if (!MO->isReg())
    1029           0 :         report("Tied use must be a register", MO, MONum);
    1030      502322 :       else if (!MO->isTied())
    1031           0 :         report("Operand should be tied", MO, MONum);
    1032      502322 :       else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
    1033           0 :         report("Tied def doesn't match MCInstrDesc", MO, MONum);
    1034     1004644 :       else if (TargetRegisterInfo::isPhysicalRegister(MO->getReg())) {
    1035      562290 :         const MachineOperand &MOTied = MI->getOperand(TiedTo);
    1036      281145 :         if (!MOTied.isReg())
    1037           0 :           report("Tied counterpart must be a register", &MOTied, TiedTo);
    1038      843434 :         else if (TargetRegisterInfo::isPhysicalRegister(MOTied.getReg()) &&
    1039      281144 :                  MO->getReg() != MOTied.getReg())
    1040           1 :           report("Tied physical registers must match.", &MOTied, TiedTo);
    1041             :       }
    1042    65309710 :     } else if (MO->isReg() && MO->isTied())
    1043           0 :       report("Explicit operand should not be tied", MO, MONum);
    1044             :   } else {
    1045             :     // ARM adds %reg0 operands to indicate predicates. We'll allow that.
    1046    28599910 :     if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
    1047           0 :       report("Extra explicit operand on non-variadic instruction", MO, MONum);
    1048             :   }
    1049             : 
    1050    74654693 :   switch (MO->getType()) {
    1051    47479258 :   case MachineOperand::MO_Register: {
    1052    47479258 :     const unsigned Reg = MO->getReg();
    1053    47479258 :     if (!Reg)
    1054     1374331 :       return;
    1055   137638259 :     if (MRI->tracksLiveness() && !MI->isDebugValue())
    1056    45427807 :       checkLiveness(MO, MONum);
    1057             : 
    1058             :     // Verify the consistency of tied operands.
    1059    46104929 :     if (MO->isTied()) {
    1060     1010650 :       unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
    1061     2021300 :       const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
    1062     1010650 :       if (!OtherMO.isReg())
    1063           0 :         report("Must be tied to a register", MO, MONum);
    1064     1010650 :       if (!OtherMO.isTied())
    1065           0 :         report("Missing tie flags on tied operand", MO, MONum);
    1066     1010650 :       if (MI->findTiedOperandIdx(OtherIdx) != MONum)
    1067           0 :         report("Inconsistent tie links", MO, MONum);
    1068     1010650 :       if (MONum < MCID.getNumDefs()) {
    1069      503068 :         if (OtherIdx < MCID.getNumOperands()) {
    1070      502322 :           if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
    1071           0 :             report("Explicit def tied to explicit use without tie constraint",
    1072             :                    MO, MONum);
    1073             :         } else {
    1074         746 :           if (!OtherMO.isImplicit())
    1075           0 :             report("Explicit def should be tied to implicit use", MO, MONum);
    1076             :         }
    1077             :       }
    1078             :     }
    1079             : 
    1080             :     // Verify two-address constraints after leaving SSA form.
    1081             :     unsigned DefIdx;
    1082    86294011 :     if (!MRI->isSSA() && MO->isUse() &&
    1083    62152480 :         MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
    1084      662694 :         Reg != MI->getOperand(DefIdx).getReg())
    1085           0 :       report("Two-address instruction operands must be identical", MO, MONum);
    1086             : 
    1087             :     // Check register classes.
    1088    80140236 :     if (MONum < MCID.getNumOperands() && !MO->isImplicit()) {
    1089    34035307 :       unsigned SubIdx = MO->getSubReg();
    1090             : 
    1091    34035307 :       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    1092    16077663 :         if (SubIdx) {
    1093           0 :           report("Illegal subregister index for physical register", MO, MONum);
    1094           0 :           return;
    1095             :         }
    1096    16077663 :         if (const TargetRegisterClass *DRC =
    1097    16077663 :               TII->getRegClass(MCID, MONum, TRI, *MF)) {
    1098    27321148 :           if (!DRC->contains(Reg)) {
    1099           0 :             report("Illegal physical register for instruction", MO, MONum);
    1100           0 :             errs() << TRI->getName(Reg) << " is not a "
    1101           0 :                 << TRI->getRegClassName(DRC) << " register.\n";
    1102             :           }
    1103             :         }
    1104             :       } else {
    1105             :         // Virtual register.
    1106    35902676 :         const TargetRegisterClass *RC = MRI->getRegClassOrNull(Reg);
    1107    17945032 :         if (!RC) {
    1108             :           // This is a generic virtual register.
    1109             : 
    1110             :           // If we're post-Select, we can't have gvregs anymore.
    1111       17699 :           if (isFunctionSelected) {
    1112           1 :             report("Generic virtual register invalid in a Selected function",
    1113             :                    MO, MONum);
    1114           3 :             return;
    1115             :           }
    1116             : 
    1117             :           // The gvreg must have a type and it must not have a SubIdx.
    1118       17698 :           LLT Ty = MRI->getType(Reg);
    1119       17698 :           if (!Ty.isValid()) {
    1120           0 :             report("Generic virtual register must have a valid type", MO,
    1121             :                    MONum);
    1122           0 :             return;
    1123             :           }
    1124             : 
    1125       30309 :           const RegisterBank *RegBank = MRI->getRegBankOrNull(Reg);
    1126             : 
    1127             :           // If we're post-RegBankSelect, the gvreg must have a bank.
    1128       12611 :           if (!RegBank && isFunctionRegBankSelected) {
    1129           1 :             report("Generic virtual register must have a bank in a "
    1130             :                    "RegBankSelected function",
    1131             :                    MO, MONum);
    1132           1 :             return;
    1133             :           }
    1134             : 
    1135             :           // Make sure the register fits into its register bank if any.
    1136       26685 :           if (RegBank && Ty.isValid() &&
    1137        8988 :               RegBank->getSize() < Ty.getSizeInBits()) {
    1138           0 :             report("Register bank is too small for virtual register", MO,
    1139             :                    MONum);
    1140           0 :             errs() << "Register bank " << RegBank->getName() << " too small("
    1141           0 :                    << RegBank->getSize() << ") to fit " << Ty.getSizeInBits()
    1142           0 :                    << "-bits\n";
    1143           0 :             return;
    1144             :           }
    1145       17697 :           if (SubIdx)  {
    1146           0 :             report("Generic virtual register does not subregister index", MO,
    1147             :                    MONum);
    1148           0 :             return;
    1149             :           }
    1150             : 
    1151             :           // If this is a target specific instruction and this operand
    1152             :           // has register class constraint, the virtual register must
    1153             :           // comply to it.
    1154       42023 :           if (!isPreISelGenericOpcode(MCID.getOpcode()) &&
    1155        6629 :               TII->getRegClass(MCID, MONum, TRI, *MF)) {
    1156           0 :             report("Virtual register does not match instruction constraint", MO,
    1157             :                    MONum);
    1158           0 :             errs() << "Expect register class "
    1159           0 :                    << TRI->getRegClassName(
    1160           0 :                           TII->getRegClass(MCID, MONum, TRI, *MF))
    1161           0 :                    << " but got nothing\n";
    1162           0 :             return;
    1163             :           }
    1164             : 
    1165       17697 :           break;
    1166             :         }
    1167    17939945 :         if (SubIdx) {
    1168             :           const TargetRegisterClass *SRC =
    1169     1924721 :             TRI->getSubClassWithSubReg(RC, SubIdx);
    1170     1924721 :           if (!SRC) {
    1171           0 :             report("Invalid subregister index for virtual register", MO, MONum);
    1172           0 :             errs() << "Register class " << TRI->getRegClassName(RC)
    1173           0 :                 << " does not support subreg index " << SubIdx << "\n";
    1174           0 :             return;
    1175             :           }
    1176     1924721 :           if (RC != SRC) {
    1177           0 :             report("Invalid register class for subregister index", MO, MONum);
    1178           0 :             errs() << "Register class " << TRI->getRegClassName(RC)
    1179           0 :                 << " does not fully support subreg index " << SubIdx << "\n";
    1180           0 :             return;
    1181             :           }
    1182             :         }
    1183    17939945 :         if (const TargetRegisterClass *DRC =
    1184    17939945 :               TII->getRegClass(MCID, MONum, TRI, *MF)) {
    1185    11038484 :           if (SubIdx) {
    1186             :             const TargetRegisterClass *SuperRC =
    1187      788031 :                 TRI->getLargestLegalSuperClass(RC, *MF);
    1188      788031 :             if (!SuperRC) {
    1189           0 :               report("No largest legal super class exists.", MO, MONum);
    1190           0 :               return;
    1191             :             }
    1192      788031 :             DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
    1193      788031 :             if (!DRC) {
    1194           0 :               report("No matching super-reg register class.", MO, MONum);
    1195           0 :               return;
    1196             :             }
    1197             :           }
    1198    11038484 :           if (!RC->hasSuperClassEq(DRC)) {
    1199           0 :             report("Illegal virtual register for instruction", MO, MONum);
    1200           0 :             errs() << "Expected a " << TRI->getRegClassName(DRC)
    1201           0 :                 << " register, but got a " << TRI->getRegClassName(RC)
    1202           0 :                 << " register\n";
    1203             :           }
    1204             :         }
    1205             :       }
    1206             :     }
    1207             :     break;
    1208             :   }
    1209             : 
    1210      169316 :   case MachineOperand::MO_RegisterMask:
    1211      169316 :     regMasks.push_back(MO->getRegMask());
    1212      169316 :     break;
    1213             : 
    1214      394654 :   case MachineOperand::MO_MachineBasicBlock:
    1215      144996 :     if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
    1216           0 :       report("PHI operand is not in the CFG", MO, MONum);
    1217             :     break;
    1218             : 
    1219      340515 :   case MachineOperand::MO_FrameIndex:
    1220      416574 :     if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
    1221      357780 :         LiveInts && !LiveInts->isNotInMIMap(*MI)) {
    1222        4839 :       int FI = MO->getIndex();
    1223        9678 :       LiveInterval &LI = LiveStks->getInterval(FI);
    1224        9678 :       SlotIndex Idx = LiveInts->getInstructionIndex(*MI);
    1225             : 
    1226        4839 :       bool stores = MI->mayStore();
    1227        4839 :       bool loads = MI->mayLoad();
    1228             :       // For a memory-to-memory move, we need to check if the frame
    1229             :       // index is used for storing or loading, by inspecting the
    1230             :       // memory operands.
    1231        4839 :       if (stores && loads) {
    1232          48 :         for (auto *MMO : MI->memoperands()) {
    1233          27 :           const PseudoSourceValue *PSV = MMO->getPseudoValue();
    1234          27 :           if (PSV == nullptr) continue;
    1235             :           const FixedStackPseudoSourceValue *Value =
    1236          27 :             dyn_cast<FixedStackPseudoSourceValue>(PSV);
    1237           0 :           if (Value == nullptr) continue;
    1238          27 :           if (Value->getFrameIndex() != FI) continue;
    1239             : 
    1240          50 :           if (MMO->isStore())
    1241             :             loads = false;
    1242             :           else
    1243          11 :             stores = false;
    1244             :           break;
    1245             :         }
    1246          25 :         if (loads == stores)
    1247           0 :           report("Missing fixed stack memoperand.", MI);
    1248             :       }
    1249        7577 :       if (loads && !LI.liveAt(Idx.getRegSlot(true))) {
    1250           0 :         report("Instruction loads from dead spill slot", MO, MONum);
    1251           0 :         errs() << "Live stack: " << LI << '\n';
    1252             :       }
    1253        6940 :       if (stores && !LI.liveAt(Idx.getRegSlot())) {
    1254           0 :         report("Instruction stores to dead spill slot", MO, MONum);
    1255           0 :         errs() << "Live stack: " << LI << '\n';
    1256             :       }
    1257             :     }
    1258             :     break;
    1259             : 
    1260             :   default:
    1261             :     break;
    1262             :   }
    1263             : }
    1264             : 
    1265     3404976 : void MachineVerifier::checkLivenessAtUse(const MachineOperand *MO,
    1266             :     unsigned MONum, SlotIndex UseIdx, const LiveRange &LR, unsigned VRegOrUnit,
    1267             :     LaneBitmask LaneMask) {
    1268     3404976 :   LiveQueryResult LRQ = LR.Query(UseIdx);
    1269             :   // Check if we have a segment at the use, note however that we only need one
    1270             :   // live subregister range, the others may be dead.
    1271     3404976 :   if (!LRQ.valueIn() && LaneMask.none()) {
    1272           0 :     report("No live segment at use", MO, MONum);
    1273           0 :     report_context_liverange(LR);
    1274           0 :     report_context_vreg_regunit(VRegOrUnit);
    1275           0 :     report_context(UseIdx);
    1276             :   }
    1277     3404976 :   if (MO->isKill() && !LRQ.isKill()) {
    1278           0 :     report("Live range continues after kill flag", MO, MONum);
    1279           0 :     report_context_liverange(LR);
    1280           0 :     report_context_vreg_regunit(VRegOrUnit);
    1281           0 :     if (LaneMask.any())
    1282           0 :       report_context_lanemask(LaneMask);
    1283           0 :     report_context(UseIdx);
    1284             :   }
    1285     3404976 : }
    1286             : 
    1287     2092268 : void MachineVerifier::checkLivenessAtDef(const MachineOperand *MO,
    1288             :     unsigned MONum, SlotIndex DefIdx, const LiveRange &LR, unsigned VRegOrUnit,
    1289             :     LaneBitmask LaneMask) {
    1290     2092268 :   if (const VNInfo *VNI = LR.getVNInfoAt(DefIdx)) {
    1291             :     assert(VNI && "NULL valno is not allowed");
    1292     4184536 :     if (VNI->def != DefIdx) {
    1293           0 :       report("Inconsistent valno->def", MO, MONum);
    1294           0 :       report_context_liverange(LR);
    1295           0 :       report_context_vreg_regunit(VRegOrUnit);
    1296           0 :       if (LaneMask.any())
    1297           0 :         report_context_lanemask(LaneMask);
    1298           0 :       report_context(*VNI);
    1299           0 :       report_context(DefIdx);
    1300             :     }
    1301             :   } else {
    1302           0 :     report("No live segment at def", MO, MONum);
    1303           0 :     report_context_liverange(LR);
    1304           0 :     report_context_vreg_regunit(VRegOrUnit);
    1305           0 :     if (LaneMask.any())
    1306           0 :       report_context_lanemask(LaneMask);
    1307           0 :     report_context(DefIdx);
    1308             :   }
    1309             :   // Check that, if the dead def flag is present, LiveInts agree.
    1310     2092268 :   if (MO->isDead()) {
    1311       10048 :     LiveQueryResult LRQ = LR.Query(DefIdx);
    1312       10048 :     if (!LRQ.isDeadDef()) {
    1313             :       // In case of physregs we can have a non-dead definition on another
    1314             :       // operand.
    1315           0 :       bool otherDef = false;
    1316           0 :       if (!TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) {
    1317           0 :         const MachineInstr &MI = *MO->getParent();
    1318           0 :         for (const MachineOperand &MO : MI.operands()) {
    1319           0 :           if (!MO.isReg() || !MO.isDef() || MO.isDead())
    1320           0 :             continue;
    1321           0 :           unsigned Reg = MO.getReg();
    1322           0 :           for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
    1323           0 :             if (*Units == VRegOrUnit) {
    1324             :               otherDef = true;
    1325             :               break;
    1326             :             }
    1327             :           }
    1328             :         }
    1329             :       }
    1330             : 
    1331           0 :       if (!otherDef) {
    1332           0 :         report("Live range continues after dead def flag", MO, MONum);
    1333           0 :         report_context_liverange(LR);
    1334           0 :         report_context_vreg_regunit(VRegOrUnit);
    1335           0 :         if (LaneMask.any())
    1336           0 :           report_context_lanemask(LaneMask);
    1337             :       }
    1338             :     }
    1339             :   }
    1340     2092268 : }
    1341             : 
    1342    45427807 : void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
    1343    45427807 :   const MachineInstr *MI = MO->getParent();
    1344    45427807 :   const unsigned Reg = MO->getReg();
    1345             : 
    1346             :   // Both use and def operands can read a register.
    1347             :   if (MO->readsReg()) {
    1348    28833432 :     if (MO->isKill())
    1349     7377404 :       addRegWithSubRegs(regsKilled, Reg);
    1350             : 
    1351             :     // Check that LiveVars knows this kill.
    1352    28834620 :     if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
    1353         594 :         MO->isKill()) {
    1354         507 :       LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
    1355        1014 :       if (!is_contained(VI.Kills, MI))
    1356           0 :         report("Kill missing from LiveVariables", MO, MONum);
    1357             :     }
    1358             : 
    1359             :     // Check LiveInts liveness and kill.
    1360    32215990 :     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
    1361     6765106 :       SlotIndex UseIdx = LiveInts->getInstructionIndex(*MI);
    1362             :       // Check the cached regunit intervals.
    1363     6765106 :       if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
    1364     1223469 :         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
    1365      962858 :           if (MRI->isReservedRegUnit(*Units))
    1366          34 :             continue;
    1367      962790 :           if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units))
    1368      379837 :             checkLivenessAtUse(MO, MONum, UseIdx, *LR, *Units);
    1369             :         }
    1370             :       }
    1371             : 
    1372     6765106 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1373     4088596 :         if (LiveInts->hasInterval(Reg)) {
    1374             :           // This is a virtual register interval.
    1375     2044298 :           const LiveInterval &LI = LiveInts->getInterval(Reg);
    1376     2044298 :           checkLivenessAtUse(MO, MONum, UseIdx, LI, Reg);
    1377             : 
    1378     2819628 :           if (LI.hasSubRanges() && !MO->isDef()) {
    1379      505512 :             unsigned SubRegIdx = MO->getSubReg();
    1380             :             LaneBitmask MOMask = SubRegIdx != 0
    1381      292585 :                                ? TRI->getSubRegIndexLaneMask(SubRegIdx)
    1382     1090682 :                                : MRI->getMaxLaneMaskForVReg(Reg);
    1383      505512 :             LaneBitmask LiveInMask;
    1384     2807986 :             for (const LiveInterval::SubRange &SR : LI.subranges()) {
    1385     1796962 :               if ((MOMask & SR.LaneMask).none())
    1386      816121 :                 continue;
    1387      980841 :               checkLivenessAtUse(MO, MONum, UseIdx, SR, Reg, SR.LaneMask);
    1388      980841 :               LiveQueryResult LRQ = SR.Query(UseIdx);
    1389      980841 :               if (LRQ.valueIn())
    1390             :                 LiveInMask |= SR.LaneMask;
    1391             :             }
    1392             :             // At least parts of the register has to be live at the use.
    1393      505512 :             if ((LiveInMask & MOMask).none()) {
    1394           0 :               report("No live subrange at use", MO, MONum);
    1395           0 :               report_context(LI);
    1396           0 :               report_context(UseIdx);
    1397             :             }
    1398             :           }
    1399             :         } else {
    1400           0 :           report("Virtual register has no live interval", MO, MONum);
    1401             :         }
    1402             :       }
    1403             :     }
    1404             : 
    1405             :     // Use of a dead register.
    1406    57666864 :     if (!regsLive.count(Reg)) {
    1407    17323934 :       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    1408             :         // Reserved registers may be used even when 'dead'.
    1409    16521322 :         bool Bad = !isReserved(Reg);
    1410             :         // We are fine if just any subregister has a defined value.
    1411     8260661 :         if (Bad) {
    1412     1567086 :           for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid();
    1413             :                ++SubRegs) {
    1414     2439861 :             if (regsLive.count(*SubRegs)) {
    1415             :               Bad = false;
    1416             :               break;
    1417             :             }
    1418             :           }
    1419             :         }
    1420             :         // If there is an additional implicit-use of a super register we stop
    1421             :         // here. By definition we are fine if the super register is not
    1422             :         // (completely) dead, if the complete super register is dead we will
    1423             :         // get a report for its operand.
    1424     8260661 :         if (Bad) {
    1425        1352 :           for (const MachineOperand &MOP : MI->uses()) {
    1426         868 :             if (!MOP.isReg())
    1427          56 :               continue;
    1428         812 :             if (!MOP.isImplicit())
    1429         270 :               continue;
    1430        3711 :             for (MCSubRegIterator SubRegs(MOP.getReg(), TRI); SubRegs.isValid();
    1431             :                  ++SubRegs) {
    1432        5758 :               if (*SubRegs == Reg) {
    1433             :                 Bad = false;
    1434             :                 break;
    1435             :               }
    1436             :             }
    1437             :           }
    1438             :         }
    1439     8260661 :         if (Bad)
    1440           0 :           report("Using an undefined physical register", MO, MONum);
    1441      802612 :       } else if (MRI->def_empty(Reg)) {
    1442           0 :         report("Reading virtual register without a def", MO, MONum);
    1443             :       } else {
    1444      802612 :         BBInfo &MInfo = MBBInfoMap[MI->getParent()];
    1445             :         // We don't know which virtual registers are live in, so only complain
    1446             :         // if vreg was killed in this MBB. Otherwise keep track of vregs that
    1447             :         // must be live in. PHI instructions are handled separately.
    1448      802612 :         if (MInfo.regsKilled.count(Reg))
    1449           0 :           report("Using a killed virtual register", MO, MONum);
    1450      657665 :         else if (!MI->isPHI())
    1451      769077 :           MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
    1452             :       }
    1453             :     }
    1454             :   }
    1455             : 
    1456    45427807 :   if (MO->isDef()) {
    1457             :     // Register defined.
    1458             :     // TODO: verify that earlyclobber ops are not used.
    1459    16732053 :     if (MO->isDead())
    1460     1387078 :       addRegWithSubRegs(regsDead, Reg);
    1461             :     else
    1462    15344975 :       addRegWithSubRegs(regsDefined, Reg);
    1463             : 
    1464             :     // Verify SSA form.
    1465    48494798 :     if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
    1466    20587242 :         std::next(MRI->def_begin(Reg)) != MRI->def_end())
    1467           0 :       report("Multiple virtual register defs in SSA form", MO, MONum);
    1468             : 
    1469             :     // Check LiveInts for a live segment, but only for virtual registers.
    1470    18607178 :     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
    1471     3750240 :       SlotIndex DefIdx = LiveInts->getInstructionIndex(*MI);
    1472     3750240 :       DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
    1473             : 
    1474     3750240 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1475     2930468 :         if (LiveInts->hasInterval(Reg)) {
    1476     1465234 :           const LiveInterval &LI = LiveInts->getInterval(Reg);
    1477     1465234 :           checkLivenessAtDef(MO, MONum, DefIdx, LI, Reg);
    1478             : 
    1479     1465234 :           if (LI.hasSubRanges()) {
    1480      475953 :             unsigned SubRegIdx = MO->getSubReg();
    1481             :             LaneBitmask MOMask = SubRegIdx != 0
    1482      422012 :               ? TRI->getSubRegIndexLaneMask(SubRegIdx)
    1483     1319977 :               : MRI->getMaxLaneMaskForVReg(Reg);
    1484     2547570 :             for (const LiveInterval::SubRange &SR : LI.subranges()) {
    1485     3191328 :               if ((SR.LaneMask & MOMask).none())
    1486      968630 :                 continue;
    1487      627034 :               checkLivenessAtDef(MO, MONum, DefIdx, SR, Reg, SR.LaneMask);
    1488             :             }
    1489             :           }
    1490             :         } else {
    1491           0 :           report("Virtual register has no Live interval", MO, MONum);
    1492             :         }
    1493             :       }
    1494             :     }
    1495             :   }
    1496    45427807 : }
    1497             : 
    1498             : void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {}
    1499             : 
    1500             : // This function gets called after visiting all instructions in a bundle. The
    1501             : // argument points to the bundle header.
    1502             : // Normal stand-alone instructions are also considered 'bundles', and this
    1503             : // function is called for all of them.
    1504    18177884 : void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
    1505    36355768 :   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
    1506    18177884 :   set_union(MInfo.regsKilled, regsKilled);
    1507    36355768 :   set_subtract(regsLive, regsKilled); regsKilled.clear();
    1508             :   // Kill any masked registers.
    1509    18347200 :   while (!regMasks.empty()) {
    1510      338632 :     const uint32_t *Mask = regMasks.pop_back_val();
    1511     8988358 :     for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
    1512    11486212 :       if (TargetRegisterInfo::isPhysicalRegister(*I) &&
    1513     6688868 :           MachineOperand::clobbersPhysReg(Mask, *I))
    1514     1410072 :         regsDead.push_back(*I);
    1515             :   }
    1516    54533652 :   set_subtract(regsLive, regsDead);   regsDead.clear();
    1517    36355768 :   set_union(regsLive, regsDefined);   regsDefined.clear();
    1518    18177884 : }
    1519             : 
    1520             : void
    1521     1423230 : MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
    1522     4269690 :   MBBInfoMap[MBB].regsLiveOut = regsLive;
    1523     2846460 :   regsLive.clear();
    1524             : 
    1525     1423230 :   if (Indexes) {
    1526      423800 :     SlotIndex stop = Indexes->getMBBEndIdx(MBB);
    1527      211900 :     if (!(stop > lastIndex)) {
    1528           0 :       report("Block ends before last instruction index", MBB);
    1529           0 :       errs() << "Block ends at " << stop
    1530           0 :           << " last instruction was at " << lastIndex << '\n';
    1531             :     }
    1532      211900 :     lastIndex = stop;
    1533             :   }
    1534     1423230 : }
    1535             : 
    1536             : // Calculate the largest possible vregsPassed sets. These are the registers that
    1537             : // can pass through an MBB live, but may not be live every time. It is assumed
    1538             : // that all vregsPassed sets are empty before the call.
    1539     1128039 : void MachineVerifier::calcRegsPassed() {
    1540             :   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
    1541             :   // have any vregsPassed.
    1542     2256078 :   SmallPtrSet<const MachineBasicBlock*, 8> todo;
    1543     4807347 :   for (const auto &MBB : *MF) {
    1544     2846460 :     BBInfo &MInfo = MBBInfoMap[&MBB];
    1545     1423230 :     if (!MInfo.reachable)
    1546        1246 :       continue;
    1547     1421984 :     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
    1548     3261521 :            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
    1549      835106 :       BBInfo &SInfo = MBBInfoMap[*SuI];
    1550      417553 :       if (SInfo.addPassed(MInfo.regsLiveOut))
    1551      149047 :         todo.insert(*SuI);
    1552             :     }
    1553             :   }
    1554             : 
    1555             :   // Iteratively push vregsPassed to successors. This will converge to the same
    1556             :   // final state regardless of DenseSet iteration order.
    1557     1492853 :   while (!todo.empty()) {
    1558      364814 :     const MachineBasicBlock *MBB = *todo.begin();
    1559      364814 :     todo.erase(MBB);
    1560      364814 :     BBInfo &MInfo = MBBInfoMap[MBB];
    1561      364814 :     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
    1562      730142 :            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
    1563      182921 :       if (*SuI == MBB)
    1564       21470 :         continue;
    1565      322902 :       BBInfo &SInfo = MBBInfoMap[*SuI];
    1566      161451 :       if (SInfo.addPassed(MInfo.vregsPassed))
    1567      110293 :         todo.insert(*SuI);
    1568             :     }
    1569             :   }
    1570     1128039 : }
    1571             : 
    1572             : // Calculate the set of virtual registers that must be passed through each basic
    1573             : // block in order to satisfy the requirements of successor blocks. This is very
    1574             : // similar to calcRegsPassed, only backwards.
    1575     1128039 : void MachineVerifier::calcRegsRequired() {
    1576             :   // First push live-in regs to predecessors' vregsRequired.
    1577     2256078 :   SmallPtrSet<const MachineBasicBlock*, 8> todo;
    1578     4807347 :   for (const auto &MBB : *MF) {
    1579     2846460 :     BBInfo &MInfo = MBBInfoMap[&MBB];
    1580     1423230 :     for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
    1581     3264262 :            PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
    1582      835604 :       BBInfo &PInfo = MBBInfoMap[*PrI];
    1583      417802 :       if (PInfo.addRequired(MInfo.vregsLiveIn))
    1584       54924 :         todo.insert(*PrI);
    1585             :     }
    1586             :   }
    1587             : 
    1588             :   // Iteratively push vregsRequired to predecessors. This will converge to the
    1589             :   // same final state regardless of DenseSet iteration order.
    1590     1278385 :   while (!todo.empty()) {
    1591      150346 :     const MachineBasicBlock *MBB = *todo.begin();
    1592      150346 :     todo.erase(MBB);
    1593      150346 :     BBInfo &MInfo = MBBInfoMap[MBB];
    1594      150346 :     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
    1595      334739 :            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
    1596      109220 :       if (*PrI == MBB)
    1597       16305 :         continue;
    1598      185830 :       BBInfo &SInfo = MBBInfoMap[*PrI];
    1599       92915 :       if (SInfo.addRequired(MInfo.vregsRequired))
    1600       36851 :         todo.insert(*PrI);
    1601             :     }
    1602             :   }
    1603     1128039 : }
    1604             : 
    1605             : // Check PHI instructions at the beginning of MBB. It is assumed that
    1606             : // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
    1607     1421984 : void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
    1608     2843968 :   SmallPtrSet<const MachineBasicBlock*, 8> seen;
    1609     7238989 :   for (const auto &BBI : *MBB) {
    1610             :     if (!BBI.isPHI())
    1611             :       break;
    1612       71544 :     seen.clear();
    1613             : 
    1614      216540 :     for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
    1615      289992 :       unsigned Reg = BBI.getOperand(i).getReg();
    1616      289992 :       const MachineBasicBlock *Pre = BBI.getOperand(i + 1).getMBB();
    1617      144996 :       if (!Pre->isSuccessor(MBB))
    1618           0 :         continue;
    1619      144996 :       seen.insert(Pre);
    1620      289992 :       BBInfo &PrInfo = MBBInfoMap[Pre];
    1621      144996 :       if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
    1622           0 :         report("PHI operand is not live-out from predecessor",
    1623           0 :                &BBI.getOperand(i), i);
    1624             :     }
    1625             : 
    1626             :     // Did we see all predecessors?
    1627       71544 :     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
    1628      287988 :            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
    1629      144900 :       if (!seen.count(*PrI)) {
    1630           0 :         report("Missing PHI operand", &BBI);
    1631           0 :         errs() << "BB#" << (*PrI)->getNumber()
    1632           0 :             << " is a predecessor according to the CFG.\n";
    1633             :       }
    1634             :     }
    1635             :   }
    1636     1421984 : }
    1637             : 
    1638     1128039 : void MachineVerifier::visitMachineFunctionAfter() {
    1639     1128039 :   calcRegsPassed();
    1640             : 
    1641     4807347 :   for (const auto &MBB : *MF) {
    1642     2846460 :     BBInfo &MInfo = MBBInfoMap[&MBB];
    1643             : 
    1644             :     // Skip unreachable MBBs.
    1645     1423230 :     if (!MInfo.reachable)
    1646        1246 :       continue;
    1647             : 
    1648     1421984 :     checkPHIOps(&MBB);
    1649             :   }
    1650             : 
    1651             :   // Now check liveness info if available
    1652     1128039 :   calcRegsRequired();
    1653             : 
    1654             :   // Check for killed virtual registers that should be live out.
    1655     4807347 :   for (const auto &MBB : *MF) {
    1656     2846460 :     BBInfo &MInfo = MBBInfoMap[&MBB];
    1657             :     for (RegSet::iterator
    1658     7859300 :          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
    1659             :          ++I)
    1660     1114725 :       if (MInfo.regsKilled.count(*I)) {
    1661           0 :         report("Virtual register killed in block, but needed live out.", &MBB);
    1662           0 :         errs() << "Virtual register " << PrintReg(*I)
    1663           0 :             << " is used after the block.\n";
    1664             :       }
    1665             :   }
    1666             : 
    1667     2256078 :   if (!MF->empty()) {
    1668     3384084 :     BBInfo &MInfo = MBBInfoMap[&MF->front()];
    1669             :     for (RegSet::iterator
    1670     5640140 :          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
    1671             :          ++I) {
    1672           0 :       report("Virtual register defs don't dominate all uses.", MF);
    1673           0 :       report_context_vreg(*I);
    1674             :     }
    1675             :   }
    1676             : 
    1677     1128039 :   if (LiveVars)
    1678         117 :     verifyLiveVariables();
    1679     1128039 :   if (LiveInts)
    1680      136556 :     verifyLiveIntervals();
    1681     1128039 : }
    1682             : 
    1683         117 : void MachineVerifier::verifyLiveVariables() {
    1684             :   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
    1685         759 :   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    1686         525 :     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    1687         525 :     LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
    1688        2361 :     for (const auto &MBB : *MF) {
    1689        1572 :       BBInfo &MInfo = MBBInfoMap[&MBB];
    1690             : 
    1691             :       // Our vregsRequired should be identical to LiveVariables' AliveBlocks
    1692        1572 :       if (MInfo.vregsRequired.count(Reg)) {
    1693           0 :         if (!VI.AliveBlocks.test(MBB.getNumber())) {
    1694           0 :           report("LiveVariables: Block missing from AliveBlocks", &MBB);
    1695           0 :           errs() << "Virtual register " << PrintReg(Reg)
    1696           0 :               << " must be live through the block.\n";
    1697             :         }
    1698             :       } else {
    1699         786 :         if (VI.AliveBlocks.test(MBB.getNumber())) {
    1700           0 :           report("LiveVariables: Block should not be in AliveBlocks", &MBB);
    1701           0 :           errs() << "Virtual register " << PrintReg(Reg)
    1702           0 :               << " is not needed live through the block.\n";
    1703             :         }
    1704             :       }
    1705             :     }
    1706             :   }
    1707         117 : }
    1708             : 
    1709      136556 : void MachineVerifier::verifyLiveIntervals() {
    1710             :   assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
    1711     3444281 :   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    1712     3171169 :     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    1713             : 
    1714             :     // Spilling and splitting may leave unused registers around. Skip them.
    1715     6342338 :     if (MRI->reg_nodbg_empty(Reg))
    1716     2035764 :       continue;
    1717             : 
    1718     2270810 :     if (!LiveInts->hasInterval(Reg)) {
    1719           0 :       report("Missing live interval for virtual register", MF);
    1720           0 :       errs() << PrintReg(Reg, TRI) << " still has defs or uses\n";
    1721           0 :       continue;
    1722             :     }
    1723             : 
    1724     1135405 :     const LiveInterval &LI = LiveInts->getInterval(Reg);
    1725             :     assert(Reg == LI.reg && "Invalid reg to interval mapping");
    1726     1135405 :     verifyLiveInterval(LI);
    1727             :   }
    1728             : 
    1729             :   // Verify all the cached regunit intervals.
    1730   134991628 :   for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
    1731   269710144 :     if (const LiveRange *LR = LiveInts->getCachedRegUnit(i))
    1732      463229 :       verifyLiveRange(*LR, i);
    1733      136556 : }
    1734             : 
    1735     2571646 : void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR,
    1736             :                                            const VNInfo *VNI, unsigned Reg,
    1737             :                                            LaneBitmask LaneMask) {
    1738     2571646 :   if (VNI->isUnused())
    1739             :     return;
    1740             : 
    1741     2570890 :   const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def);
    1742             : 
    1743     2570890 :   if (!DefVNI) {
    1744           0 :     report("Value not live at VNInfo def and not marked unused", MF);
    1745           0 :     report_context(LR, Reg, LaneMask);
    1746           0 :     report_context(*VNI);
    1747           0 :     return;
    1748             :   }
    1749             : 
    1750     2570890 :   if (DefVNI != VNI) {
    1751           0 :     report("Live segment at def has different VNInfo", MF);
    1752           0 :     report_context(LR, Reg, LaneMask);
    1753           0 :     report_context(*VNI);
    1754           0 :     return;
    1755             :   }
    1756             : 
    1757     5141780 :   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
    1758     2570890 :   if (!MBB) {
    1759           0 :     report("Invalid VNInfo definition index", MF);
    1760           0 :     report_context(LR, Reg, LaneMask);
    1761           0 :     report_context(*VNI);
    1762           0 :     return;
    1763             :   }
    1764             : 
    1765     2570890 :   if (VNI->isPHIDef()) {
    1766      910329 :     if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
    1767           0 :       report("PHIDef VNInfo is not defined at MBB start", MBB);
    1768           0 :       report_context(LR, Reg, LaneMask);
    1769           0 :       report_context(*VNI);
    1770             :     }
    1771             :     return;
    1772             :   }
    1773             : 
    1774             :   // Non-PHI def.
    1775     4534894 :   const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
    1776     2267447 :   if (!MI) {
    1777           0 :     report("No instruction at VNInfo def index", MBB);
    1778           0 :     report_context(LR, Reg, LaneMask);
    1779           0 :     report_context(*VNI);
    1780           0 :     return;
    1781             :   }
    1782             : 
    1783     2267447 :   if (Reg != 0) {
    1784     2265477 :     bool hasDef = false;
    1785     2265477 :     bool isEarlyClobber = false;
    1786    12044966 :     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
    1787    38973803 :       if (!MOI->isReg() || !MOI->isDef())
    1788     7070539 :         continue;
    1789     2708950 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1790     2323544 :         if (MOI->getReg() != Reg)
    1791      231178 :           continue;
    1792             :       } else {
    1793     1096065 :         if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
    1794      650506 :             !TRI->hasRegUnit(MOI->getReg(), Reg))
    1795      211602 :           continue;
    1796             :       }
    1797     2893264 :       if (LaneMask.any() &&
    1798     3135400 :           (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
    1799          14 :         continue;
    1800     2266156 :       hasDef = true;
    1801     4532312 :       if (MOI->isEarlyClobber())
    1802       13449 :         isEarlyClobber = true;
    1803             :     }
    1804             : 
    1805     2265477 :     if (!hasDef) {
    1806           0 :       report("Defining instruction does not modify register", MI);
    1807           0 :       report_context(LR, Reg, LaneMask);
    1808           0 :       report_context(*VNI);
    1809             :     }
    1810             : 
    1811             :     // Early clobber defs begin at USE slots, but other defs must begin at
    1812             :     // DEF slots.
    1813     2265477 :     if (isEarlyClobber) {
    1814       26898 :       if (!VNI->def.isEarlyClobber()) {
    1815           0 :         report("Early clobber def must be at an early-clobber slot", MBB);
    1816           0 :         report_context(LR, Reg, LaneMask);
    1817           0 :         report_context(*VNI);
    1818             :       }
    1819     4504056 :     } else if (!VNI->def.isRegister()) {
    1820           0 :       report("Non-PHI, non-early clobber def must be at a register slot", MBB);
    1821           0 :       report_context(LR, Reg, LaneMask);
    1822           0 :       report_context(*VNI);
    1823             :     }
    1824             :   }
    1825             : }
    1826             : 
    1827     2587401 : void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
    1828             :                                              const LiveRange::const_iterator I,
    1829             :                                              unsigned Reg, LaneBitmask LaneMask)
    1830             : {
    1831     2587401 :   const LiveRange::Segment &S = *I;
    1832     2587401 :   const VNInfo *VNI = S.valno;
    1833             :   assert(VNI && "Live segment has no valno");
    1834             : 
    1835     7762203 :   if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) {
    1836           0 :     report("Foreign valno in live segment", MF);
    1837           0 :     report_context(LR, Reg, LaneMask);
    1838           0 :     report_context(S);
    1839           0 :     report_context(*VNI);
    1840             :   }
    1841             : 
    1842     2587401 :   if (VNI->isUnused()) {
    1843           0 :     report("Live segment valno is marked unused", MF);
    1844           0 :     report_context(LR, Reg, LaneMask);
    1845           0 :     report_context(S);
    1846             :   }
    1847             : 
    1848     5174802 :   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start);
    1849     2587401 :   if (!MBB) {
    1850           0 :     report("Bad start of live segment, no basic block", MF);
    1851           0 :     report_context(LR, Reg, LaneMask);
    1852           0 :     report_context(S);
    1853           0 :     return;
    1854             :   }
    1855     5174802 :   SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
    1856     7442249 :   if (S.start != MBBStartIdx && S.start != VNI->def) {
    1857           0 :     report("Live segment must begin at MBB entry or valno def", MBB);
    1858           0 :     report_context(LR, Reg, LaneMask);
    1859           0 :     report_context(S);
    1860             :   }
    1861             : 
    1862             :   const MachineBasicBlock *EndMBB =
    1863     7762203 :     LiveInts->getMBBFromIndex(S.end.getPrevSlot());
    1864     2587401 :   if (!EndMBB) {
    1865           0 :     report("Bad end of live segment, no basic block", MF);
    1866           0 :     report_context(LR, Reg, LaneMask);
    1867           0 :     report_context(S);
    1868           0 :     return;
    1869             :   }
    1870             : 
    1871             :   // No more checks for live-out segments.
    1872     7762203 :   if (S.end == LiveInts->getMBBEndIdx(EndMBB))
    1873             :     return;
    1874             : 
    1875             :   // RegUnit intervals are allowed dead phis.
    1876     3250333 :   if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() &&
    1877     3912708 :       S.start == VNI->def && S.end == VNI->def.getDeadSlot())
    1878             :     return;
    1879             : 
    1880             :   // The live segment is ending inside EndMBB
    1881             :   const MachineInstr *MI =
    1882     7538691 :     LiveInts->getInstructionFromIndex(S.end.getPrevSlot());
    1883     2512897 :   if (!MI) {
    1884           0 :     report("Live segment doesn't end at a valid instruction", EndMBB);
    1885           0 :     report_context(LR, Reg, LaneMask);
    1886           0 :     report_context(S);
    1887           0 :     return;
    1888             :   }
    1889             : 
    1890             :   // The block slot must refer to a basic block boundary.
    1891     5025794 :   if (S.end.isBlock()) {
    1892           0 :     report("Live segment ends at B slot of an instruction", EndMBB);
    1893           0 :     report_context(LR, Reg, LaneMask);
    1894           0 :     report_context(S);
    1895             :   }
    1896             : 
    1897     5025794 :   if (S.end.isDead()) {
    1898             :     // Segment ends on the dead slot.
    1899             :     // That means there must be a dead def.
    1900       84692 :     if (!SlotIndex::isSameInstr(S.start, S.end)) {
    1901           0 :       report("Live segment ending at dead slot spans instructions", EndMBB);
    1902           0 :       report_context(LR, Reg, LaneMask);
    1903           0 :       report_context(S);
    1904             :     }
    1905             :   }
    1906             : 
    1907             :   // A live segment can only end at an early-clobber slot if it is being
    1908             :   // redefined by an early-clobber def.
    1909     5025794 :   if (S.end.isEarlyClobber()) {
    1910       16284 :     if (I+1 == LR.end() || (I+1)->start != S.end) {
    1911           0 :       report("Live segment ending at early clobber slot must be "
    1912             :              "redefined by an EC def in the same instruction", EndMBB);
    1913           0 :       report_context(LR, Reg, LaneMask);
    1914           0 :       report_context(S);
    1915             :     }
    1916             :   }
    1917             : 
    1918             :   // The following checks only apply to virtual registers. Physreg liveness
    1919             :   // is too weird to check.
    1920     2512897 :   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    1921             :     // A live segment can end with either a redefinition, a kill flag on a
    1922             :     // use, or a dead flag on a def.
    1923     2062634 :     bool hasRead = false;
    1924     2062634 :     bool hasSubRegDef = false;
    1925     2062634 :     bool hasDeadDef = false;
    1926    13386205 :     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
    1927    38330450 :       if (!MOI->isReg() || MOI->getReg() != Reg)
    1928     9152410 :         continue;
    1929     4342322 :       unsigned Sub = MOI->getSubReg();
    1930      539869 :       LaneBitmask SLM = Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
    1931     3250899 :                                  : LaneBitmask::getAll();
    1932     4342322 :       if (MOI->isDef()) {
    1933      344600 :         if (Sub != 0) {
    1934      277848 :           hasSubRegDef = true;
    1935             :           // An operand vreg0:sub0<def> reads vreg0:sub1..n. Invert the lane
    1936             :           // mask for subregister defs. Read-undef defs will be handled by
    1937             :           // readsReg below.
    1938      277848 :           SLM = ~SLM;
    1939             :         }
    1940      689200 :         if (MOI->isDead())
    1941       12989 :           hasDeadDef = true;
    1942             :       }
    1943     2825814 :       if (LaneMask.any() && (LaneMask & SLM).none())
    1944       12133 :         continue;
    1945     2225780 :       if (MOI->readsReg())
    1946             :         hasRead = true;
    1947             :     }
    1948     4125268 :     if (S.end.isDead()) {
    1949             :       // Make sure that the corresponding machine operand for a "dead" live
    1950             :       // range has the dead flag. We cannot perform this check for subregister
    1951             :       // liveranges as partially dead values are allowed.
    1952       14224 :       if (LaneMask.none() && !hasDeadDef) {
    1953           0 :         report("Instruction ending live segment on dead slot has no dead flag",
    1954             :                MI);
    1955           0 :         report_context(LR, Reg, LaneMask);
    1956           0 :         report_context(S);
    1957             :       }
    1958             :     } else {
    1959     2048410 :       if (!hasRead) {
    1960             :         // When tracking subregister liveness, the main range must start new
    1961             :         // values on partial register writes, even if there is no read.
    1962           2 :         if (!MRI->shouldTrackSubRegLiveness(Reg) || LaneMask.any() ||
    1963             :             !hasSubRegDef) {
    1964           0 :           report("Instruction ending live segment doesn't read the register",
    1965             :                  MI);
    1966           0 :           report_context(LR, Reg, LaneMask);
    1967           0 :           report_context(S);
    1968             :         }
    1969             :       }
    1970             :     }
    1971             :   }
    1972             : 
    1973             :   // Now check all the basic blocks in this live segment.
    1974     5025794 :   MachineFunction::const_iterator MFI = MBB->getIterator();
    1975             :   // Is this live segment the beginning of a non-PHIDef VN?
    1976     7534020 :   if (S.start == VNI->def && !VNI->isPHIDef()) {
    1977             :     // Not live-in to any blocks.
    1978     2216356 :     if (MBB == EndMBB)
    1979             :       return;
    1980             :     // Skip this block.
    1981             :     ++MFI;
    1982             :   }
    1983             :   while (true) {
    1984             :     assert(LiveInts->isLiveInToMBB(LR, &*MFI));
    1985             :     // We don't know how to track physregs into a landing pad.
    1986      648969 :     if (!TargetRegisterInfo::isVirtualRegister(Reg) &&
    1987      275155 :         MFI->isEHPad()) {
    1988          44 :       if (&*MFI == EndMBB)
    1989             :         break;
    1990           0 :       ++MFI;
    1991           0 :       continue;
    1992             :     }
    1993             : 
    1994             :     // Is VNI a PHI-def in the current block?
    1995      671737 :     bool IsPHI = VNI->isPHIDef() &&
    1996     1565638 :       VNI->def == LiveInts->getMBBStartIdx(&*MFI);
    1997             : 
    1998             :     // Check that VNI is live-out of all predecessors.
    1999      747540 :     for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
    2000     1269792 :          PE = MFI->pred_end(); PI != PE; ++PI) {
    2001      296964 :       SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
    2002      148482 :       const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
    2003             : 
    2004             :       // All predecessors must have a live-out value. However for a phi
    2005             :       // instruction with subregister intervals
    2006             :       // only one of the subregisters (not necessarily the current one) needs to
    2007             :       // be defined.
    2008      148482 :       if (!PVNI && (LaneMask.none() || !IsPHI) ) {
    2009           0 :         report("Register not marked live out of predecessor", *PI);
    2010           0 :         report_context(LR, Reg, LaneMask);
    2011           0 :         report_context(*VNI);
    2012           0 :         errs() << " live into BB#" << MFI->getNumber()
    2013           0 :                << '@' << LiveInts->getMBBStartIdx(&*MFI) << ", not live before "
    2014           0 :                << PEnd << '\n';
    2015           0 :         continue;
    2016             :       }
    2017             : 
    2018             :       // Only PHI-defs can take different predecessor values.
    2019      148482 :       if (!IsPHI && PVNI != VNI) {
    2020           0 :         report("Different value live out of predecessor", *PI);
    2021           0 :         report_context(LR, Reg, LaneMask);
    2022           0 :         errs() << "Valno #" << PVNI->id << " live out of BB#"
    2023           0 :                << (*PI)->getNumber() << '@' << PEnd << "\nValno #" << VNI->id
    2024           0 :                << " live into BB#" << MFI->getNumber() << '@'
    2025           0 :                << LiveInts->getMBBStartIdx(&*MFI) << '\n';
    2026             :       }
    2027             :     }
    2028      373770 :     if (&*MFI == EndMBB)
    2029             :       break;
    2030             :     ++MFI;
    2031             :   }
    2032             : }
    2033             : 
    2034     2208746 : void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg,
    2035             :                                       LaneBitmask LaneMask) {
    2036     9197884 :   for (const VNInfo *VNI : LR.valnos)
    2037     2571646 :     verifyLiveRangeValue(LR, VNI, Reg, LaneMask);
    2038             : 
    2039     7004893 :   for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I)
    2040     2587401 :     verifyLiveRangeSegment(LR, I, Reg, LaneMask);
    2041     2208746 : }
    2042             : 
    2043     1135405 : void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
    2044     1135405 :   unsigned Reg = LI.reg;
    2045             :   assert(TargetRegisterInfo::isVirtualRegister(Reg));
    2046     1135405 :   verifyLiveRange(LI, Reg);
    2047             : 
    2048     1135405 :   LaneBitmask Mask;
    2049     1135405 :   LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
    2050     2880922 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
    2051      610112 :     if ((Mask & SR.LaneMask).any()) {
    2052           0 :       report("Lane masks of sub ranges overlap in live interval", MF);
    2053           0 :       report_context(LI);
    2054             :     }
    2055     1220224 :     if ((SR.LaneMask & ~MaxMask).any()) {
    2056           0 :       report("Subrange lanemask is invalid", MF);
    2057           0 :       report_context(LI);
    2058             :     }
    2059     1220224 :     if (SR.empty()) {
    2060           0 :       report("Subrange must not be empty", MF);
    2061           0 :       report_context(SR, LI.reg, SR.LaneMask);
    2062             :     }
    2063      610112 :     Mask |= SR.LaneMask;
    2064      610112 :     verifyLiveRange(SR, LI.reg, SR.LaneMask);
    2065      610112 :     if (!LI.covers(SR)) {
    2066           0 :       report("A Subrange is not covered by the main range", MF);
    2067           0 :       report_context(LI);
    2068             :     }
    2069             :   }
    2070             : 
    2071             :   // Check the LI only has one connected component.
    2072     3406215 :   ConnectedVNInfoEqClasses ConEQ(*LiveInts);
    2073     1135405 :   unsigned NumComp = ConEQ.Classify(LI);
    2074     1135405 :   if (NumComp > 1) {
    2075           0 :     report("Multiple connected components in live interval", MF);
    2076           0 :     report_context(LI);
    2077           0 :     for (unsigned comp = 0; comp != NumComp; ++comp) {
    2078           0 :       errs() << comp << ": valnos";
    2079           0 :       for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
    2080           0 :            E = LI.vni_end(); I!=E; ++I)
    2081           0 :         if (comp == ConEQ.getEqClass(*I))
    2082           0 :           errs() << ' ' << (*I)->id;
    2083           0 :       errs() << '\n';
    2084             :     }
    2085             :   }
    2086     1135405 : }
    2087             : 
    2088             : namespace {
    2089             : 
    2090             :   // FrameSetup and FrameDestroy can have zero adjustment, so using a single
    2091             :   // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
    2092             :   // value is zero.
    2093             :   // We use a bool plus an integer to capture the stack state.
    2094             :   struct StackStateOfBB {
    2095             :     StackStateOfBB() = default;
    2096             :     StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
    2097             :       EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
    2098             :       ExitIsSetup(ExitSetup) {}
    2099             : 
    2100             :     // Can be negative, which means we are setting up a frame.
    2101             :     int EntryValue = 0;
    2102             :     int ExitValue = 0;
    2103             :     bool EntryIsSetup = false;
    2104             :     bool ExitIsSetup = false;
    2105             :   };
    2106             : 
    2107             : } // end anonymous namespace
    2108             : 
    2109             : /// Make sure on every path through the CFG, a FrameSetup <n> is always followed
    2110             : /// by a FrameDestroy <n>, stack adjustments are identical on all
    2111             : /// CFG edges to a merge point, and frame is destroyed at end of a return block.
    2112     1128028 : void MachineVerifier::verifyStackFrame() {
    2113     1128028 :   unsigned FrameSetupOpcode   = TII->getCallFrameSetupOpcode();
    2114     1128028 :   unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
    2115     1128028 :   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
    2116        3497 :     return;
    2117             : 
    2118     2249062 :   SmallVector<StackStateOfBB, 8> SPState;
    2119     2249062 :   SPState.resize(MF->getNumBlockIDs());
    2120     2249062 :   df_iterator_default_set<const MachineBasicBlock*> Reachable;
    2121             : 
    2122             :   // Visit the MBBs in DFS order.
    2123             :   for (df_ext_iterator<const MachineFunction *,
    2124             :                        df_iterator_default_set<const MachineBasicBlock *>>
    2125     3373593 :        DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
    2126     2542723 :        DFI != DFE; ++DFI) {
    2127     1418192 :     const MachineBasicBlock *MBB = *DFI;
    2128             : 
    2129     1418192 :     StackStateOfBB BBState;
    2130             :     // Check the exit state of the DFS stack predecessor.
    2131     1418192 :     if (DFI.getPathLength() >= 2) {
    2132      587322 :       const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
    2133             :       assert(Reachable.count(StackPred) &&
    2134             :              "DFS stack predecessor is already visited.\n");
    2135      587322 :       BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
    2136      587322 :       BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
    2137      293661 :       BBState.ExitValue = BBState.EntryValue;
    2138      293661 :       BBState.ExitIsSetup = BBState.EntryIsSetup;
    2139             :     }
    2140             : 
    2141             :     // Update stack state by checking contents of MBB.
    2142    41958262 :     for (const auto &I : *MBB) {
    2143    18142747 :       if (I.getOpcode() == FrameSetupOpcode) {
    2144       94613 :         if (BBState.ExitIsSetup)
    2145           0 :           report("FrameSetup is after another FrameSetup", &I);
    2146      189226 :         BBState.ExitValue -= TII->getFrameTotalSize(I);
    2147       94613 :         BBState.ExitIsSetup = true;
    2148             :       }
    2149             : 
    2150    18142747 :       if (I.getOpcode() == FrameDestroyOpcode) {
    2151      189226 :         int Size = TII->getFrameTotalSize(I);
    2152       94613 :         if (!BBState.ExitIsSetup)
    2153           0 :           report("FrameDestroy is not after a FrameSetup", &I);
    2154       94613 :         int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
    2155             :                                                BBState.ExitValue;
    2156       94613 :         if (BBState.ExitIsSetup && AbsSPAdj != Size) {
    2157           0 :           report("FrameDestroy <n> is after FrameSetup <m>", &I);
    2158           0 :           errs() << "FrameDestroy <" << Size << "> is after FrameSetup <"
    2159           0 :               << AbsSPAdj << ">.\n";
    2160             :         }
    2161       94613 :         BBState.ExitValue += Size;
    2162       94613 :         BBState.ExitIsSetup = false;
    2163             :       }
    2164             :     }
    2165     2836384 :     SPState[MBB->getNumber()] = BBState;
    2166             : 
    2167             :     // Make sure the exit state of any predecessor is consistent with the entry
    2168             :     // state.
    2169     1418192 :     for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
    2170     3253603 :          E = MBB->pred_end(); I != E; ++I) {
    2171      782676 :       if (Reachable.count(*I) &&
    2172     1096371 :           (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue ||
    2173      730914 :            SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
    2174           0 :         report("The exit stack state of a predecessor is inconsistent.", MBB);
    2175           0 :         errs() << "Predecessor BB#" << (*I)->getNumber() << " has exit state ("
    2176           0 :             << SPState[(*I)->getNumber()].ExitValue << ", "
    2177           0 :             << SPState[(*I)->getNumber()].ExitIsSetup
    2178           0 :             << "), while BB#" << MBB->getNumber() << " has entry state ("
    2179           0 :             << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
    2180             :       }
    2181             :     }
    2182             : 
    2183             :     // Make sure the entry state of any successor is consistent with the exit
    2184             :     // state.
    2185     1418192 :     for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
    2186     3253539 :          E = MBB->succ_end(); I != E; ++I) {
    2187      506985 :       if (Reachable.count(*I) &&
    2188      269490 :           (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue ||
    2189      179660 :            SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
    2190           0 :         report("The entry stack state of a successor is inconsistent.", MBB);
    2191           0 :         errs() << "Successor BB#" << (*I)->getNumber() << " has entry state ("
    2192           0 :             << SPState[(*I)->getNumber()].EntryValue << ", "
    2193           0 :             << SPState[(*I)->getNumber()].EntryIsSetup
    2194           0 :             << "), while BB#" << MBB->getNumber() << " has exit state ("
    2195           0 :             << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
    2196             :       }
    2197             :     }
    2198             : 
    2199             :     // Make sure a basic block with return ends with zero stack adjustment.
    2200     4226678 :     if (!MBB->empty() && MBB->back().isReturn()) {
    2201     1138425 :       if (BBState.ExitIsSetup)
    2202           0 :         report("A return block ends with a FrameSetup.", MBB);
    2203     1138425 :       if (BBState.ExitValue)
    2204           0 :         report("A return block ends with a nonzero stack adjustment.", MBB);
    2205             :     }
    2206             :   }
    2207             : }

Generated by: LCOV version 1.13