contrib/llvm-project/llvm/lib/CodeGen/MachineVerifier.cpp

   1 //===- MachineVerifier.cpp - Machine Code Verifier ------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Pass to verify generated machine code. The following is checked:
  10 //
  11 // Operand counts: All explicit operands must be present.
  12 //
  13 // Register classes: All physical and virtual register operands must be
  14 // compatible with the register class required by the instruction descriptor.
  15 //
  16 // Register live intervals: Registers must be defined only once, and must be
  17 // defined before use.
  18 //
  19 // The machine code verifier is enabled from LLVMTargetMachine.cpp with the
  20 // command-line option -verify-machineinstrs, or by defining the environment
  21 // variable LLVM_VERIFY_MACHINEINSTRS to the name of a file that will receive
  22 // the verifier errors.
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "LiveRangeCalc.h"
  26 #include "llvm/ADT/BitVector.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/ADT/DenseSet.h"
  29 #include "llvm/ADT/DepthFirstIterator.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/ADT/SetOperations.h"
  32 #include "llvm/ADT/SmallPtrSet.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/ADT/StringRef.h"
  35 #include "llvm/ADT/Twine.h"
  36 #include "llvm/Analysis/EHPersonalities.h"
  37 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
  38 #include "llvm/CodeGen/LiveInterval.h"
  39 #include "llvm/CodeGen/LiveIntervals.h"
  40 #include "llvm/CodeGen/LiveStacks.h"
  41 #include "llvm/CodeGen/LiveVariables.h"
  42 #include "llvm/CodeGen/MachineBasicBlock.h"
  43 #include "llvm/CodeGen/MachineFrameInfo.h"
  44 #include "llvm/CodeGen/MachineFunction.h"
  45 #include "llvm/CodeGen/MachineFunctionPass.h"
  46 #include "llvm/CodeGen/MachineInstr.h"
  47 #include "llvm/CodeGen/MachineInstrBundle.h"
  48 #include "llvm/CodeGen/MachineMemOperand.h"
  49 #include "llvm/CodeGen/MachineOperand.h"
  50 #include "llvm/CodeGen/MachineRegisterInfo.h"
  51 #include "llvm/CodeGen/PseudoSourceValue.h"
  52 #include "llvm/CodeGen/SlotIndexes.h"
  53 #include "llvm/CodeGen/StackMaps.h"
  54 #include "llvm/CodeGen/TargetInstrInfo.h"
  55 #include "llvm/CodeGen/TargetOpcodes.h"
  56 #include "llvm/CodeGen/TargetRegisterInfo.h"
  57 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  58 #include "llvm/IR/BasicBlock.h"
  59 #include "llvm/IR/Function.h"
  60 #include "llvm/IR/InlineAsm.h"
  61 #include "llvm/IR/Instructions.h"
  62 #include "llvm/MC/LaneBitmask.h"
  63 #include "llvm/MC/MCAsmInfo.h"
  64 #include "llvm/MC/MCInstrDesc.h"
  65 #include "llvm/MC/MCRegisterInfo.h"
  66 #include "llvm/MC/MCTargetOptions.h"
  67 #include "llvm/Pass.h"
  68 #include "llvm/Support/Casting.h"
  69 #include "llvm/Support/ErrorHandling.h"
  70 #include "llvm/Support/LowLevelTypeImpl.h"
  71 #include "llvm/Support/MathExtras.h"
  72 #include "llvm/Support/raw_ostream.h"
  73 #include "llvm/Target/TargetMachine.h"
  74 #include <algorithm>
  75 #include <cassert>
  76 #include <cstddef>
  77 #include <cstdint>
  78 #include <iterator>
  79 #include <string>
  80 #include <utility>
  81
  82 using namespace llvm;
  83
  84 namespace {
  85
  86   struct MachineVerifier {
  87     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 *FirstNonPHI;
 112     const MachineInstr *FirstTerminator;
 113     BlockSet FunctionBlocks;
 114
 115     BitVector regsReserved;
 116     RegSet regsLive;
 117     RegVector regsDefined, regsDead, regsKilled;
 118     RegMaskVector regMasks;
 119
 120     SlotIndex lastIndex;
 121
 122     // Add Reg and any sub-registers to RV
 123     void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
 124       RV.push_back(Reg);
 125       if (TargetRegisterInfo::isPhysicalRegister(Reg))
 126         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
 127           RV.push_back(*SubRegs);
 128     }
 129
 130     struct BBInfo {
 131       // Is this MBB reachable from the MF entry point?
 132       bool reachable = false;
 133
 134       // Vregs that must be live in because they are used without being
 135       // defined. Map value is the user.
 136       RegMap vregsLiveIn;
 137
 138       // Regs killed in MBB. They may be defined again, and will then be in both
 139       // regsKilled and regsLiveOut.
 140       RegSet regsKilled;
 141
 142       // Regs defined in MBB and live out. Note that vregs passing through may
 143       // be live out without being mentioned here.
 144       RegSet regsLiveOut;
 145
 146       // Vregs that pass through MBB untouched. This set is disjoint from
 147       // regsKilled and regsLiveOut.
 148       RegSet vregsPassed;
 149
 150       // Vregs that must pass through MBB because they are needed by a successor
 151       // block. This set is disjoint from regsLiveOut.
 152       RegSet vregsRequired;
 153
 154       // Set versions of block's predecessor and successor lists.
 155       BlockSet Preds, Succs;
 156
 157       BBInfo() = default;
 158
 159       // Add register to vregsPassed if it belongs there. Return true if
 160       // anything changed.
 161       bool addPassed(unsigned Reg) {
 162         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 163           return false;
 164         if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
 165           return false;
 166         return vregsPassed.insert(Reg).second;
 167       }
 168
 169       // Same for a full set.
 170       bool addPassed(const RegSet &RS) {
 171         bool changed = false;
 172         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
 173           if (addPassed(*I))
 174             changed = true;
 175         return changed;
 176       }
 177
 178       // Add register to vregsRequired if it belongs there. Return true if
 179       // anything changed.
 180       bool addRequired(unsigned Reg) {
 181         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 182           return false;
 183         if (regsLiveOut.count(Reg))
 184           return false;
 185         return vregsRequired.insert(Reg).second;
 186       }
 187
 188       // Same for a full set.
 189       bool addRequired(const RegSet &RS) {
 190         bool changed = false;
 191         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
 192           if (addRequired(*I))
 193             changed = true;
 194         return changed;
 195       }
 196
 197       // Same for a full map.
 198       bool addRequired(const RegMap &RM) {
 199         bool changed = false;
 200         for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
 201           if (addRequired(I->first))
 202             changed = true;
 203         return changed;
 204       }
 205
 206       // Live-out registers are either in regsLiveOut or vregsPassed.
 207       bool isLiveOut(unsigned Reg) const {
 208         return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
 209       }
 210     };
 211
 212     // Extra register info per MBB.
 213     DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
 214
 215     bool isReserved(unsigned Reg) {
 216       return Reg < regsReserved.size() && regsReserved.test(Reg);
 217     }
 218
 219     bool isAllocatable(unsigned Reg) const {
 220       return Reg < TRI->getNumRegs() && TRI->isInAllocatableClass(Reg) &&
 221              !regsReserved.test(Reg);
 222     }
 223
 224     // Analysis information if available
 225     LiveVariables *LiveVars;
 226     LiveIntervals *LiveInts;
 227     LiveStacks *LiveStks;
 228     SlotIndexes *Indexes;
 229
 230     void visitMachineFunctionBefore();
 231     void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
 232     void visitMachineBundleBefore(const MachineInstr *MI);
 233
 234     bool verifyVectorElementMatch(LLT Ty0, LLT Ty1, const MachineInstr *MI);
 235     void verifyPreISelGenericInstruction(const MachineInstr *MI);
 236     void visitMachineInstrBefore(const MachineInstr *MI);
 237     void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
 238     void visitMachineInstrAfter(const MachineInstr *MI);
 239     void visitMachineBundleAfter(const MachineInstr *MI);
 240     void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
 241     void visitMachineFunctionAfter();
 242
 243     void report(const char *msg, const MachineFunction *MF);
 244     void report(const char *msg, const MachineBasicBlock *MBB);
 245     void report(const char *msg, const MachineInstr *MI);
 246     void report(const char *msg, const MachineOperand *MO, unsigned MONum,
 247                 LLT MOVRegType = LLT{});
 248
 249     void report_context(const LiveInterval &LI) const;
 250     void report_context(const LiveRange &LR, unsigned VRegUnit,
 251                         LaneBitmask LaneMask) const;
 252     void report_context(const LiveRange::Segment &S) const;
 253     void report_context(const VNInfo &VNI) const;
 254     void report_context(SlotIndex Pos) const;
 255     void report_context(MCPhysReg PhysReg) const;
 256     void report_context_liverange(const LiveRange &LR) const;
 257     void report_context_lanemask(LaneBitmask LaneMask) const;
 258     void report_context_vreg(unsigned VReg) const;
 259     void report_context_vreg_regunit(unsigned VRegOrUnit) const;
 260
 261     void verifyInlineAsm(const MachineInstr *MI);
 262
 263     void checkLiveness(const MachineOperand *MO, unsigned MONum);
 264     void checkLivenessAtUse(const MachineOperand *MO, unsigned MONum,
 265                             SlotIndex UseIdx, const LiveRange &LR, unsigned VRegOrUnit,
 266                             LaneBitmask LaneMask = LaneBitmask::getNone());
 267     void checkLivenessAtDef(const MachineOperand *MO, unsigned MONum,
 268                             SlotIndex DefIdx, const LiveRange &LR, unsigned VRegOrUnit,
 269                             bool SubRangeCheck = false,
 270                             LaneBitmask LaneMask = LaneBitmask::getNone());
 271
 272     void markReachable(const MachineBasicBlock *MBB);
 273     void calcRegsPassed();
 274     void checkPHIOps(const MachineBasicBlock &MBB);
 275
 276     void calcRegsRequired();
 277     void verifyLiveVariables();
 278     void verifyLiveIntervals();
 279     void verifyLiveInterval(const LiveInterval&);
 280     void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned,
 281                               LaneBitmask);
 282     void verifyLiveRangeSegment(const LiveRange&,
 283                                 const LiveRange::const_iterator I, unsigned,
 284                                 LaneBitmask);
 285     void verifyLiveRange(const LiveRange&, unsigned,
 286                          LaneBitmask LaneMask = LaneBitmask::getNone());
 287
 288     void verifyStackFrame();
 289
 290     void verifySlotIndexes() const;
 291     void verifyProperties(const MachineFunction &MF);
 292   };
 293
 294   struct MachineVerifierPass : public MachineFunctionPass {
 295     static char ID; // Pass ID, replacement for typeid
 296
 297     const std::string Banner;
 298
 299     MachineVerifierPass(std::string banner = std::string())
 300       : MachineFunctionPass(ID), Banner(std::move(banner)) {
 301         initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
 302       }
 303
 304     void getAnalysisUsage(AnalysisUsage &AU) const override {
 305       AU.setPreservesAll();
 306       MachineFunctionPass::getAnalysisUsage(AU);
 307     }
 308
 309     bool runOnMachineFunction(MachineFunction &MF) override {
 310       unsigned FoundErrors = MachineVerifier(this, Banner.c_str()).verify(MF);
 311       if (FoundErrors)
 312         report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
 313       return false;
 314     }
 315   };
 316
 317 } // end anonymous namespace
 318
 319 char MachineVerifierPass::ID = 0;
 320
 321 INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
 322                 "Verify generated machine code", false, false)
 323
 324 FunctionPass *llvm::createMachineVerifierPass(const std::string &Banner) {
 325   return new MachineVerifierPass(Banner);
 326 }
 327
 328 bool MachineFunction::verify(Pass *p, const char *Banner, bool AbortOnErrors)
 329     const {
 330   MachineFunction &MF = const_cast<MachineFunction&>(*this);
 331   unsigned FoundErrors = MachineVerifier(p, Banner).verify(MF);
 332   if (AbortOnErrors && FoundErrors)
 333     report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
 334   return FoundErrors == 0;
 335 }
 336
 337 void MachineVerifier::verifySlotIndexes() const {
 338   if (Indexes == nullptr)
 339     return;
 340
 341   // Ensure the IdxMBB list is sorted by slot indexes.
 342   SlotIndex Last;
 343   for (SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(),
 344        E = Indexes->MBBIndexEnd(); I != E; ++I) {
 345     assert(!Last.isValid() || I->first > Last);
 346     Last = I->first;
 347   }
 348 }
 349
 350 void MachineVerifier::verifyProperties(const MachineFunction &MF) {
 351   // If a pass has introduced virtual registers without clearing the
 352   // NoVRegs property (or set it without allocating the vregs)
 353   // then report an error.
 354   if (MF.getProperties().hasProperty(
 355           MachineFunctionProperties::Property::NoVRegs) &&
 356       MRI->getNumVirtRegs())
 357     report("Function has NoVRegs property but there are VReg operands", &MF);
 358 }
 359
 360 unsigned MachineVerifier::verify(MachineFunction &MF) {
 361   foundErrors = 0;
 362
 363   this->MF = &MF;
 364   TM = &MF.getTarget();
 365   TII = MF.getSubtarget().getInstrInfo();
 366   TRI = MF.getSubtarget().getRegisterInfo();
 367   MRI = &MF.getRegInfo();
 368
 369   const bool isFunctionFailedISel = MF.getProperties().hasProperty(
 370       MachineFunctionProperties::Property::FailedISel);
 371
 372   // If we're mid-GlobalISel and we already triggered the fallback path then
 373   // it's expected that the MIR is somewhat broken but that's ok since we'll
 374   // reset it and clear the FailedISel attribute in ResetMachineFunctions.
 375   if (isFunctionFailedISel)
 376     return foundErrors;
 377
 378   isFunctionRegBankSelected =
 379       !isFunctionFailedISel &&
 380       MF.getProperties().hasProperty(
 381           MachineFunctionProperties::Property::RegBankSelected);
 382   isFunctionSelected = !isFunctionFailedISel &&
 383                        MF.getProperties().hasProperty(
 384                            MachineFunctionProperties::Property::Selected);
 385   LiveVars = nullptr;
 386   LiveInts = nullptr;
 387   LiveStks = nullptr;
 388   Indexes = nullptr;
 389   if (PASS) {
 390     LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
 391     // We don't want to verify LiveVariables if LiveIntervals is available.
 392     if (!LiveInts)
 393       LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
 394     LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
 395     Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
 396   }
 397
 398   verifySlotIndexes();
 399
 400   verifyProperties(MF);
 401
 402   visitMachineFunctionBefore();
 403   for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
 404        MFI!=MFE; ++MFI) {
 405     visitMachineBasicBlockBefore(&*MFI);
 406     // Keep track of the current bundle header.
 407     const MachineInstr *CurBundle = nullptr;
 408     // Do we expect the next instruction to be part of the same bundle?
 409     bool InBundle = false;
 410
 411     for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
 412            MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
 413       if (MBBI->getParent() != &*MFI) {
 414         report("Bad instruction parent pointer", &*MFI);
 415         errs() << "Instruction: " << *MBBI;
 416         continue;
 417       }
 418
 419       // Check for consistent bundle flags.
 420       if (InBundle && !MBBI->isBundledWithPred())
 421         report("Missing BundledPred flag, "
 422                "BundledSucc was set on predecessor",
 423                &*MBBI);
 424       if (!InBundle && MBBI->isBundledWithPred())
 425         report("BundledPred flag is set, "
 426                "but BundledSucc not set on predecessor",
 427                &*MBBI);
 428
 429       // Is this a bundle header?
 430       if (!MBBI->isInsideBundle()) {
 431         if (CurBundle)
 432           visitMachineBundleAfter(CurBundle);
 433         CurBundle = &*MBBI;
 434         visitMachineBundleBefore(CurBundle);
 435       } else if (!CurBundle)
 436         report("No bundle header", &*MBBI);
 437       visitMachineInstrBefore(&*MBBI);
 438       for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) {
 439         const MachineInstr &MI = *MBBI;
 440         const MachineOperand &Op = MI.getOperand(I);
 441         if (Op.getParent() != &MI) {
 442           // Make sure to use correct addOperand / RemoveOperand / ChangeTo
 443           // functions when replacing operands of a MachineInstr.
 444           report("Instruction has operand with wrong parent set", &MI);
 445         }
 446
 447         visitMachineOperand(&Op, I);
 448       }
 449
 450       visitMachineInstrAfter(&*MBBI);
 451
 452       // Was this the last bundled instruction?
 453       InBundle = MBBI->isBundledWithSucc();
 454     }
 455     if (CurBundle)
 456       visitMachineBundleAfter(CurBundle);
 457     if (InBundle)
 458       report("BundledSucc flag set on last instruction in block", &MFI->back());
 459     visitMachineBasicBlockAfter(&*MFI);
 460   }
 461   visitMachineFunctionAfter();
 462
 463   // Clean up.
 464   regsLive.clear();
 465   regsDefined.clear();
 466   regsDead.clear();
 467   regsKilled.clear();
 468   regMasks.clear();
 469   MBBInfoMap.clear();
 470
 471   return foundErrors;
 472 }
 473
 474 void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
 475   assert(MF);
 476   errs() << '\n';
 477   if (!foundErrors++) {
 478     if (Banner)
 479       errs() << "# " << Banner << '\n';
 480     if (LiveInts != nullptr)
 481       LiveInts->print(errs());
 482     else
 483       MF->print(errs(), Indexes);
 484   }
 485   errs() << "*** Bad machine code: " << msg << " ***\n"
 486       << "- function:    " << MF->getName() << "\n";
 487 }
 488
 489 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
 490   assert(MBB);
 491   report(msg, MBB->getParent());
 492   errs() << "- basic block: " << printMBBReference(*MBB) << ' '
 493          << MBB->getName() << " (" << (const void *)MBB << ')';
 494   if (Indexes)
 495     errs() << " [" << Indexes->getMBBStartIdx(MBB)
 496         << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
 497   errs() << '\n';
 498 }
 499
 500 void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
 501   assert(MI);
 502   report(msg, MI->getParent());
 503   errs() << "- instruction: ";
 504   if (Indexes && Indexes->hasIndex(*MI))
 505     errs() << Indexes->getInstructionIndex(*MI) << '\t';
 506   MI->print(errs(), /*SkipOpers=*/true);
 507 }
 508
 509 void MachineVerifier::report(const char *msg, const MachineOperand *MO,
 510                              unsigned MONum, LLT MOVRegType) {
 511   assert(MO);
 512   report(msg, MO->getParent());
 513   errs() << "- operand " << MONum << ":   ";
 514   MO->print(errs(), MOVRegType, TRI);
 515   errs() << "\n";
 516 }
 517
 518 void MachineVerifier::report_context(SlotIndex Pos) const {
 519   errs() << "- at:          " << Pos << '\n';
 520 }
 521
 522 void MachineVerifier::report_context(const LiveInterval &LI) const {
 523   errs() << "- interval:    " << LI << '\n';
 524 }
 525
 526 void MachineVerifier::report_context(const LiveRange &LR, unsigned VRegUnit,
 527                                      LaneBitmask LaneMask) const {
 528   report_context_liverange(LR);
 529   report_context_vreg_regunit(VRegUnit);
 530   if (LaneMask.any())
 531     report_context_lanemask(LaneMask);
 532 }
 533
 534 void MachineVerifier::report_context(const LiveRange::Segment &S) const {
 535   errs() << "- segment:     " << S << '\n';
 536 }
 537
 538 void MachineVerifier::report_context(const VNInfo &VNI) const {
 539   errs() << "- ValNo:       " << VNI.id << " (def " << VNI.def << ")\n";
 540 }
 541
 542 void MachineVerifier::report_context_liverange(const LiveRange &LR) const {
 543   errs() << "- liverange:   " << LR << '\n';
 544 }
 545
 546 void MachineVerifier::report_context(MCPhysReg PReg) const {
 547   errs() << "- p. register: " << printReg(PReg, TRI) << '\n';
 548 }
 549
 550 void MachineVerifier::report_context_vreg(unsigned VReg) const {
 551   errs() << "- v. register: " << printReg(VReg, TRI) << '\n';
 552 }
 553
 554 void MachineVerifier::report_context_vreg_regunit(unsigned VRegOrUnit) const {
 555   if (TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) {
 556     report_context_vreg(VRegOrUnit);
 557   } else {
 558     errs() << "- regunit:     " << printRegUnit(VRegOrUnit, TRI) << '\n';
 559   }
 560 }
 561
 562 void MachineVerifier::report_context_lanemask(LaneBitmask LaneMask) const {
 563   errs() << "- lanemask:    " << PrintLaneMask(LaneMask) << '\n';
 564 }
 565
 566 void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
 567   BBInfo &MInfo = MBBInfoMap[MBB];
 568   if (!MInfo.reachable) {
 569     MInfo.reachable = true;
 570     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
 571            SuE = MBB->succ_end(); SuI != SuE; ++SuI)
 572       markReachable(*SuI);
 573   }
 574 }
 575
 576 void MachineVerifier::visitMachineFunctionBefore() {
 577   lastIndex = SlotIndex();
 578   regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs()
 579                                            : TRI->getReservedRegs(*MF);
 580
 581   if (!MF->empty())
 582     markReachable(&MF->front());
 583
 584   // Build a set of the basic blocks in the function.
 585   FunctionBlocks.clear();
 586   for (const auto &MBB : *MF) {
 587     FunctionBlocks.insert(&MBB);
 588     BBInfo &MInfo = MBBInfoMap[&MBB];
 589
 590     MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end());
 591     if (MInfo.Preds.size() != MBB.pred_size())
 592       report("MBB has duplicate entries in its predecessor list.", &MBB);
 593
 594     MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end());
 595     if (MInfo.Succs.size() != MBB.succ_size())
 596       report("MBB has duplicate entries in its successor list.", &MBB);
 597   }
 598
 599   // Check that the register use lists are sane.
 600   MRI->verifyUseLists();
 601
 602   if (!MF->empty())
 603     verifyStackFrame();
 604 }
 605
 606 // Does iterator point to a and b as the first two elements?
 607 static bool matchPair(MachineBasicBlock::const_succ_iterator i,
 608                       const MachineBasicBlock *a, const MachineBasicBlock *b) {
 609   if (*i == a)
 610     return *++i == b;
 611   if (*i == b)
 612     return *++i == a;
 613   return false;
 614 }
 615
 616 void
 617 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
 618   FirstTerminator = nullptr;
 619   FirstNonPHI = nullptr;
 620
 621   if (!MF->getProperties().hasProperty(
 622       MachineFunctionProperties::Property::NoPHIs) && MRI->tracksLiveness()) {
 623     // If this block has allocatable physical registers live-in, check that
 624     // it is an entry block or landing pad.
 625     for (const auto &LI : MBB->liveins()) {
 626       if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() &&
 627           MBB->getIterator() != MBB->getParent()->begin()) {
 628         report("MBB has allocatable live-in, but isn't entry or landing-pad.", MBB);
 629         report_context(LI.PhysReg);
 630       }
 631     }
 632   }
 633
 634   // Count the number of landing pad successors.
 635   SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
 636   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
 637        E = MBB->succ_end(); I != E; ++I) {
 638     if ((*I)->isEHPad())
 639       LandingPadSuccs.insert(*I);
 640     if (!FunctionBlocks.count(*I))
 641       report("MBB has successor that isn't part of the function.", MBB);
 642     if (!MBBInfoMap[*I].Preds.count(MBB)) {
 643       report("Inconsistent CFG", MBB);
 644       errs() << "MBB is not in the predecessor list of the successor "
 645              << printMBBReference(*(*I)) << ".\n";
 646     }
 647   }
 648
 649   // Check the predecessor list.
 650   for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
 651        E = MBB->pred_end(); I != E; ++I) {
 652     if (!FunctionBlocks.count(*I))
 653       report("MBB has predecessor that isn't part of the function.", MBB);
 654     if (!MBBInfoMap[*I].Succs.count(MBB)) {
 655       report("Inconsistent CFG", MBB);
 656       errs() << "MBB is not in the successor list of the predecessor "
 657              << printMBBReference(*(*I)) << ".\n";
 658     }
 659   }
 660
 661   const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
 662   const BasicBlock *BB = MBB->getBasicBlock();
 663   const Function &F = MF->getFunction();
 664   if (LandingPadSuccs.size() > 1 &&
 665       !(AsmInfo &&
 666         AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
 667         BB && isa<SwitchInst>(BB->getTerminator())) &&
 668       !isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
 669     report("MBB has more than one landing pad successor", MBB);
 670
 671   // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
 672   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 673   SmallVector<MachineOperand, 4> Cond;
 674   if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB,
 675                           Cond)) {
 676     // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
 677     // check whether its answers match up with reality.
 678     if (!TBB && !FBB) {
 679       // Block falls through to its successor.
 680       MachineFunction::const_iterator MBBI = MBB->getIterator();
 681       ++MBBI;
 682       if (MBBI == MF->end()) {
 683         // It's possible that the block legitimately ends with a noreturn
 684         // call or an unreachable, in which case it won't actually fall
 685         // out the bottom of the function.
 686       } else if (MBB->succ_size() == LandingPadSuccs.size()) {
 687         // It's possible that the block legitimately ends with a noreturn
 688         // call or an unreachable, in which case it won't actually fall
 689         // out of the block.
 690       } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
 691         report("MBB exits via unconditional fall-through but doesn't have "
 692                "exactly one CFG successor!", MBB);
 693       } else if (!MBB->isSuccessor(&*MBBI)) {
 694         report("MBB exits via unconditional fall-through but its successor "
 695                "differs from its CFG successor!", MBB);
 696       }
 697       if (!MBB->empty() && MBB->back().isBarrier() &&
 698           !TII->isPredicated(MBB->back())) {
 699         report("MBB exits via unconditional fall-through but ends with a "
 700                "barrier instruction!", MBB);
 701       }
 702       if (!Cond.empty()) {
 703         report("MBB exits via unconditional fall-through but has a condition!",
 704                MBB);
 705       }
 706     } else if (TBB && !FBB && Cond.empty()) {
 707       // Block unconditionally branches somewhere.
 708       // If the block has exactly one successor, that happens to be a
 709       // landingpad, accept it as valid control flow.
 710       if (MBB->succ_size() != 1+LandingPadSuccs.size() &&
 711           (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 ||
 712            *MBB->succ_begin() != *LandingPadSuccs.begin())) {
 713         report("MBB exits via unconditional branch but doesn't have "
 714                "exactly one CFG successor!", MBB);
 715       } else if (!MBB->isSuccessor(TBB)) {
 716         report("MBB exits via unconditional branch but the CFG "
 717                "successor doesn't match the actual successor!", MBB);
 718       }
 719       if (MBB->empty()) {
 720         report("MBB exits via unconditional branch but doesn't contain "
 721                "any instructions!", MBB);
 722       } else if (!MBB->back().isBarrier()) {
 723         report("MBB exits via unconditional branch but doesn't end with a "
 724                "barrier instruction!", MBB);
 725       } else if (!MBB->back().isTerminator()) {
 726         report("MBB exits via unconditional branch but the branch isn't a "
 727                "terminator instruction!", MBB);
 728       }
 729     } else if (TBB && !FBB && !Cond.empty()) {
 730       // Block conditionally branches somewhere, otherwise falls through.
 731       MachineFunction::const_iterator MBBI = MBB->getIterator();
 732       ++MBBI;
 733       if (MBBI == MF->end()) {
 734         report("MBB conditionally falls through out of function!", MBB);
 735       } else if (MBB->succ_size() == 1) {
 736         // A conditional branch with only one successor is weird, but allowed.
 737         if (&*MBBI != TBB)
 738           report("MBB exits via conditional branch/fall-through but only has "
 739                  "one CFG successor!", MBB);
 740         else if (TBB != *MBB->succ_begin())
 741           report("MBB exits via conditional branch/fall-through but the CFG "
 742                  "successor don't match the actual successor!", MBB);
 743       } else if (MBB->succ_size() != 2) {
 744         report("MBB exits via conditional branch/fall-through but doesn't have "
 745                "exactly two CFG successors!", MBB);
 746       } else if (!matchPair(MBB->succ_begin(), TBB, &*MBBI)) {
 747         report("MBB exits via conditional branch/fall-through but the CFG "
 748                "successors don't match the actual successors!", MBB);
 749       }
 750       if (MBB->empty()) {
 751         report("MBB exits via conditional branch/fall-through but doesn't "
 752                "contain any instructions!", MBB);
 753       } else if (MBB->back().isBarrier()) {
 754         report("MBB exits via conditional branch/fall-through but ends with a "
 755                "barrier instruction!", MBB);
 756       } else if (!MBB->back().isTerminator()) {
 757         report("MBB exits via conditional branch/fall-through but the branch "
 758                "isn't a terminator instruction!", MBB);
 759       }
 760     } else if (TBB && FBB) {
 761       // Block conditionally branches somewhere, otherwise branches
 762       // somewhere else.
 763       if (MBB->succ_size() == 1) {
 764         // A conditional branch with only one successor is weird, but allowed.
 765         if (FBB != TBB)
 766           report("MBB exits via conditional branch/branch through but only has "
 767                  "one CFG successor!", MBB);
 768         else if (TBB != *MBB->succ_begin())
 769           report("MBB exits via conditional branch/branch through but the CFG "
 770                  "successor don't match the actual successor!", MBB);
 771       } else if (MBB->succ_size() != 2) {
 772         report("MBB exits via conditional branch/branch but doesn't have "
 773                "exactly two CFG successors!", MBB);
 774       } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
 775         report("MBB exits via conditional branch/branch but the CFG "
 776                "successors don't match the actual successors!", MBB);
 777       }
 778       if (MBB->empty()) {
 779         report("MBB exits via conditional branch/branch but doesn't "
 780                "contain any instructions!", MBB);
 781       } else if (!MBB->back().isBarrier()) {
 782         report("MBB exits via conditional branch/branch but doesn't end with a "
 783                "barrier instruction!", MBB);
 784       } else if (!MBB->back().isTerminator()) {
 785         report("MBB exits via conditional branch/branch but the branch "
 786                "isn't a terminator instruction!", MBB);
 787       }
 788       if (Cond.empty()) {
 789         report("MBB exits via conditional branch/branch but there's no "
 790                "condition!", MBB);
 791       }
 792     } else {
 793       report("AnalyzeBranch returned invalid data!", MBB);
 794     }
 795   }
 796
 797   regsLive.clear();
 798   if (MRI->tracksLiveness()) {
 799     for (const auto &LI : MBB->liveins()) {
 800       if (!TargetRegisterInfo::isPhysicalRegister(LI.PhysReg)) {
 801         report("MBB live-in list contains non-physical register", MBB);
 802         continue;
 803       }
 804       for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true);
 805            SubRegs.isValid(); ++SubRegs)
 806         regsLive.insert(*SubRegs);
 807     }
 808   }
 809
 810   const MachineFrameInfo &MFI = MF->getFrameInfo();
 811   BitVector PR = MFI.getPristineRegs(*MF);
 812   for (unsigned I : PR.set_bits()) {
 813     for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
 814          SubRegs.isValid(); ++SubRegs)
 815       regsLive.insert(*SubRegs);
 816   }
 817
 818   regsKilled.clear();
 819   regsDefined.clear();
 820
 821   if (Indexes)
 822     lastIndex = Indexes->getMBBStartIdx(MBB);
 823 }
 824
 825 // This function gets called for all bundle headers, including normal
 826 // stand-alone unbundled instructions.
 827 void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
 828   if (Indexes && Indexes->hasIndex(*MI)) {
 829     SlotIndex idx = Indexes->getInstructionIndex(*MI);
 830     if (!(idx > lastIndex)) {
 831       report("Instruction index out of order", MI);
 832       errs() << "Last instruction was at " << lastIndex << '\n';
 833     }
 834     lastIndex = idx;
 835   }
 836
 837   // Ensure non-terminators don't follow terminators.
 838   // Ignore predicated terminators formed by if conversion.
 839   // FIXME: If conversion shouldn't need to violate this rule.
 840   if (MI->isTerminator() && !TII->isPredicated(*MI)) {
 841     if (!FirstTerminator)
 842       FirstTerminator = MI;
 843   } else if (FirstTerminator && !MI->isDebugEntryValue()) {
 844     report("Non-terminator instruction after the first terminator", MI);
 845     errs() << "First terminator was:\t" << *FirstTerminator;
 846   }
 847 }
 848
 849 // The operands on an INLINEASM instruction must follow a template.
 850 // Verify that the flag operands make sense.
 851 void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
 852   // The first two operands on INLINEASM are the asm string and global flags.
 853   if (MI->getNumOperands() < 2) {
 854     report("Too few operands on inline asm", MI);
 855     return;
 856   }
 857   if (!MI->getOperand(0).isSymbol())
 858     report("Asm string must be an external symbol", MI);
 859   if (!MI->getOperand(1).isImm())
 860     report("Asm flags must be an immediate", MI);
 861   // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
 862   // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16,
 863   // and Extra_IsConvergent = 32.
 864   if (!isUInt<6>(MI->getOperand(1).getImm()))
 865     report("Unknown asm flags", &MI->getOperand(1), 1);
 866
 867   static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed");
 868
 869   unsigned OpNo = InlineAsm::MIOp_FirstOperand;
 870   unsigned NumOps;
 871   for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
 872     const MachineOperand &MO = MI->getOperand(OpNo);
 873     // There may be implicit ops after the fixed operands.
 874     if (!MO.isImm())
 875       break;
 876     NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
 877   }
 878
 879   if (OpNo > MI->getNumOperands())
 880     report("Missing operands in last group", MI);
 881
 882   // An optional MDNode follows the groups.
 883   if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
 884     ++OpNo;
 885
 886   // All trailing operands must be implicit registers.
 887   for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
 888     const MachineOperand &MO = MI->getOperand(OpNo);
 889     if (!MO.isReg() || !MO.isImplicit())
 890       report("Expected implicit register after groups", &MO, OpNo);
 891   }
 892 }
 893
 894 /// Check that types are consistent when two operands need to have the same
 895 /// number of vector elements.
 896 /// \return true if the types are valid.
 897 bool MachineVerifier::verifyVectorElementMatch(LLT Ty0, LLT Ty1,
 898                                                const MachineInstr *MI) {
 899   if (Ty0.isVector() != Ty1.isVector()) {
 900     report("operand types must be all-vector or all-scalar", MI);
 901     // Generally we try to report as many issues as possible at once, but in
 902     // this case it's not clear what should we be comparing the size of the
 903     // scalar with: the size of the whole vector or its lane. Instead of
 904     // making an arbitrary choice and emitting not so helpful message, let's
 905     // avoid the extra noise and stop here.
 906     return false;
 907   }
 908
 909   if (Ty0.isVector() && Ty0.getNumElements() != Ty1.getNumElements()) {
 910     report("operand types must preserve number of vector elements", MI);
 911     return false;
 912   }
 913
 914   return true;
 915 }
 916
 917 void MachineVerifier::verifyPreISelGenericInstruction(const MachineInstr *MI) {
 918   if (isFunctionSelected)
 919     report("Unexpected generic instruction in a Selected function", MI);
 920
 921   const MCInstrDesc &MCID = MI->getDesc();
 922   unsigned NumOps = MI->getNumOperands();
 923
 924   // Check types.
 925   SmallVector<LLT, 4> Types;
 926   for (unsigned I = 0, E = std::min(MCID.getNumOperands(), NumOps);
 927        I != E; ++I) {
 928     if (!MCID.OpInfo[I].isGenericType())
 929       continue;
 930     // Generic instructions specify type equality constraints between some of
 931     // their operands. Make sure these are consistent.
 932     size_t TypeIdx = MCID.OpInfo[I].getGenericTypeIndex();
 933     Types.resize(std::max(TypeIdx + 1, Types.size()));
 934
 935     const MachineOperand *MO = &MI->getOperand(I);
 936     if (!MO->isReg()) {
 937       report("generic instruction must use register operands", MI);
 938       continue;
 939     }
 940
 941     LLT OpTy = MRI->getType(MO->getReg());
 942     // Don't report a type mismatch if there is no actual mismatch, only a
 943     // type missing, to reduce noise:
 944     if (OpTy.isValid()) {
 945       // Only the first valid type for a type index will be printed: don't
 946       // overwrite it later so it's always clear which type was expected:
 947       if (!Types[TypeIdx].isValid())
 948         Types[TypeIdx] = OpTy;
 949       else if (Types[TypeIdx] != OpTy)
 950         report("Type mismatch in generic instruction", MO, I, OpTy);
 951     } else {
 952       // Generic instructions must have types attached to their operands.
 953       report("Generic instruction is missing a virtual register type", MO, I);
 954     }
 955   }
 956
 957   // Generic opcodes must not have physical register operands.
 958   for (unsigned I = 0; I < MI->getNumOperands(); ++I) {
 959     const MachineOperand *MO = &MI->getOperand(I);
 960     if (MO->isReg() && TargetRegisterInfo::isPhysicalRegister(MO->getReg()))
 961       report("Generic instruction cannot have physical register", MO, I);
 962   }
 963
 964   // Avoid out of bounds in checks below. This was already reported earlier.
 965   if (MI->getNumOperands() < MCID.getNumOperands())
 966     return;
 967
 968   StringRef ErrorInfo;
 969   if (!TII->verifyInstruction(*MI, ErrorInfo))
 970     report(ErrorInfo.data(), MI);
 971
 972   // Verify properties of various specific instruction types
 973   switch (MI->getOpcode()) {
 974   case TargetOpcode::G_CONSTANT:
 975   case TargetOpcode::G_FCONSTANT: {
 976     if (MI->getNumOperands() < MCID.getNumOperands())
 977       break;
 978
 979     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
 980     if (DstTy.isVector())
 981       report("Instruction cannot use a vector result type", MI);
 982
 983     if (MI->getOpcode() == TargetOpcode::G_CONSTANT) {
 984       if (!MI->getOperand(1).isCImm()) {
 985         report("G_CONSTANT operand must be cimm", MI);
 986         break;
 987       }
 988
 989       const ConstantInt *CI = MI->getOperand(1).getCImm();
 990       if (CI->getBitWidth() != DstTy.getSizeInBits())
 991         report("inconsistent constant size", MI);
 992     } else {
 993       if (!MI->getOperand(1).isFPImm()) {
 994         report("G_FCONSTANT operand must be fpimm", MI);
 995         break;
 996       }
 997       const ConstantFP *CF = MI->getOperand(1).getFPImm();
 998
 999       if (APFloat::getSizeInBits(CF->getValueAPF().getSemantics()) !=
1000           DstTy.getSizeInBits()) {
1001         report("inconsistent constant size", MI);
1002       }
1003     }
1004
1005     break;
1006   }
1007   case TargetOpcode::G_LOAD:
1008   case TargetOpcode::G_STORE:
1009   case TargetOpcode::G_ZEXTLOAD:
1010   case TargetOpcode::G_SEXTLOAD: {
1011     LLT ValTy = MRI->getType(MI->getOperand(0).getReg());
1012     LLT PtrTy = MRI->getType(MI->getOperand(1).getReg());
1013     if (!PtrTy.isPointer())
1014       report("Generic memory instruction must access a pointer", MI);
1015
1016     // Generic loads and stores must have a single MachineMemOperand
1017     // describing that access.
1018     if (!MI->hasOneMemOperand()) {
1019       report("Generic instruction accessing memory must have one mem operand",
1020              MI);
1021     } else {
1022       const MachineMemOperand &MMO = **MI->memoperands_begin();
1023       if (MI->getOpcode() == TargetOpcode::G_ZEXTLOAD ||
1024           MI->getOpcode() == TargetOpcode::G_SEXTLOAD) {
1025         if (MMO.getSizeInBits() >= ValTy.getSizeInBits())
1026           report("Generic extload must have a narrower memory type", MI);
1027       } else if (MI->getOpcode() == TargetOpcode::G_LOAD) {
1028         if (MMO.getSize() > ValTy.getSizeInBytes())
1029           report("load memory size cannot exceed result size", MI);
1030       } else if (MI->getOpcode() == TargetOpcode::G_STORE) {
1031         if (ValTy.getSizeInBytes() < MMO.getSize())
1032           report("store memory size cannot exceed value size", MI);
1033       }
1034     }
1035
1036     break;
1037   }
1038   case TargetOpcode::G_PHI: {
1039     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1040     if (!DstTy.isValid() ||
1041         !std::all_of(MI->operands_begin() + 1, MI->operands_end(),
1042                      [this, &DstTy](const MachineOperand &MO) {
1043                        if (!MO.isReg())
1044                          return true;
1045                        LLT Ty = MRI->getType(MO.getReg());
1046                        if (!Ty.isValid() || (Ty != DstTy))
1047                          return false;
1048                        return true;
1049                      }))
1050       report("Generic Instruction G_PHI has operands with incompatible/missing "
1051              "types",
1052              MI);
1053     break;
1054   }
1055   case TargetOpcode::G_BITCAST: {
1056     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1057     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1058     if (!DstTy.isValid() || !SrcTy.isValid())
1059       break;
1060
1061     if (SrcTy.isPointer() != DstTy.isPointer())
1062       report("bitcast cannot convert between pointers and other types", MI);
1063
1064     if (SrcTy.getSizeInBits() != DstTy.getSizeInBits())
1065       report("bitcast sizes must match", MI);
1066     break;
1067   }
1068   case TargetOpcode::G_INTTOPTR:
1069   case TargetOpcode::G_PTRTOINT:
1070   case TargetOpcode::G_ADDRSPACE_CAST: {
1071     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1072     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1073     if (!DstTy.isValid() || !SrcTy.isValid())
1074       break;
1075
1076     verifyVectorElementMatch(DstTy, SrcTy, MI);
1077
1078     DstTy = DstTy.getScalarType();
1079     SrcTy = SrcTy.getScalarType();
1080
1081     if (MI->getOpcode() == TargetOpcode::G_INTTOPTR) {
1082       if (!DstTy.isPointer())
1083         report("inttoptr result type must be a pointer", MI);
1084       if (SrcTy.isPointer())
1085         report("inttoptr source type must not be a pointer", MI);
1086     } else if (MI->getOpcode() == TargetOpcode::G_PTRTOINT) {
1087       if (!SrcTy.isPointer())
1088         report("ptrtoint source type must be a pointer", MI);
1089       if (DstTy.isPointer())
1090         report("ptrtoint result type must not be a pointer", MI);
1091     } else {
1092       assert(MI->getOpcode() == TargetOpcode::G_ADDRSPACE_CAST);
1093       if (!SrcTy.isPointer() || !DstTy.isPointer())
1094         report("addrspacecast types must be pointers", MI);
1095       else {
1096         if (SrcTy.getAddressSpace() == DstTy.getAddressSpace())
1097           report("addrspacecast must convert different address spaces", MI);
1098       }
1099     }
1100
1101     break;
1102   }
1103   case TargetOpcode::G_GEP: {
1104     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1105     LLT PtrTy = MRI->getType(MI->getOperand(1).getReg());
1106     LLT OffsetTy = MRI->getType(MI->getOperand(2).getReg());
1107     if (!DstTy.isValid() || !PtrTy.isValid() || !OffsetTy.isValid())
1108       break;
1109
1110     if (!PtrTy.getScalarType().isPointer())
1111       report("gep first operand must be a pointer", MI);
1112
1113     if (OffsetTy.getScalarType().isPointer())
1114       report("gep offset operand must not be a pointer", MI);
1115
1116     // TODO: Is the offset allowed to be a scalar with a vector?
1117     break;
1118   }
1119   case TargetOpcode::G_SEXT:
1120   case TargetOpcode::G_ZEXT:
1121   case TargetOpcode::G_ANYEXT:
1122   case TargetOpcode::G_TRUNC:
1123   case TargetOpcode::G_FPEXT:
1124   case TargetOpcode::G_FPTRUNC: {
1125     // Number of operands and presense of types is already checked (and
1126     // reported in case of any issues), so no need to report them again. As
1127     // we're trying to report as many issues as possible at once, however, the
1128     // instructions aren't guaranteed to have the right number of operands or
1129     // types attached to them at this point
1130     assert(MCID.getNumOperands() == 2 && "Expected 2 operands G_*{EXT,TRUNC}");
1131     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1132     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1133     if (!DstTy.isValid() || !SrcTy.isValid())
1134       break;
1135
1136     LLT DstElTy = DstTy.getScalarType();
1137     LLT SrcElTy = SrcTy.getScalarType();
1138     if (DstElTy.isPointer() || SrcElTy.isPointer())
1139       report("Generic extend/truncate can not operate on pointers", MI);
1140
1141     verifyVectorElementMatch(DstTy, SrcTy, MI);
1142
1143     unsigned DstSize = DstElTy.getSizeInBits();
1144     unsigned SrcSize = SrcElTy.getSizeInBits();
1145     switch (MI->getOpcode()) {
1146     default:
1147       if (DstSize <= SrcSize)
1148         report("Generic extend has destination type no larger than source", MI);
1149       break;
1150     case TargetOpcode::G_TRUNC:
1151     case TargetOpcode::G_FPTRUNC:
1152       if (DstSize >= SrcSize)
1153         report("Generic truncate has destination type no smaller than source",
1154                MI);
1155       break;
1156     }
1157     break;
1158   }
1159   case TargetOpcode::G_SELECT: {
1160     LLT SelTy = MRI->getType(MI->getOperand(0).getReg());
1161     LLT CondTy = MRI->getType(MI->getOperand(1).getReg());
1162     if (!SelTy.isValid() || !CondTy.isValid())
1163       break;
1164
1165     // Scalar condition select on a vector is valid.
1166     if (CondTy.isVector())
1167       verifyVectorElementMatch(SelTy, CondTy, MI);
1168     break;
1169   }
1170   case TargetOpcode::G_MERGE_VALUES: {
1171     // G_MERGE_VALUES should only be used to merge scalars into a larger scalar,
1172     // e.g. s2N = MERGE sN, sN
1173     // Merging multiple scalars into a vector is not allowed, should use
1174     // G_BUILD_VECTOR for that.
1175     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1176     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1177     if (DstTy.isVector() || SrcTy.isVector())
1178       report("G_MERGE_VALUES cannot operate on vectors", MI);
1179
1180     const unsigned NumOps = MI->getNumOperands();
1181     if (DstTy.getSizeInBits() != SrcTy.getSizeInBits() * (NumOps - 1))
1182       report("G_MERGE_VALUES result size is inconsistent", MI);
1183
1184     for (unsigned I = 2; I != NumOps; ++I) {
1185       if (MRI->getType(MI->getOperand(I).getReg()) != SrcTy)
1186         report("G_MERGE_VALUES source types do not match", MI);
1187     }
1188
1189     break;
1190   }
1191   case TargetOpcode::G_UNMERGE_VALUES: {
1192     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1193     LLT SrcTy = MRI->getType(MI->getOperand(MI->getNumOperands()-1).getReg());
1194     // For now G_UNMERGE can split vectors.
1195     for (unsigned i = 0; i < MI->getNumOperands()-1; ++i) {
1196       if (MRI->getType(MI->getOperand(i).getReg()) != DstTy)
1197         report("G_UNMERGE_VALUES destination types do not match", MI);
1198     }
1199     if (SrcTy.getSizeInBits() !=
1200         (DstTy.getSizeInBits() * (MI->getNumOperands() - 1))) {
1201       report("G_UNMERGE_VALUES source operand does not cover dest operands",
1202              MI);
1203     }
1204     break;
1205   }
1206   case TargetOpcode::G_BUILD_VECTOR: {
1207     // Source types must be scalars, dest type a vector. Total size of scalars
1208     // must match the dest vector size.
1209     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1210     LLT SrcEltTy = MRI->getType(MI->getOperand(1).getReg());
1211     if (!DstTy.isVector() || SrcEltTy.isVector()) {
1212       report("G_BUILD_VECTOR must produce a vector from scalar operands", MI);
1213       break;
1214     }
1215
1216     if (DstTy.getElementType() != SrcEltTy)
1217       report("G_BUILD_VECTOR result element type must match source type", MI);
1218
1219     if (DstTy.getNumElements() != MI->getNumOperands() - 1)
1220       report("G_BUILD_VECTOR must have an operand for each elemement", MI);
1221
1222     for (unsigned i = 2; i < MI->getNumOperands(); ++i) {
1223       if (MRI->getType(MI->getOperand(1).getReg()) !=
1224           MRI->getType(MI->getOperand(i).getReg()))
1225         report("G_BUILD_VECTOR source operand types are not homogeneous", MI);
1226     }
1227
1228     break;
1229   }
1230   case TargetOpcode::G_BUILD_VECTOR_TRUNC: {
1231     // Source types must be scalars, dest type a vector. Scalar types must be
1232     // larger than the dest vector elt type, as this is a truncating operation.
1233     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1234     LLT SrcEltTy = MRI->getType(MI->getOperand(1).getReg());
1235     if (!DstTy.isVector() || SrcEltTy.isVector())
1236       report("G_BUILD_VECTOR_TRUNC must produce a vector from scalar operands",
1237              MI);
1238     for (unsigned i = 2; i < MI->getNumOperands(); ++i) {
1239       if (MRI->getType(MI->getOperand(1).getReg()) !=
1240           MRI->getType(MI->getOperand(i).getReg()))
1241         report("G_BUILD_VECTOR_TRUNC source operand types are not homogeneous",
1242                MI);
1243     }
1244     if (SrcEltTy.getSizeInBits() <= DstTy.getElementType().getSizeInBits())
1245       report("G_BUILD_VECTOR_TRUNC source operand types are not larger than "
1246              "dest elt type",
1247              MI);
1248     break;
1249   }
1250   case TargetOpcode::G_CONCAT_VECTORS: {
1251     // Source types should be vectors, and total size should match the dest
1252     // vector size.
1253     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1254     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1255     if (!DstTy.isVector() || !SrcTy.isVector())
1256       report("G_CONCAT_VECTOR requires vector source and destination operands",
1257              MI);
1258     for (unsigned i = 2; i < MI->getNumOperands(); ++i) {
1259       if (MRI->getType(MI->getOperand(1).getReg()) !=
1260           MRI->getType(MI->getOperand(i).getReg()))
1261         report("G_CONCAT_VECTOR source operand types are not homogeneous", MI);
1262     }
1263     if (DstTy.getNumElements() !=
1264         SrcTy.getNumElements() * (MI->getNumOperands() - 1))
1265       report("G_CONCAT_VECTOR num dest and source elements should match", MI);
1266     break;
1267   }
1268   case TargetOpcode::G_ICMP:
1269   case TargetOpcode::G_FCMP: {
1270     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1271     LLT SrcTy = MRI->getType(MI->getOperand(2).getReg());
1272
1273     if ((DstTy.isVector() != SrcTy.isVector()) ||
1274         (DstTy.isVector() && DstTy.getNumElements() != SrcTy.getNumElements()))
1275       report("Generic vector icmp/fcmp must preserve number of lanes", MI);
1276
1277     break;
1278   }
1279   case TargetOpcode::G_EXTRACT: {
1280     const MachineOperand &SrcOp = MI->getOperand(1);
1281     if (!SrcOp.isReg()) {
1282       report("extract source must be a register", MI);
1283       break;
1284     }
1285
1286     const MachineOperand &OffsetOp = MI->getOperand(2);
1287     if (!OffsetOp.isImm()) {
1288       report("extract offset must be a constant", MI);
1289       break;
1290     }
1291
1292     unsigned DstSize = MRI->getType(MI->getOperand(0).getReg()).getSizeInBits();
1293     unsigned SrcSize = MRI->getType(SrcOp.getReg()).getSizeInBits();
1294     if (SrcSize == DstSize)
1295       report("extract source must be larger than result", MI);
1296
1297     if (DstSize + OffsetOp.getImm() > SrcSize)
1298       report("extract reads past end of register", MI);
1299     break;
1300   }
1301   case TargetOpcode::G_INSERT: {
1302     const MachineOperand &SrcOp = MI->getOperand(2);
1303     if (!SrcOp.isReg()) {
1304       report("insert source must be a register", MI);
1305       break;
1306     }
1307
1308     const MachineOperand &OffsetOp = MI->getOperand(3);
1309     if (!OffsetOp.isImm()) {
1310       report("insert offset must be a constant", MI);
1311       break;
1312     }
1313
1314     unsigned DstSize = MRI->getType(MI->getOperand(0).getReg()).getSizeInBits();
1315     unsigned SrcSize = MRI->getType(SrcOp.getReg()).getSizeInBits();
1316
1317     if (DstSize <= SrcSize)
1318       report("inserted size must be smaller than total register", MI);
1319
1320     if (SrcSize + OffsetOp.getImm() > DstSize)
1321       report("insert writes past end of register", MI);
1322
1323     break;
1324   }
1325   case TargetOpcode::G_JUMP_TABLE: {
1326     if (!MI->getOperand(1).isJTI())
1327       report("G_JUMP_TABLE source operand must be a jump table index", MI);
1328     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1329     if (!DstTy.isPointer())
1330       report("G_JUMP_TABLE dest operand must have a pointer type", MI);
1331     break;
1332   }
1333   case TargetOpcode::G_BRJT: {
1334     if (!MRI->getType(MI->getOperand(0).getReg()).isPointer())
1335       report("G_BRJT src operand 0 must be a pointer type", MI);
1336
1337     if (!MI->getOperand(1).isJTI())
1338       report("G_BRJT src operand 1 must be a jump table index", MI);
1339
1340     const auto &IdxOp = MI->getOperand(2);
1341     if (!IdxOp.isReg() || MRI->getType(IdxOp.getReg()).isPointer())
1342       report("G_BRJT src operand 2 must be a scalar reg type", MI);
1343     break;
1344   }
1345   case TargetOpcode::G_INTRINSIC:
1346   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS: {
1347     // TODO: Should verify number of def and use operands, but the current
1348     // interface requires passing in IR types for mangling.
1349     const MachineOperand &IntrIDOp = MI->getOperand(MI->getNumExplicitDefs());
1350     if (!IntrIDOp.isIntrinsicID()) {
1351       report("G_INTRINSIC first src operand must be an intrinsic ID", MI);
1352       break;
1353     }
1354
1355     bool NoSideEffects = MI->getOpcode() == TargetOpcode::G_INTRINSIC;
1356     unsigned IntrID = IntrIDOp.getIntrinsicID();
1357     if (IntrID != 0 && IntrID < Intrinsic::num_intrinsics) {
1358       AttributeList Attrs
1359         = Intrinsic::getAttributes(MF->getFunction().getContext(),
1360                                    static_cast<Intrinsic::ID>(IntrID));
1361       bool DeclHasSideEffects = !Attrs.hasFnAttribute(Attribute::ReadNone);
1362       if (NoSideEffects && DeclHasSideEffects) {
1363         report("G_INTRINSIC used with intrinsic that accesses memory", MI);
1364         break;
1365       }
1366       if (!NoSideEffects && !DeclHasSideEffects) {
1367         report("G_INTRINSIC_W_SIDE_EFFECTS used with readnone intrinsic", MI);
1368         break;
1369       }
1370     }
1371
1372     break;
1373   }
1374   default:
1375     break;
1376   }
1377 }
1378
1379 void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
1380   const MCInstrDesc &MCID = MI->getDesc();
1381   if (MI->getNumOperands() < MCID.getNumOperands()) {
1382     report("Too few operands", MI);
1383     errs() << MCID.getNumOperands() << " operands expected, but "
1384            << MI->getNumOperands() << " given.\n";
1385   }
1386
1387   if (MI->isPHI()) {
1388     if (MF->getProperties().hasProperty(
1389             MachineFunctionProperties::Property::NoPHIs))
1390       report("Found PHI instruction with NoPHIs property set", MI);
1391
1392     if (FirstNonPHI)
1393       report("Found PHI instruction after non-PHI", MI);
1394   } else if (FirstNonPHI == nullptr)
1395     FirstNonPHI = MI;
1396
1397   // Check the tied operands.
1398   if (MI->isInlineAsm())
1399     verifyInlineAsm(MI);
1400
1401   // Check the MachineMemOperands for basic consistency.
1402   for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
1403                                   E = MI->memoperands_end();
1404        I != E; ++I) {
1405     if ((*I)->isLoad() && !MI->mayLoad())
1406       report("Missing mayLoad flag", MI);
1407     if ((*I)->isStore() && !MI->mayStore())
1408       report("Missing mayStore flag", MI);
1409   }
1410
1411   // Debug values must not have a slot index.
1412   // Other instructions must have one, unless they are inside a bundle.
1413   if (LiveInts) {
1414     bool mapped = !LiveInts->isNotInMIMap(*MI);
1415     if (MI->isDebugInstr()) {
1416       if (mapped)
1417         report("Debug instruction has a slot index", MI);
1418     } else if (MI->isInsideBundle()) {
1419       if (mapped)
1420         report("Instruction inside bundle has a slot index", MI);
1421     } else {
1422       if (!mapped)
1423         report("Missing slot index", MI);
1424     }
1425   }
1426
1427   if (isPreISelGenericOpcode(MCID.getOpcode())) {
1428     verifyPreISelGenericInstruction(MI);
1429     return;
1430   }
1431
1432   StringRef ErrorInfo;
1433   if (!TII->verifyInstruction(*MI, ErrorInfo))
1434     report(ErrorInfo.data(), MI);
1435
1436   // Verify properties of various specific instruction types
1437   switch (MI->getOpcode()) {
1438   case TargetOpcode::COPY: {
1439     if (foundErrors)
1440       break;
1441     const MachineOperand &DstOp = MI->getOperand(0);
1442     const MachineOperand &SrcOp = MI->getOperand(1);
1443     LLT DstTy = MRI->getType(DstOp.getReg());
1444     LLT SrcTy = MRI->getType(SrcOp.getReg());
1445     if (SrcTy.isValid() && DstTy.isValid()) {
1446       // If both types are valid, check that the types are the same.
1447       if (SrcTy != DstTy) {
1448         report("Copy Instruction is illegal with mismatching types", MI);
1449         errs() << "Def = " << DstTy << ", Src = " << SrcTy << "\n";
1450       }
1451     }
1452     if (SrcTy.isValid() || DstTy.isValid()) {
1453       // If one of them have valid types, let's just check they have the same
1454       // size.
1455       unsigned SrcSize = TRI->getRegSizeInBits(SrcOp.getReg(), *MRI);
1456       unsigned DstSize = TRI->getRegSizeInBits(DstOp.getReg(), *MRI);
1457       assert(SrcSize && "Expecting size here");
1458       assert(DstSize && "Expecting size here");
1459       if (SrcSize != DstSize)
1460         if (!DstOp.getSubReg() && !SrcOp.getSubReg()) {
1461           report("Copy Instruction is illegal with mismatching sizes", MI);
1462           errs() << "Def Size = " << DstSize << ", Src Size = " << SrcSize
1463                  << "\n";
1464         }
1465     }
1466     break;
1467   }
1468   case TargetOpcode::STATEPOINT:
1469     if (!MI->getOperand(StatepointOpers::IDPos).isImm() ||
1470         !MI->getOperand(StatepointOpers::NBytesPos).isImm() ||
1471         !MI->getOperand(StatepointOpers::NCallArgsPos).isImm())
1472       report("meta operands to STATEPOINT not constant!", MI);
1473     break;
1474
1475     auto VerifyStackMapConstant = [&](unsigned Offset) {
1476       if (!MI->getOperand(Offset).isImm() ||
1477           MI->getOperand(Offset).getImm() != StackMaps::ConstantOp ||
1478           !MI->getOperand(Offset + 1).isImm())
1479         report("stack map constant to STATEPOINT not well formed!", MI);
1480     };
1481     const unsigned VarStart = StatepointOpers(MI).getVarIdx();
1482     VerifyStackMapConstant(VarStart + StatepointOpers::CCOffset);
1483     VerifyStackMapConstant(VarStart + StatepointOpers::FlagsOffset);
1484     VerifyStackMapConstant(VarStart + StatepointOpers::NumDeoptOperandsOffset);
1485
1486     // TODO: verify we have properly encoded deopt arguments
1487     break;
1488   }
1489 }
1490
1491 void
1492 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
1493   const MachineInstr *MI = MO->getParent();
1494   const MCInstrDesc &MCID = MI->getDesc();
1495   unsigned NumDefs = MCID.getNumDefs();
1496   if (MCID.getOpcode() == TargetOpcode::PATCHPOINT)
1497     NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0;
1498
1499   // The first MCID.NumDefs operands must be explicit register defines
1500   if (MONum < NumDefs) {
1501     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1502     if (!MO->isReg())
1503       report("Explicit definition must be a register", MO, MONum);
1504     else if (!MO->isDef() && !MCOI.isOptionalDef())
1505       report("Explicit definition marked as use", MO, MONum);
1506     else if (MO->isImplicit())
1507       report("Explicit definition marked as implicit", MO, MONum);
1508   } else if (MONum < MCID.getNumOperands()) {
1509     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1510     // Don't check if it's the last operand in a variadic instruction. See,
1511     // e.g., LDM_RET in the arm back end.
1512     if (MO->isReg() &&
1513         !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
1514       if (MO->isDef() && !MCOI.isOptionalDef())
1515         report("Explicit operand marked as def", MO, MONum);
1516       if (MO->isImplicit())
1517         report("Explicit operand marked as implicit", MO, MONum);
1518     }
1519
1520     int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
1521     if (TiedTo != -1) {
1522       if (!MO->isReg())
1523         report("Tied use must be a register", MO, MONum);
1524       else if (!MO->isTied())
1525         report("Operand should be tied", MO, MONum);
1526       else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
1527         report("Tied def doesn't match MCInstrDesc", MO, MONum);
1528       else if (TargetRegisterInfo::isPhysicalRegister(MO->getReg())) {
1529         const MachineOperand &MOTied = MI->getOperand(TiedTo);
1530         if (!MOTied.isReg())
1531           report("Tied counterpart must be a register", &MOTied, TiedTo);
1532         else if (TargetRegisterInfo::isPhysicalRegister(MOTied.getReg()) &&
1533                  MO->getReg() != MOTied.getReg())
1534           report("Tied physical registers must match.", &MOTied, TiedTo);
1535       }
1536     } else if (MO->isReg() && MO->isTied())
1537       report("Explicit operand should not be tied", MO, MONum);
1538   } else {
1539     // ARM adds %reg0 operands to indicate predicates. We'll allow that.
1540     if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
1541       report("Extra explicit operand on non-variadic instruction", MO, MONum);
1542   }
1543
1544   switch (MO->getType()) {
1545   case MachineOperand::MO_Register: {
1546     const unsigned Reg = MO->getReg();
1547     if (!Reg)
1548       return;
1549     if (MRI->tracksLiveness() && !MI->isDebugValue())
1550       checkLiveness(MO, MONum);
1551
1552     // Verify the consistency of tied operands.
1553     if (MO->isTied()) {
1554       unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
1555       const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
1556       if (!OtherMO.isReg())
1557         report("Must be tied to a register", MO, MONum);
1558       if (!OtherMO.isTied())
1559         report("Missing tie flags on tied operand", MO, MONum);
1560       if (MI->findTiedOperandIdx(OtherIdx) != MONum)
1561         report("Inconsistent tie links", MO, MONum);
1562       if (MONum < MCID.getNumDefs()) {
1563         if (OtherIdx < MCID.getNumOperands()) {
1564           if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
1565             report("Explicit def tied to explicit use without tie constraint",
1566                    MO, MONum);
1567         } else {
1568           if (!OtherMO.isImplicit())
1569             report("Explicit def should be tied to implicit use", MO, MONum);
1570         }
1571       }
1572     }
1573
1574     // Verify two-address constraints after leaving SSA form.
1575     unsigned DefIdx;
1576     if (!MRI->isSSA() && MO->isUse() &&
1577         MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
1578         Reg != MI->getOperand(DefIdx).getReg())
1579       report("Two-address instruction operands must be identical", MO, MONum);
1580
1581     // Check register classes.
1582     unsigned SubIdx = MO->getSubReg();
1583
1584     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1585       if (SubIdx) {
1586         report("Illegal subregister index for physical register", MO, MONum);
1587         return;
1588       }
1589       if (MONum < MCID.getNumOperands()) {
1590         if (const TargetRegisterClass *DRC =
1591               TII->getRegClass(MCID, MONum, TRI, *MF)) {
1592           if (!DRC->contains(Reg)) {
1593             report("Illegal physical register for instruction", MO, MONum);
1594             errs() << printReg(Reg, TRI) << " is not a "
1595                    << TRI->getRegClassName(DRC) << " register.\n";
1596           }
1597         }
1598       }
1599       if (MO->isRenamable()) {
1600         if (MRI->isReserved(Reg)) {
1601           report("isRenamable set on reserved register", MO, MONum);
1602           return;
1603         }
1604       }
1605       if (MI->isDebugValue() && MO->isUse() && !MO->isDebug()) {
1606         report("Use-reg is not IsDebug in a DBG_VALUE", MO, MONum);
1607         return;
1608       }
1609     } else {
1610       // Virtual register.
1611       const TargetRegisterClass *RC = MRI->getRegClassOrNull(Reg);
1612       if (!RC) {
1613         // This is a generic virtual register.
1614
1615         // If we're post-Select, we can't have gvregs anymore.
1616         if (isFunctionSelected) {
1617           report("Generic virtual register invalid in a Selected function",
1618                  MO, MONum);
1619           return;
1620         }
1621
1622         // The gvreg must have a type and it must not have a SubIdx.
1623         LLT Ty = MRI->getType(Reg);
1624         if (!Ty.isValid()) {
1625           report("Generic virtual register must have a valid type", MO,
1626                  MONum);
1627           return;
1628         }
1629
1630         const RegisterBank *RegBank = MRI->getRegBankOrNull(Reg);
1631
1632         // If we're post-RegBankSelect, the gvreg must have a bank.
1633         if (!RegBank && isFunctionRegBankSelected) {
1634           report("Generic virtual register must have a bank in a "
1635                  "RegBankSelected function",
1636                  MO, MONum);
1637           return;
1638         }
1639
1640         // Make sure the register fits into its register bank if any.
1641         if (RegBank && Ty.isValid() &&
1642             RegBank->getSize() < Ty.getSizeInBits()) {
1643           report("Register bank is too small for virtual register", MO,
1644                  MONum);
1645           errs() << "Register bank " << RegBank->getName() << " too small("
1646                  << RegBank->getSize() << ") to fit " << Ty.getSizeInBits()
1647                  << "-bits\n";
1648           return;
1649         }
1650         if (SubIdx)  {
1651           report("Generic virtual register does not allow subregister index", MO,
1652                  MONum);
1653           return;
1654         }
1655
1656         // If this is a target specific instruction and this operand
1657         // has register class constraint, the virtual register must
1658         // comply to it.
1659         if (!isPreISelGenericOpcode(MCID.getOpcode()) &&
1660             MONum < MCID.getNumOperands() &&
1661             TII->getRegClass(MCID, MONum, TRI, *MF)) {
1662           report("Virtual register does not match instruction constraint", MO,
1663                  MONum);
1664           errs() << "Expect register class "
1665                  << TRI->getRegClassName(
1666                         TII->getRegClass(MCID, MONum, TRI, *MF))
1667                  << " but got nothing\n";
1668           return;
1669         }
1670
1671         break;
1672       }
1673       if (SubIdx) {
1674         const TargetRegisterClass *SRC =
1675           TRI->getSubClassWithSubReg(RC, SubIdx);
1676         if (!SRC) {
1677           report("Invalid subregister index for virtual register", MO, MONum);
1678           errs() << "Register class " << TRI->getRegClassName(RC)
1679               << " does not support subreg index " << SubIdx << "\n";
1680           return;
1681         }
1682         if (RC != SRC) {
1683           report("Invalid register class for subregister index", MO, MONum);
1684           errs() << "Register class " << TRI->getRegClassName(RC)
1685               << " does not fully support subreg index " << SubIdx << "\n";
1686           return;
1687         }
1688       }
1689       if (MONum < MCID.getNumOperands()) {
1690         if (const TargetRegisterClass *DRC =
1691               TII->getRegClass(MCID, MONum, TRI, *MF)) {
1692           if (SubIdx) {
1693             const TargetRegisterClass *SuperRC =
1694                 TRI->getLargestLegalSuperClass(RC, *MF);
1695             if (!SuperRC) {
1696               report("No largest legal super class exists.", MO, MONum);
1697               return;
1698             }
1699             DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
1700             if (!DRC) {
1701               report("No matching super-reg register class.", MO, MONum);
1702               return;
1703             }
1704           }
1705           if (!RC->hasSuperClassEq(DRC)) {
1706             report("Illegal virtual register for instruction", MO, MONum);
1707             errs() << "Expected a " << TRI->getRegClassName(DRC)
1708                 << " register, but got a " << TRI->getRegClassName(RC)
1709                 << " register\n";
1710           }
1711         }
1712       }
1713     }
1714     break;
1715   }
1716
1717   case MachineOperand::MO_RegisterMask:
1718     regMasks.push_back(MO->getRegMask());
1719     break;
1720
1721   case MachineOperand::MO_MachineBasicBlock:
1722     if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
1723       report("PHI operand is not in the CFG", MO, MONum);
1724     break;
1725
1726   case MachineOperand::MO_FrameIndex:
1727     if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
1728         LiveInts && !LiveInts->isNotInMIMap(*MI)) {
1729       int FI = MO->getIndex();
1730       LiveInterval &LI = LiveStks->getInterval(FI);
1731       SlotIndex Idx = LiveInts->getInstructionIndex(*MI);
1732
1733       bool stores = MI->mayStore();
1734       bool loads = MI->mayLoad();
1735       // For a memory-to-memory move, we need to check if the frame
1736       // index is used for storing or loading, by inspecting the
1737       // memory operands.
1738       if (stores && loads) {
1739         for (auto *MMO : MI->memoperands()) {
1740           const PseudoSourceValue *PSV = MMO->getPseudoValue();
1741           if (PSV == nullptr) continue;
1742           const FixedStackPseudoSourceValue *Value =
1743             dyn_cast<FixedStackPseudoSourceValue>(PSV);
1744           if (Value == nullptr) continue;
1745           if (Value->getFrameIndex() != FI) continue;
1746
1747           if (MMO->isStore())
1748             loads = false;
1749           else
1750             stores = false;
1751           break;
1752         }
1753         if (loads == stores)
1754           report("Missing fixed stack memoperand.", MI);
1755       }
1756       if (loads && !LI.liveAt(Idx.getRegSlot(true))) {
1757         report("Instruction loads from dead spill slot", MO, MONum);
1758         errs() << "Live stack: " << LI << '\n';
1759       }
1760       if (stores && !LI.liveAt(Idx.getRegSlot())) {
1761         report("Instruction stores to dead spill slot", MO, MONum);
1762         errs() << "Live stack: " << LI << '\n';
1763       }
1764     }
1765     break;
1766
1767   default:
1768     break;
1769   }
1770 }
1771
1772 void MachineVerifier::checkLivenessAtUse(const MachineOperand *MO,
1773     unsigned MONum, SlotIndex UseIdx, const LiveRange &LR, unsigned VRegOrUnit,
1774     LaneBitmask LaneMask) {
1775   LiveQueryResult LRQ = LR.Query(UseIdx);
1776   // Check if we have a segment at the use, note however that we only need one
1777   // live subregister range, the others may be dead.
1778   if (!LRQ.valueIn() && LaneMask.none()) {
1779     report("No live segment at use", MO, MONum);
1780     report_context_liverange(LR);
1781     report_context_vreg_regunit(VRegOrUnit);
1782     report_context(UseIdx);
1783   }
1784   if (MO->isKill() && !LRQ.isKill()) {
1785     report("Live range continues after kill flag", MO, MONum);
1786     report_context_liverange(LR);
1787     report_context_vreg_regunit(VRegOrUnit);
1788     if (LaneMask.any())
1789       report_context_lanemask(LaneMask);
1790     report_context(UseIdx);
1791   }
1792 }
1793
1794 void MachineVerifier::checkLivenessAtDef(const MachineOperand *MO,
1795     unsigned MONum, SlotIndex DefIdx, const LiveRange &LR, unsigned VRegOrUnit,
1796     bool SubRangeCheck, LaneBitmask LaneMask) {
1797   if (const VNInfo *VNI = LR.getVNInfoAt(DefIdx)) {
1798     assert(VNI && "NULL valno is not allowed");
1799     if (VNI->def != DefIdx) {
1800       report("Inconsistent valno->def", MO, MONum);
1801       report_context_liverange(LR);
1802       report_context_vreg_regunit(VRegOrUnit);
1803       if (LaneMask.any())
1804         report_context_lanemask(LaneMask);
1805       report_context(*VNI);
1806       report_context(DefIdx);
1807     }
1808   } else {
1809     report("No live segment at def", MO, MONum);
1810     report_context_liverange(LR);
1811     report_context_vreg_regunit(VRegOrUnit);
1812     if (LaneMask.any())
1813       report_context_lanemask(LaneMask);
1814     report_context(DefIdx);
1815   }
1816   // Check that, if the dead def flag is present, LiveInts agree.
1817   if (MO->isDead()) {
1818     LiveQueryResult LRQ = LR.Query(DefIdx);
1819     if (!LRQ.isDeadDef()) {
1820       assert(TargetRegisterInfo::isVirtualRegister(VRegOrUnit) &&
1821              "Expecting a virtual register.");
1822       // A dead subreg def only tells us that the specific subreg is dead. There
1823       // could be other non-dead defs of other subregs, or we could have other
1824       // parts of the register being live through the instruction. So unless we
1825       // are checking liveness for a subrange it is ok for the live range to
1826       // continue, given that we have a dead def of a subregister.
1827       if (SubRangeCheck || MO->getSubReg() == 0) {
1828         report("Live range continues after dead def flag", MO, MONum);
1829         report_context_liverange(LR);
1830         report_context_vreg_regunit(VRegOrUnit);
1831         if (LaneMask.any())
1832           report_context_lanemask(LaneMask);
1833       }
1834     }
1835   }
1836 }
1837
1838 void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
1839   const MachineInstr *MI = MO->getParent();
1840   const unsigned Reg = MO->getReg();
1841
1842   // Both use and def operands can read a register.
1843   if (MO->readsReg()) {
1844     if (MO->isKill())
1845       addRegWithSubRegs(regsKilled, Reg);
1846
1847     // Check that LiveVars knows this kill.
1848     if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
1849         MO->isKill()) {
1850       LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1851       if (!is_contained(VI.Kills, MI))
1852         report("Kill missing from LiveVariables", MO, MONum);
1853     }
1854
1855     // Check LiveInts liveness and kill.
1856     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
1857       SlotIndex UseIdx = LiveInts->getInstructionIndex(*MI);
1858       // Check the cached regunit intervals.
1859       if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
1860         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
1861           if (MRI->isReservedRegUnit(*Units))
1862             continue;
1863           if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units))
1864             checkLivenessAtUse(MO, MONum, UseIdx, *LR, *Units);
1865         }
1866       }
1867
1868       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1869         if (LiveInts->hasInterval(Reg)) {
1870           // This is a virtual register interval.
1871           const LiveInterval &LI = LiveInts->getInterval(Reg);
1872           checkLivenessAtUse(MO, MONum, UseIdx, LI, Reg);
1873
1874           if (LI.hasSubRanges() && !MO->isDef()) {
1875             unsigned SubRegIdx = MO->getSubReg();
1876             LaneBitmask MOMask = SubRegIdx != 0
1877                                ? TRI->getSubRegIndexLaneMask(SubRegIdx)
1878                                : MRI->getMaxLaneMaskForVReg(Reg);
1879             LaneBitmask LiveInMask;
1880             for (const LiveInterval::SubRange &SR : LI.subranges()) {
1881               if ((MOMask & SR.LaneMask).none())
1882                 continue;
1883               checkLivenessAtUse(MO, MONum, UseIdx, SR, Reg, SR.LaneMask);
1884               LiveQueryResult LRQ = SR.Query(UseIdx);
1885               if (LRQ.valueIn())
1886                 LiveInMask |= SR.LaneMask;
1887             }
1888             // At least parts of the register has to be live at the use.
1889             if ((LiveInMask & MOMask).none()) {
1890               report("No live subrange at use", MO, MONum);
1891               report_context(LI);
1892               report_context(UseIdx);
1893             }
1894           }
1895         } else {
1896           report("Virtual register has no live interval", MO, MONum);
1897         }
1898       }
1899     }
1900
1901     // Use of a dead register.
1902     if (!regsLive.count(Reg)) {
1903       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1904         // Reserved registers may be used even when 'dead'.
1905         bool Bad = !isReserved(Reg);
1906         // We are fine if just any subregister has a defined value.
1907         if (Bad) {
1908           for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid();
1909                ++SubRegs) {
1910             if (regsLive.count(*SubRegs)) {
1911               Bad = false;
1912               break;
1913             }
1914           }
1915         }
1916         // If there is an additional implicit-use of a super register we stop
1917         // here. By definition we are fine if the super register is not
1918         // (completely) dead, if the complete super register is dead we will
1919         // get a report for its operand.
1920         if (Bad) {
1921           for (const MachineOperand &MOP : MI->uses()) {
1922             if (!MOP.isReg() || !MOP.isImplicit())
1923               continue;
1924
1925             if (!TargetRegisterInfo::isPhysicalRegister(MOP.getReg()))
1926               continue;
1927
1928             for (MCSubRegIterator SubRegs(MOP.getReg(), TRI); SubRegs.isValid();
1929                  ++SubRegs) {
1930               if (*SubRegs == Reg) {
1931                 Bad = false;
1932                 break;
1933               }
1934             }
1935           }
1936         }
1937         if (Bad)
1938           report("Using an undefined physical register", MO, MONum);
1939       } else if (MRI->def_empty(Reg)) {
1940         report("Reading virtual register without a def", MO, MONum);
1941       } else {
1942         BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1943         // We don't know which virtual registers are live in, so only complain
1944         // if vreg was killed in this MBB. Otherwise keep track of vregs that
1945         // must be live in. PHI instructions are handled separately.
1946         if (MInfo.regsKilled.count(Reg))
1947           report("Using a killed virtual register", MO, MONum);
1948         else if (!MI->isPHI())
1949           MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
1950       }
1951     }
1952   }
1953
1954   if (MO->isDef()) {
1955     // Register defined.
1956     // TODO: verify that earlyclobber ops are not used.
1957     if (MO->isDead())
1958       addRegWithSubRegs(regsDead, Reg);
1959     else
1960       addRegWithSubRegs(regsDefined, Reg);
1961
1962     // Verify SSA form.
1963     if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
1964         std::next(MRI->def_begin(Reg)) != MRI->def_end())
1965       report("Multiple virtual register defs in SSA form", MO, MONum);
1966
1967     // Check LiveInts for a live segment, but only for virtual registers.
1968     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
1969       SlotIndex DefIdx = LiveInts->getInstructionIndex(*MI);
1970       DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
1971
1972       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1973         if (LiveInts->hasInterval(Reg)) {
1974           const LiveInterval &LI = LiveInts->getInterval(Reg);
1975           checkLivenessAtDef(MO, MONum, DefIdx, LI, Reg);
1976
1977           if (LI.hasSubRanges()) {
1978             unsigned SubRegIdx = MO->getSubReg();
1979             LaneBitmask MOMask = SubRegIdx != 0
1980               ? TRI->getSubRegIndexLaneMask(SubRegIdx)
1981               : MRI->getMaxLaneMaskForVReg(Reg);
1982             for (const LiveInterval::SubRange &SR : LI.subranges()) {
1983               if ((SR.LaneMask & MOMask).none())
1984                 continue;
1985               checkLivenessAtDef(MO, MONum, DefIdx, SR, Reg, true, SR.LaneMask);
1986             }
1987           }
1988         } else {
1989           report("Virtual register has no Live interval", MO, MONum);
1990         }
1991       }
1992     }
1993   }
1994 }
1995
1996 void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {}
1997
1998 // This function gets called after visiting all instructions in a bundle. The
1999 // argument points to the bundle header.
2000 // Normal stand-alone instructions are also considered 'bundles', and this
2001 // function is called for all of them.
2002 void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
2003   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
2004   set_union(MInfo.regsKilled, regsKilled);
2005   set_subtract(regsLive, regsKilled); regsKilled.clear();
2006   // Kill any masked registers.
2007   while (!regMasks.empty()) {
2008     const uint32_t *Mask = regMasks.pop_back_val();
2009     for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
2010       if (TargetRegisterInfo::isPhysicalRegister(*I) &&
2011           MachineOperand::clobbersPhysReg(Mask, *I))
2012         regsDead.push_back(*I);
2013   }
2014   set_subtract(regsLive, regsDead);   regsDead.clear();
2015   set_union(regsLive, regsDefined);   regsDefined.clear();
2016 }
2017
2018 void
2019 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
2020   MBBInfoMap[MBB].regsLiveOut = regsLive;
2021   regsLive.clear();
2022
2023   if (Indexes) {
2024     SlotIndex stop = Indexes->getMBBEndIdx(MBB);
2025     if (!(stop > lastIndex)) {
2026       report("Block ends before last instruction index", MBB);
2027       errs() << "Block ends at " << stop
2028           << " last instruction was at " << lastIndex << '\n';
2029     }
2030     lastIndex = stop;
2031   }
2032 }
2033
2034 // Calculate the largest possible vregsPassed sets. These are the registers that
2035 // can pass through an MBB live, but may not be live every time. It is assumed
2036 // that all vregsPassed sets are empty before the call.
2037 void MachineVerifier::calcRegsPassed() {
2038   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
2039   // have any vregsPassed.
2040   SmallPtrSet<const MachineBasicBlock*, 8> todo;
2041   for (const auto &MBB : *MF) {
2042     BBInfo &MInfo = MBBInfoMap[&MBB];
2043     if (!MInfo.reachable)
2044       continue;
2045     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
2046            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
2047       BBInfo &SInfo = MBBInfoMap[*SuI];
2048       if (SInfo.addPassed(MInfo.regsLiveOut))
2049         todo.insert(*SuI);
2050     }
2051   }
2052
2053   // Iteratively push vregsPassed to successors. This will converge to the same
2054   // final state regardless of DenseSet iteration order.
2055   while (!todo.empty()) {
2056     const MachineBasicBlock *MBB = *todo.begin();
2057     todo.erase(MBB);
2058     BBInfo &MInfo = MBBInfoMap[MBB];
2059     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
2060            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
2061       if (*SuI == MBB)
2062         continue;
2063       BBInfo &SInfo = MBBInfoMap[*SuI];
2064       if (SInfo.addPassed(MInfo.vregsPassed))
2065         todo.insert(*SuI);
2066     }
2067   }
2068 }
2069
2070 // Calculate the set of virtual registers that must be passed through each basic
2071 // block in order to satisfy the requirements of successor blocks. This is very
2072 // similar to calcRegsPassed, only backwards.
2073 void MachineVerifier::calcRegsRequired() {
2074   // First push live-in regs to predecessors' vregsRequired.
2075   SmallPtrSet<const MachineBasicBlock*, 8> todo;
2076   for (const auto &MBB : *MF) {
2077     BBInfo &MInfo = MBBInfoMap[&MBB];
2078     for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
2079            PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
2080       BBInfo &PInfo = MBBInfoMap[*PrI];
2081       if (PInfo.addRequired(MInfo.vregsLiveIn))
2082         todo.insert(*PrI);
2083     }
2084   }
2085
2086   // Iteratively push vregsRequired to predecessors. This will converge to the
2087   // same final state regardless of DenseSet iteration order.
2088   while (!todo.empty()) {
2089     const MachineBasicBlock *MBB = *todo.begin();
2090     todo.erase(MBB);
2091     BBInfo &MInfo = MBBInfoMap[MBB];
2092     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
2093            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
2094       if (*PrI == MBB)
2095         continue;
2096       BBInfo &SInfo = MBBInfoMap[*PrI];
2097       if (SInfo.addRequired(MInfo.vregsRequired))
2098         todo.insert(*PrI);
2099     }
2100   }
2101 }
2102
2103 // Check PHI instructions at the beginning of MBB. It is assumed that
2104 // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
2105 void MachineVerifier::checkPHIOps(const MachineBasicBlock &MBB) {
2106   BBInfo &MInfo = MBBInfoMap[&MBB];
2107
2108   SmallPtrSet<const MachineBasicBlock*, 8> seen;
2109   for (const MachineInstr &Phi : MBB) {
2110     if (!Phi.isPHI())
2111       break;
2112     seen.clear();
2113
2114     const MachineOperand &MODef = Phi.getOperand(0);
2115     if (!MODef.isReg() || !MODef.isDef()) {
2116       report("Expected first PHI operand to be a register def", &MODef, 0);
2117       continue;
2118     }
2119     if (MODef.isTied() || MODef.isImplicit() || MODef.isInternalRead() ||
2120         MODef.isEarlyClobber() || MODef.isDebug())
2121       report("Unexpected flag on PHI operand", &MODef, 0);
2122     unsigned DefReg = MODef.getReg();
2123     if (!TargetRegisterInfo::isVirtualRegister(DefReg))
2124       report("Expected first PHI operand to be a virtual register", &MODef, 0);
2125
2126     for (unsigned I = 1, E = Phi.getNumOperands(); I != E; I += 2) {
2127       const MachineOperand &MO0 = Phi.getOperand(I);
2128       if (!MO0.isReg()) {
2129         report("Expected PHI operand to be a register", &MO0, I);
2130         continue;
2131       }
2132       if (MO0.isImplicit() || MO0.isInternalRead() || MO0.isEarlyClobber() ||
2133           MO0.isDebug() || MO0.isTied())
2134         report("Unexpected flag on PHI operand", &MO0, I);
2135
2136       const MachineOperand &MO1 = Phi.getOperand(I + 1);
2137       if (!MO1.isMBB()) {
2138         report("Expected PHI operand to be a basic block", &MO1, I + 1);
2139         continue;
2140       }
2141
2142       const MachineBasicBlock &Pre = *MO1.getMBB();
2143       if (!Pre.isSuccessor(&MBB)) {
2144         report("PHI input is not a predecessor block", &MO1, I + 1);
2145         continue;
2146       }
2147
2148       if (MInfo.reachable) {
2149         seen.insert(&Pre);
2150         BBInfo &PrInfo = MBBInfoMap[&Pre];
2151         if (!MO0.isUndef() && PrInfo.reachable &&
2152             !PrInfo.isLiveOut(MO0.getReg()))
2153           report("PHI operand is not live-out from predecessor", &MO0, I);
2154       }
2155     }
2156
2157     // Did we see all predecessors?
2158     if (MInfo.reachable) {
2159       for (MachineBasicBlock *Pred : MBB.predecessors()) {
2160         if (!seen.count(Pred)) {
2161           report("Missing PHI operand", &Phi);
2162           errs() << printMBBReference(*Pred)
2163                  << " is a predecessor according to the CFG.\n";
2164         }
2165       }
2166     }
2167   }
2168 }
2169
2170 void MachineVerifier::visitMachineFunctionAfter() {
2171   calcRegsPassed();
2172
2173   for (const MachineBasicBlock &MBB : *MF)
2174     checkPHIOps(MBB);
2175
2176   // Now check liveness info if available
2177   calcRegsRequired();
2178
2179   // Check for killed virtual registers that should be live out.
2180   for (const auto &MBB : *MF) {
2181     BBInfo &MInfo = MBBInfoMap[&MBB];
2182     for (RegSet::iterator
2183          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
2184          ++I)
2185       if (MInfo.regsKilled.count(*I)) {
2186         report("Virtual register killed in block, but needed live out.", &MBB);
2187         errs() << "Virtual register " << printReg(*I)
2188                << " is used after the block.\n";
2189       }
2190   }
2191
2192   if (!MF->empty()) {
2193     BBInfo &MInfo = MBBInfoMap[&MF->front()];
2194     for (RegSet::iterator
2195          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
2196          ++I) {
2197       report("Virtual register defs don't dominate all uses.", MF);
2198       report_context_vreg(*I);
2199     }
2200   }
2201
2202   if (LiveVars)
2203     verifyLiveVariables();
2204   if (LiveInts)
2205     verifyLiveIntervals();
2206
2207   for (auto CSInfo : MF->getCallSitesInfo())
2208     if (!CSInfo.first->isCall())
2209       report("Call site info referencing instruction that is not call", MF);
2210 }
2211
2212 void MachineVerifier::verifyLiveVariables() {
2213   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
2214   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
2215     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
2216     LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
2217     for (const auto &MBB : *MF) {
2218       BBInfo &MInfo = MBBInfoMap[&MBB];
2219
2220       // Our vregsRequired should be identical to LiveVariables' AliveBlocks
2221       if (MInfo.vregsRequired.count(Reg)) {
2222         if (!VI.AliveBlocks.test(MBB.getNumber())) {
2223           report("LiveVariables: Block missing from AliveBlocks", &MBB);
2224           errs() << "Virtual register " << printReg(Reg)
2225                  << " must be live through the block.\n";
2226         }
2227       } else {
2228         if (VI.AliveBlocks.test(MBB.getNumber())) {
2229           report("LiveVariables: Block should not be in AliveBlocks", &MBB);
2230           errs() << "Virtual register " << printReg(Reg)
2231                  << " is not needed live through the block.\n";
2232         }
2233       }
2234     }
2235   }
2236 }
2237
2238 void MachineVerifier::verifyLiveIntervals() {
2239   assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
2240   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
2241     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
2242
2243     // Spilling and splitting may leave unused registers around. Skip them.
2244     if (MRI->reg_nodbg_empty(Reg))
2245       continue;
2246
2247     if (!LiveInts->hasInterval(Reg)) {
2248       report("Missing live interval for virtual register", MF);
2249       errs() << printReg(Reg, TRI) << " still has defs or uses\n";
2250       continue;
2251     }
2252
2253     const LiveInterval &LI = LiveInts->getInterval(Reg);
2254     assert(Reg == LI.reg && "Invalid reg to interval mapping");
2255     verifyLiveInterval(LI);
2256   }
2257
2258   // Verify all the cached regunit intervals.
2259   for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
2260     if (const LiveRange *LR = LiveInts->getCachedRegUnit(i))
2261       verifyLiveRange(*LR, i);
2262 }
2263
2264 void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR,
2265                                            const VNInfo *VNI, unsigned Reg,
2266                                            LaneBitmask LaneMask) {
2267   if (VNI->isUnused())
2268     return;
2269
2270   const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def);
2271
2272   if (!DefVNI) {
2273     report("Value not live at VNInfo def and not marked unused", MF);
2274     report_context(LR, Reg, LaneMask);
2275     report_context(*VNI);
2276     return;
2277   }
2278
2279   if (DefVNI != VNI) {
2280     report("Live segment at def has different VNInfo", MF);
2281     report_context(LR, Reg, LaneMask);
2282     report_context(*VNI);
2283     return;
2284   }
2285
2286   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
2287   if (!MBB) {
2288     report("Invalid VNInfo definition index", MF);
2289     report_context(LR, Reg, LaneMask);
2290     report_context(*VNI);
2291     return;
2292   }
2293
2294   if (VNI->isPHIDef()) {
2295     if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
2296       report("PHIDef VNInfo is not defined at MBB start", MBB);
2297       report_context(LR, Reg, LaneMask);
2298       report_context(*VNI);
2299     }
2300     return;
2301   }
2302
2303   // Non-PHI def.
2304   const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
2305   if (!MI) {
2306     report("No instruction at VNInfo def index", MBB);
2307     report_context(LR, Reg, LaneMask);
2308     report_context(*VNI);
2309     return;
2310   }
2311
2312   if (Reg != 0) {
2313     bool hasDef = false;
2314     bool isEarlyClobber = false;
2315     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
2316       if (!MOI->isReg() || !MOI->isDef())
2317         continue;
2318       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2319         if (MOI->getReg() != Reg)
2320           continue;
2321       } else {
2322         if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
2323             !TRI->hasRegUnit(MOI->getReg(), Reg))
2324           continue;
2325       }
2326       if (LaneMask.any() &&
2327           (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
2328         continue;
2329       hasDef = true;
2330       if (MOI->isEarlyClobber())
2331         isEarlyClobber = true;
2332     }
2333
2334     if (!hasDef) {
2335       report("Defining instruction does not modify register", MI);
2336       report_context(LR, Reg, LaneMask);
2337       report_context(*VNI);
2338     }
2339
2340     // Early clobber defs begin at USE slots, but other defs must begin at
2341     // DEF slots.
2342     if (isEarlyClobber) {
2343       if (!VNI->def.isEarlyClobber()) {
2344         report("Early clobber def must be at an early-clobber slot", MBB);
2345         report_context(LR, Reg, LaneMask);
2346         report_context(*VNI);
2347       }
2348     } else if (!VNI->def.isRegister()) {
2349       report("Non-PHI, non-early clobber def must be at a register slot", MBB);
2350       report_context(LR, Reg, LaneMask);
2351       report_context(*VNI);
2352     }
2353   }
2354 }
2355
2356 void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
2357                                              const LiveRange::const_iterator I,
2358                                              unsigned Reg, LaneBitmask LaneMask)
2359 {
2360   const LiveRange::Segment &S = *I;
2361   const VNInfo *VNI = S.valno;
2362   assert(VNI && "Live segment has no valno");
2363
2364   if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) {
2365     report("Foreign valno in live segment", MF);
2366     report_context(LR, Reg, LaneMask);
2367     report_context(S);
2368     report_context(*VNI);
2369   }
2370
2371   if (VNI->isUnused()) {
2372     report("Live segment valno is marked unused", MF);
2373     report_context(LR, Reg, LaneMask);
2374     report_context(S);
2375   }
2376
2377   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start);
2378   if (!MBB) {
2379     report("Bad start of live segment, no basic block", MF);
2380     report_context(LR, Reg, LaneMask);
2381     report_context(S);
2382     return;
2383   }
2384   SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
2385   if (S.start != MBBStartIdx && S.start != VNI->def) {
2386     report("Live segment must begin at MBB entry or valno def", MBB);
2387     report_context(LR, Reg, LaneMask);
2388     report_context(S);
2389   }
2390
2391   const MachineBasicBlock *EndMBB =
2392     LiveInts->getMBBFromIndex(S.end.getPrevSlot());
2393   if (!EndMBB) {
2394     report("Bad end of live segment, no basic block", MF);
2395     report_context(LR, Reg, LaneMask);
2396     report_context(S);
2397     return;
2398   }
2399
2400   // No more checks for live-out segments.
2401   if (S.end == LiveInts->getMBBEndIdx(EndMBB))
2402     return;
2403
2404   // RegUnit intervals are allowed dead phis.
2405   if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() &&
2406       S.start == VNI->def && S.end == VNI->def.getDeadSlot())
2407     return;
2408
2409   // The live segment is ending inside EndMBB
2410   const MachineInstr *MI =
2411     LiveInts->getInstructionFromIndex(S.end.getPrevSlot());
2412   if (!MI) {
2413     report("Live segment doesn't end at a valid instruction", EndMBB);
2414     report_context(LR, Reg, LaneMask);
2415     report_context(S);
2416     return;
2417   }
2418
2419   // The block slot must refer to a basic block boundary.
2420   if (S.end.isBlock()) {
2421     report("Live segment ends at B slot of an instruction", EndMBB);
2422     report_context(LR, Reg, LaneMask);
2423     report_context(S);
2424   }
2425
2426   if (S.end.isDead()) {
2427     // Segment ends on the dead slot.
2428     // That means there must be a dead def.
2429     if (!SlotIndex::isSameInstr(S.start, S.end)) {
2430       report("Live segment ending at dead slot spans instructions", EndMBB);
2431       report_context(LR, Reg, LaneMask);
2432       report_context(S);
2433     }
2434   }
2435
2436   // A live segment can only end at an early-clobber slot if it is being
2437   // redefined by an early-clobber def.
2438   if (S.end.isEarlyClobber()) {
2439     if (I+1 == LR.end() || (I+1)->start != S.end) {
2440       report("Live segment ending at early clobber slot must be "
2441              "redefined by an EC def in the same instruction", EndMBB);
2442       report_context(LR, Reg, LaneMask);
2443       report_context(S);
2444     }
2445   }
2446
2447   // The following checks only apply to virtual registers. Physreg liveness
2448   // is too weird to check.
2449   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2450     // A live segment can end with either a redefinition, a kill flag on a
2451     // use, or a dead flag on a def.
2452     bool hasRead = false;
2453     bool hasSubRegDef = false;
2454     bool hasDeadDef = false;
2455     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
2456       if (!MOI->isReg() || MOI->getReg() != Reg)
2457         continue;
2458       unsigned Sub = MOI->getSubReg();
2459       LaneBitmask SLM = Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
2460                                  : LaneBitmask::getAll();
2461       if (MOI->isDef()) {
2462         if (Sub != 0) {
2463           hasSubRegDef = true;
2464           // An operand %0:sub0 reads %0:sub1..n. Invert the lane
2465           // mask for subregister defs. Read-undef defs will be handled by
2466           // readsReg below.
2467           SLM = ~SLM;
2468         }
2469         if (MOI->isDead())
2470           hasDeadDef = true;
2471       }
2472       if (LaneMask.any() && (LaneMask & SLM).none())
2473         continue;
2474       if (MOI->readsReg())
2475         hasRead = true;
2476     }
2477     if (S.end.isDead()) {
2478       // Make sure that the corresponding machine operand for a "dead" live
2479       // range has the dead flag. We cannot perform this check for subregister
2480       // liveranges as partially dead values are allowed.
2481       if (LaneMask.none() && !hasDeadDef) {
2482         report("Instruction ending live segment on dead slot has no dead flag",
2483                MI);
2484         report_context(LR, Reg, LaneMask);
2485         report_context(S);
2486       }
2487     } else {
2488       if (!hasRead) {
2489         // When tracking subregister liveness, the main range must start new
2490         // values on partial register writes, even if there is no read.
2491         if (!MRI->shouldTrackSubRegLiveness(Reg) || LaneMask.any() ||
2492             !hasSubRegDef) {
2493           report("Instruction ending live segment doesn't read the register",
2494                  MI);
2495           report_context(LR, Reg, LaneMask);
2496           report_context(S);
2497         }
2498       }
2499     }
2500   }
2501
2502   // Now check all the basic blocks in this live segment.
2503   MachineFunction::const_iterator MFI = MBB->getIterator();
2504   // Is this live segment the beginning of a non-PHIDef VN?
2505   if (S.start == VNI->def && !VNI->isPHIDef()) {
2506     // Not live-in to any blocks.
2507     if (MBB == EndMBB)
2508       return;
2509     // Skip this block.
2510     ++MFI;
2511   }
2512
2513   SmallVector<SlotIndex, 4> Undefs;
2514   if (LaneMask.any()) {
2515     LiveInterval &OwnerLI = LiveInts->getInterval(Reg);
2516     OwnerLI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
2517   }
2518
2519   while (true) {
2520     assert(LiveInts->isLiveInToMBB(LR, &*MFI));
2521     // We don't know how to track physregs into a landing pad.
2522     if (!TargetRegisterInfo::isVirtualRegister(Reg) &&
2523         MFI->isEHPad()) {
2524       if (&*MFI == EndMBB)
2525         break;
2526       ++MFI;
2527       continue;
2528     }
2529
2530     // Is VNI a PHI-def in the current block?
2531     bool IsPHI = VNI->isPHIDef() &&
2532       VNI->def == LiveInts->getMBBStartIdx(&*MFI);
2533
2534     // Check that VNI is live-out of all predecessors.
2535     for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
2536          PE = MFI->pred_end(); PI != PE; ++PI) {
2537       SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
2538       const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
2539
2540       // All predecessors must have a live-out value. However for a phi
2541       // instruction with subregister intervals
2542       // only one of the subregisters (not necessarily the current one) needs to
2543       // be defined.
2544       if (!PVNI && (LaneMask.none() || !IsPHI)) {
2545         if (LiveRangeCalc::isJointlyDominated(*PI, Undefs, *Indexes))
2546           continue;
2547         report("Register not marked live out of predecessor", *PI);
2548         report_context(LR, Reg, LaneMask);
2549         report_context(*VNI);
2550         errs() << " live into " << printMBBReference(*MFI) << '@'
2551                << LiveInts->getMBBStartIdx(&*MFI) << ", not live before "
2552                << PEnd << '\n';
2553         continue;
2554       }
2555
2556       // Only PHI-defs can take different predecessor values.
2557       if (!IsPHI && PVNI != VNI) {
2558         report("Different value live out of predecessor", *PI);
2559         report_context(LR, Reg, LaneMask);
2560         errs() << "Valno #" << PVNI->id << " live out of "
2561                << printMBBReference(*(*PI)) << '@' << PEnd << "\nValno #"
2562                << VNI->id << " live into " << printMBBReference(*MFI) << '@'
2563                << LiveInts->getMBBStartIdx(&*MFI) << '\n';
2564       }
2565     }
2566     if (&*MFI == EndMBB)
2567       break;
2568     ++MFI;
2569   }
2570 }
2571
2572 void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg,
2573                                       LaneBitmask LaneMask) {
2574   for (const VNInfo *VNI : LR.valnos)
2575     verifyLiveRangeValue(LR, VNI, Reg, LaneMask);
2576
2577   for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I)
2578     verifyLiveRangeSegment(LR, I, Reg, LaneMask);
2579 }
2580
2581 void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
2582   unsigned Reg = LI.reg;
2583   assert(TargetRegisterInfo::isVirtualRegister(Reg));
2584   verifyLiveRange(LI, Reg);
2585
2586   LaneBitmask Mask;
2587   LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
2588   for (const LiveInterval::SubRange &SR : LI.subranges()) {
2589     if ((Mask & SR.LaneMask).any()) {
2590       report("Lane masks of sub ranges overlap in live interval", MF);
2591       report_context(LI);
2592     }
2593     if ((SR.LaneMask & ~MaxMask).any()) {
2594       report("Subrange lanemask is invalid", MF);
2595       report_context(LI);
2596     }
2597     if (SR.empty()) {
2598       report("Subrange must not be empty", MF);
2599       report_context(SR, LI.reg, SR.LaneMask);
2600     }
2601     Mask |= SR.LaneMask;
2602     verifyLiveRange(SR, LI.reg, SR.LaneMask);
2603     if (!LI.covers(SR)) {
2604       report("A Subrange is not covered by the main range", MF);
2605       report_context(LI);
2606     }
2607   }
2608
2609   // Check the LI only has one connected component.
2610   ConnectedVNInfoEqClasses ConEQ(*LiveInts);
2611   unsigned NumComp = ConEQ.Classify(LI);
2612   if (NumComp > 1) {
2613     report("Multiple connected components in live interval", MF);
2614     report_context(LI);
2615     for (unsigned comp = 0; comp != NumComp; ++comp) {
2616       errs() << comp << ": valnos";
2617       for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
2618            E = LI.vni_end(); I!=E; ++I)
2619         if (comp == ConEQ.getEqClass(*I))
2620           errs() << ' ' << (*I)->id;
2621       errs() << '\n';
2622     }
2623   }
2624 }
2625
2626 namespace {
2627
2628   // FrameSetup and FrameDestroy can have zero adjustment, so using a single
2629   // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
2630   // value is zero.
2631   // We use a bool plus an integer to capture the stack state.
2632   struct StackStateOfBB {
2633     StackStateOfBB() = default;
2634     StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
2635       EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
2636       ExitIsSetup(ExitSetup) {}
2637
2638     // Can be negative, which means we are setting up a frame.
2639     int EntryValue = 0;
2640     int ExitValue = 0;
2641     bool EntryIsSetup = false;
2642     bool ExitIsSetup = false;
2643   };
2644
2645 } // end anonymous namespace
2646
2647 /// Make sure on every path through the CFG, a FrameSetup <n> is always followed
2648 /// by a FrameDestroy <n>, stack adjustments are identical on all
2649 /// CFG edges to a merge point, and frame is destroyed at end of a return block.
2650 void MachineVerifier::verifyStackFrame() {
2651   unsigned FrameSetupOpcode   = TII->getCallFrameSetupOpcode();
2652   unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
2653   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
2654     return;
2655
2656   SmallVector<StackStateOfBB, 8> SPState;
2657   SPState.resize(MF->getNumBlockIDs());
2658   df_iterator_default_set<const MachineBasicBlock*> Reachable;
2659
2660   // Visit the MBBs in DFS order.
2661   for (df_ext_iterator<const MachineFunction *,
2662                        df_iterator_default_set<const MachineBasicBlock *>>
2663        DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
2664        DFI != DFE; ++DFI) {
2665     const MachineBasicBlock *MBB = *DFI;
2666
2667     StackStateOfBB BBState;
2668     // Check the exit state of the DFS stack predecessor.
2669     if (DFI.getPathLength() >= 2) {
2670       const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
2671       assert(Reachable.count(StackPred) &&
2672              "DFS stack predecessor is already visited.\n");
2673       BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
2674       BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
2675       BBState.ExitValue = BBState.EntryValue;
2676       BBState.ExitIsSetup = BBState.EntryIsSetup;
2677     }
2678
2679     // Update stack state by checking contents of MBB.
2680     for (const auto &I : *MBB) {
2681       if (I.getOpcode() == FrameSetupOpcode) {
2682         if (BBState.ExitIsSetup)
2683           report("FrameSetup is after another FrameSetup", &I);
2684         BBState.ExitValue -= TII->getFrameTotalSize(I);
2685         BBState.ExitIsSetup = true;
2686       }
2687
2688       if (I.getOpcode() == FrameDestroyOpcode) {
2689         int Size = TII->getFrameTotalSize(I);
2690         if (!BBState.ExitIsSetup)
2691           report("FrameDestroy is not after a FrameSetup", &I);
2692         int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
2693                                                BBState.ExitValue;
2694         if (BBState.ExitIsSetup && AbsSPAdj != Size) {
2695           report("FrameDestroy <n> is after FrameSetup <m>", &I);
2696           errs() << "FrameDestroy <" << Size << "> is after FrameSetup <"
2697               << AbsSPAdj << ">.\n";
2698         }
2699         BBState.ExitValue += Size;
2700         BBState.ExitIsSetup = false;
2701       }
2702     }
2703     SPState[MBB->getNumber()] = BBState;
2704
2705     // Make sure the exit state of any predecessor is consistent with the entry
2706     // state.
2707     for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
2708          E = MBB->pred_end(); I != E; ++I) {
2709       if (Reachable.count(*I) &&
2710           (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue ||
2711            SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
2712         report("The exit stack state of a predecessor is inconsistent.", MBB);
2713         errs() << "Predecessor " << printMBBReference(*(*I))
2714                << " has exit state (" << SPState[(*I)->getNumber()].ExitValue
2715                << ", " << SPState[(*I)->getNumber()].ExitIsSetup << "), while "
2716                << printMBBReference(*MBB) << " has entry state ("
2717                << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
2718       }
2719     }
2720
2721     // Make sure the entry state of any successor is consistent with the exit
2722     // state.
2723     for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
2724          E = MBB->succ_end(); I != E; ++I) {
2725       if (Reachable.count(*I) &&
2726           (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue ||
2727            SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
2728         report("The entry stack state of a successor is inconsistent.", MBB);
2729         errs() << "Successor " << printMBBReference(*(*I))
2730                << " has entry state (" << SPState[(*I)->getNumber()].EntryValue
2731                << ", " << SPState[(*I)->getNumber()].EntryIsSetup << "), while "
2732                << printMBBReference(*MBB) << " has exit state ("
2733                << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
2734       }
2735     }
2736
2737     // Make sure a basic block with return ends with zero stack adjustment.
2738     if (!MBB->empty() && MBB->back().isReturn()) {
2739       if (BBState.ExitIsSetup)
2740         report("A return block ends with a FrameSetup.", MBB);
2741       if (BBState.ExitValue)
2742         report("A return block ends with a nonzero stack adjustment.", MBB);
2743     }
2744   }
2745 }