contrib/llvm/lib/CodeGen/MachineVerifier.cpp

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