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/Instructions.h"
  27 #include "llvm/Function.h"
  28 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  29 #include "llvm/CodeGen/LiveVariables.h"
  30 #include "llvm/CodeGen/LiveStackAnalysis.h"
  31 #include "llvm/CodeGen/MachineInstrBundle.h"
  32 #include "llvm/CodeGen/MachineFunctionPass.h"
  33 #include "llvm/CodeGen/MachineFrameInfo.h"
  34 #include "llvm/CodeGen/MachineMemOperand.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/MC/MCAsmInfo.h"
  38 #include "llvm/Target/TargetMachine.h"
  39 #include "llvm/Target/TargetRegisterInfo.h"
  40 #include "llvm/Target/TargetInstrInfo.h"
  41 #include "llvm/ADT/DenseSet.h"
  42 #include "llvm/ADT/SetOperations.h"
  43 #include "llvm/ADT/SmallVector.h"
  44 #include "llvm/Support/Debug.h"
  45 #include "llvm/Support/ErrorHandling.h"
  46 #include "llvm/Support/raw_ostream.h"
  47 using namespace llvm;
  48
  49 namespace {
  50   struct MachineVerifier {
  51
  52     MachineVerifier(Pass *pass, const char *b) :
  53       PASS(pass),
  54       Banner(b),
  55       OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
  56       {}
  57
  58     bool runOnMachineFunction(MachineFunction &MF);
  59
  60     Pass *const PASS;
  61     const char *Banner;
  62     const char *const OutFileName;
  63     raw_ostream *OS;
  64     const MachineFunction *MF;
  65     const TargetMachine *TM;
  66     const TargetInstrInfo *TII;
  67     const TargetRegisterInfo *TRI;
  68     const MachineRegisterInfo *MRI;
  69
  70     unsigned foundErrors;
  71
  72     typedef SmallVector<unsigned, 16> RegVector;
  73     typedef SmallVector<const uint32_t*, 4> RegMaskVector;
  74     typedef DenseSet<unsigned> RegSet;
  75     typedef DenseMap<unsigned, const MachineInstr*> RegMap;
  76
  77     const MachineInstr *FirstTerminator;
  78
  79     BitVector regsReserved;
  80     BitVector regsAllocatable;
  81     RegSet regsLive;
  82     RegVector regsDefined, regsDead, regsKilled;
  83     RegMaskVector regMasks;
  84     RegSet regsLiveInButUnused;
  85
  86     SlotIndex lastIndex;
  87
  88     // Add Reg and any sub-registers to RV
  89     void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
  90       RV.push_back(Reg);
  91       if (TargetRegisterInfo::isPhysicalRegister(Reg))
  92         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
  93           RV.push_back(*SubRegs);
  94     }
  95
  96     struct BBInfo {
  97       // Is this MBB reachable from the MF entry point?
  98       bool reachable;
  99
 100       // Vregs that must be live in because they are used without being
 101       // defined. Map value is the user.
 102       RegMap vregsLiveIn;
 103
 104       // Regs killed in MBB. They may be defined again, and will then be in both
 105       // regsKilled and regsLiveOut.
 106       RegSet regsKilled;
 107
 108       // Regs defined in MBB and live out. Note that vregs passing through may
 109       // be live out without being mentioned here.
 110       RegSet regsLiveOut;
 111
 112       // Vregs that pass through MBB untouched. This set is disjoint from
 113       // regsKilled and regsLiveOut.
 114       RegSet vregsPassed;
 115
 116       // Vregs that must pass through MBB because they are needed by a successor
 117       // block. This set is disjoint from regsLiveOut.
 118       RegSet vregsRequired;
 119
 120       BBInfo() : reachable(false) {}
 121
 122       // Add register to vregsPassed if it belongs there. Return true if
 123       // anything changed.
 124       bool addPassed(unsigned Reg) {
 125         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 126           return false;
 127         if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
 128           return false;
 129         return vregsPassed.insert(Reg).second;
 130       }
 131
 132       // Same for a full set.
 133       bool addPassed(const RegSet &RS) {
 134         bool changed = false;
 135         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
 136           if (addPassed(*I))
 137             changed = true;
 138         return changed;
 139       }
 140
 141       // Add register to vregsRequired if it belongs there. Return true if
 142       // anything changed.
 143       bool addRequired(unsigned Reg) {
 144         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 145           return false;
 146         if (regsLiveOut.count(Reg))
 147           return false;
 148         return vregsRequired.insert(Reg).second;
 149       }
 150
 151       // Same for a full set.
 152       bool addRequired(const RegSet &RS) {
 153         bool changed = false;
 154         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
 155           if (addRequired(*I))
 156             changed = true;
 157         return changed;
 158       }
 159
 160       // Same for a full map.
 161       bool addRequired(const RegMap &RM) {
 162         bool changed = false;
 163         for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
 164           if (addRequired(I->first))
 165             changed = true;
 166         return changed;
 167       }
 168
 169       // Live-out registers are either in regsLiveOut or vregsPassed.
 170       bool isLiveOut(unsigned Reg) const {
 171         return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
 172       }
 173     };
 174
 175     // Extra register info per MBB.
 176     DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
 177
 178     bool isReserved(unsigned Reg) {
 179       return Reg < regsReserved.size() && regsReserved.test(Reg);
 180     }
 181
 182     bool isAllocatable(unsigned Reg) {
 183       return Reg < regsAllocatable.size() && regsAllocatable.test(Reg);
 184     }
 185
 186     // Analysis information if available
 187     LiveVariables *LiveVars;
 188     LiveIntervals *LiveInts;
 189     LiveStacks *LiveStks;
 190     SlotIndexes *Indexes;
 191
 192     void visitMachineFunctionBefore();
 193     void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
 194     void visitMachineBundleBefore(const MachineInstr *MI);
 195     void visitMachineInstrBefore(const MachineInstr *MI);
 196     void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
 197     void visitMachineInstrAfter(const MachineInstr *MI);
 198     void visitMachineBundleAfter(const MachineInstr *MI);
 199     void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
 200     void visitMachineFunctionAfter();
 201
 202     void report(const char *msg, const MachineFunction *MF);
 203     void report(const char *msg, const MachineBasicBlock *MBB);
 204     void report(const char *msg, const MachineInstr *MI);
 205     void report(const char *msg, const MachineOperand *MO, unsigned MONum);
 206     void report(const char *msg, const MachineFunction *MF,
 207                 const LiveInterval &LI);
 208     void report(const char *msg, const MachineBasicBlock *MBB,
 209                 const LiveInterval &LI);
 210
 211     void checkLiveness(const MachineOperand *MO, unsigned MONum);
 212     void markReachable(const MachineBasicBlock *MBB);
 213     void calcRegsPassed();
 214     void checkPHIOps(const MachineBasicBlock *MBB);
 215
 216     void calcRegsRequired();
 217     void verifyLiveVariables();
 218     void verifyLiveIntervals();
 219     void verifyLiveInterval(const LiveInterval&);
 220     void verifyLiveIntervalValue(const LiveInterval&, VNInfo*);
 221     void verifyLiveIntervalSegment(const LiveInterval&,
 222                                    LiveInterval::const_iterator);
 223   };
 224
 225   struct MachineVerifierPass : public MachineFunctionPass {
 226     static char ID; // Pass ID, replacement for typeid
 227     const char *const Banner;
 228
 229     MachineVerifierPass(const char *b = 0)
 230       : MachineFunctionPass(ID), Banner(b) {
 231         initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
 232       }
 233
 234     void getAnalysisUsage(AnalysisUsage &AU) const {
 235       AU.setPreservesAll();
 236       MachineFunctionPass::getAnalysisUsage(AU);
 237     }
 238
 239     bool runOnMachineFunction(MachineFunction &MF) {
 240       MF.verify(this, Banner);
 241       return false;
 242     }
 243   };
 244
 245 }
 246
 247 char MachineVerifierPass::ID = 0;
 248 INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
 249                 "Verify generated machine code", false, false)
 250
 251 FunctionPass *llvm::createMachineVerifierPass(const char *Banner) {
 252   return new MachineVerifierPass(Banner);
 253 }
 254
 255 void MachineFunction::verify(Pass *p, const char *Banner) const {
 256   MachineVerifier(p, Banner)
 257     .runOnMachineFunction(const_cast<MachineFunction&>(*this));
 258 }
 259
 260 bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
 261   raw_ostream *OutFile = 0;
 262   if (OutFileName) {
 263     std::string ErrorInfo;
 264     OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
 265                                  raw_fd_ostream::F_Append);
 266     if (!ErrorInfo.empty()) {
 267       errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
 268       exit(1);
 269     }
 270
 271     OS = OutFile;
 272   } else {
 273     OS = &errs();
 274   }
 275
 276   foundErrors = 0;
 277
 278   this->MF = &MF;
 279   TM = &MF.getTarget();
 280   TII = TM->getInstrInfo();
 281   TRI = TM->getRegisterInfo();
 282   MRI = &MF.getRegInfo();
 283
 284   LiveVars = NULL;
 285   LiveInts = NULL;
 286   LiveStks = NULL;
 287   Indexes = NULL;
 288   if (PASS) {
 289     LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
 290     // We don't want to verify LiveVariables if LiveIntervals is available.
 291     if (!LiveInts)
 292       LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
 293     LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
 294     Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
 295   }
 296
 297   visitMachineFunctionBefore();
 298   for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
 299        MFI!=MFE; ++MFI) {
 300     visitMachineBasicBlockBefore(MFI);
 301     // Keep track of the current bundle header.
 302     const MachineInstr *CurBundle = 0;
 303     for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
 304            MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
 305       if (MBBI->getParent() != MFI) {
 306         report("Bad instruction parent pointer", MFI);
 307         *OS << "Instruction: " << *MBBI;
 308         continue;
 309       }
 310       // Is this a bundle header?
 311       if (!MBBI->isInsideBundle()) {
 312         if (CurBundle)
 313           visitMachineBundleAfter(CurBundle);
 314         CurBundle = MBBI;
 315         visitMachineBundleBefore(CurBundle);
 316       } else if (!CurBundle)
 317         report("No bundle header", MBBI);
 318       visitMachineInstrBefore(MBBI);
 319       for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
 320         visitMachineOperand(&MBBI->getOperand(I), I);
 321       visitMachineInstrAfter(MBBI);
 322     }
 323     if (CurBundle)
 324       visitMachineBundleAfter(CurBundle);
 325     visitMachineBasicBlockAfter(MFI);
 326   }
 327   visitMachineFunctionAfter();
 328
 329   if (OutFile)
 330     delete OutFile;
 331   else if (foundErrors)
 332     report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
 333
 334   // Clean up.
 335   regsLive.clear();
 336   regsDefined.clear();
 337   regsDead.clear();
 338   regsKilled.clear();
 339   regMasks.clear();
 340   regsLiveInButUnused.clear();
 341   MBBInfoMap.clear();
 342
 343   return false;                 // no changes
 344 }
 345
 346 void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
 347   assert(MF);
 348   *OS << '\n';
 349   if (!foundErrors++) {
 350     if (Banner)
 351       *OS << "# " << Banner << '\n';
 352     MF->print(*OS, Indexes);
 353   }
 354   *OS << "*** Bad machine code: " << msg << " ***\n"
 355       << "- function:    " << MF->getFunction()->getName() << "\n";
 356 }
 357
 358 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
 359   assert(MBB);
 360   report(msg, MBB->getParent());
 361   *OS << "- basic block: BB#" << MBB->getNumber()
 362       << ' ' << MBB->getName()
 363       << " (" << (void*)MBB << ')';
 364   if (Indexes)
 365     *OS << " [" << Indexes->getMBBStartIdx(MBB)
 366         << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
 367   *OS << '\n';
 368 }
 369
 370 void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
 371   assert(MI);
 372   report(msg, MI->getParent());
 373   *OS << "- instruction: ";
 374   if (Indexes && Indexes->hasIndex(MI))
 375     *OS << Indexes->getInstructionIndex(MI) << '\t';
 376   MI->print(*OS, TM);
 377 }
 378
 379 void MachineVerifier::report(const char *msg,
 380                              const MachineOperand *MO, unsigned MONum) {
 381   assert(MO);
 382   report(msg, MO->getParent());
 383   *OS << "- operand " << MONum << ":   ";
 384   MO->print(*OS, TM);
 385   *OS << "\n";
 386 }
 387
 388 void MachineVerifier::report(const char *msg, const MachineFunction *MF,
 389                              const LiveInterval &LI) {
 390   report(msg, MF);
 391   *OS << "- interval:    ";
 392   if (TargetRegisterInfo::isVirtualRegister(LI.reg))
 393     *OS << PrintReg(LI.reg, TRI);
 394   else
 395     *OS << PrintRegUnit(LI.reg, TRI);
 396   *OS << ' ' << LI << '\n';
 397 }
 398
 399 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB,
 400                              const LiveInterval &LI) {
 401   report(msg, MBB);
 402   *OS << "- interval:    ";
 403   if (TargetRegisterInfo::isVirtualRegister(LI.reg))
 404     *OS << PrintReg(LI.reg, TRI);
 405   else
 406     *OS << PrintRegUnit(LI.reg, TRI);
 407   *OS << ' ' << LI << '\n';
 408 }
 409
 410 void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
 411   BBInfo &MInfo = MBBInfoMap[MBB];
 412   if (!MInfo.reachable) {
 413     MInfo.reachable = true;
 414     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
 415            SuE = MBB->succ_end(); SuI != SuE; ++SuI)
 416       markReachable(*SuI);
 417   }
 418 }
 419
 420 void MachineVerifier::visitMachineFunctionBefore() {
 421   lastIndex = SlotIndex();
 422   regsReserved = TRI->getReservedRegs(*MF);
 423
 424   // A sub-register of a reserved register is also reserved
 425   for (int Reg = regsReserved.find_first(); Reg>=0;
 426        Reg = regsReserved.find_next(Reg)) {
 427     for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
 428       // FIXME: This should probably be:
 429       // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register");
 430       regsReserved.set(*SubRegs);
 431     }
 432   }
 433
 434   regsAllocatable = TRI->getAllocatableSet(*MF);
 435
 436   markReachable(&MF->front());
 437 }
 438
 439 // Does iterator point to a and b as the first two elements?
 440 static bool matchPair(MachineBasicBlock::const_succ_iterator i,
 441                       const MachineBasicBlock *a, const MachineBasicBlock *b) {
 442   if (*i == a)
 443     return *++i == b;
 444   if (*i == b)
 445     return *++i == a;
 446   return false;
 447 }
 448
 449 void
 450 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
 451   FirstTerminator = 0;
 452
 453   if (MRI->isSSA()) {
 454     // If this block has allocatable physical registers live-in, check that
 455     // it is an entry block or landing pad.
 456     for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
 457            LE = MBB->livein_end();
 458          LI != LE; ++LI) {
 459       unsigned reg = *LI;
 460       if (isAllocatable(reg) && !MBB->isLandingPad() &&
 461           MBB != MBB->getParent()->begin()) {
 462         report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB);
 463       }
 464     }
 465   }
 466
 467   // Count the number of landing pad successors.
 468   SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
 469   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
 470        E = MBB->succ_end(); I != E; ++I) {
 471     if ((*I)->isLandingPad())
 472       LandingPadSuccs.insert(*I);
 473   }
 474
 475   const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
 476   const BasicBlock *BB = MBB->getBasicBlock();
 477   if (LandingPadSuccs.size() > 1 &&
 478       !(AsmInfo &&
 479         AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
 480         BB && isa<SwitchInst>(BB->getTerminator())))
 481     report("MBB has more than one landing pad successor", MBB);
 482
 483   // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
 484   MachineBasicBlock *TBB = 0, *FBB = 0;
 485   SmallVector<MachineOperand, 4> Cond;
 486   if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
 487                           TBB, FBB, Cond)) {
 488     // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
 489     // check whether its answers match up with reality.
 490     if (!TBB && !FBB) {
 491       // Block falls through to its successor.
 492       MachineFunction::const_iterator MBBI = MBB;
 493       ++MBBI;
 494       if (MBBI == MF->end()) {
 495         // It's possible that the block legitimately ends with a noreturn
 496         // call or an unreachable, in which case it won't actually fall
 497         // out the bottom of the function.
 498       } else if (MBB->succ_size() == LandingPadSuccs.size()) {
 499         // It's possible that the block legitimately ends with a noreturn
 500         // call or an unreachable, in which case it won't actuall fall
 501         // out of the block.
 502       } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
 503         report("MBB exits via unconditional fall-through but doesn't have "
 504                "exactly one CFG successor!", MBB);
 505       } else if (!MBB->isSuccessor(MBBI)) {
 506         report("MBB exits via unconditional fall-through but its successor "
 507                "differs from its CFG successor!", MBB);
 508       }
 509       if (!MBB->empty() && getBundleStart(&MBB->back())->isBarrier() &&
 510           !TII->isPredicated(getBundleStart(&MBB->back()))) {
 511         report("MBB exits via unconditional fall-through but ends with a "
 512                "barrier instruction!", MBB);
 513       }
 514       if (!Cond.empty()) {
 515         report("MBB exits via unconditional fall-through but has a condition!",
 516                MBB);
 517       }
 518     } else if (TBB && !FBB && Cond.empty()) {
 519       // Block unconditionally branches somewhere.
 520       if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
 521         report("MBB exits via unconditional branch but doesn't have "
 522                "exactly one CFG successor!", MBB);
 523       } else if (!MBB->isSuccessor(TBB)) {
 524         report("MBB exits via unconditional branch but the CFG "
 525                "successor doesn't match the actual successor!", MBB);
 526       }
 527       if (MBB->empty()) {
 528         report("MBB exits via unconditional branch but doesn't contain "
 529                "any instructions!", MBB);
 530       } else if (!getBundleStart(&MBB->back())->isBarrier()) {
 531         report("MBB exits via unconditional branch but doesn't end with a "
 532                "barrier instruction!", MBB);
 533       } else if (!getBundleStart(&MBB->back())->isTerminator()) {
 534         report("MBB exits via unconditional branch but the branch isn't a "
 535                "terminator instruction!", MBB);
 536       }
 537     } else if (TBB && !FBB && !Cond.empty()) {
 538       // Block conditionally branches somewhere, otherwise falls through.
 539       MachineFunction::const_iterator MBBI = MBB;
 540       ++MBBI;
 541       if (MBBI == MF->end()) {
 542         report("MBB conditionally falls through out of function!", MBB);
 543       } if (MBB->succ_size() != 2) {
 544         report("MBB exits via conditional branch/fall-through but doesn't have "
 545                "exactly two CFG successors!", MBB);
 546       } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
 547         report("MBB exits via conditional branch/fall-through but the CFG "
 548                "successors don't match the actual successors!", MBB);
 549       }
 550       if (MBB->empty()) {
 551         report("MBB exits via conditional branch/fall-through but doesn't "
 552                "contain any instructions!", MBB);
 553       } else if (getBundleStart(&MBB->back())->isBarrier()) {
 554         report("MBB exits via conditional branch/fall-through but ends with a "
 555                "barrier instruction!", MBB);
 556       } else if (!getBundleStart(&MBB->back())->isTerminator()) {
 557         report("MBB exits via conditional branch/fall-through but the branch "
 558                "isn't a terminator instruction!", MBB);
 559       }
 560     } else if (TBB && FBB) {
 561       // Block conditionally branches somewhere, otherwise branches
 562       // somewhere else.
 563       if (MBB->succ_size() != 2) {
 564         report("MBB exits via conditional branch/branch but doesn't have "
 565                "exactly two CFG successors!", MBB);
 566       } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
 567         report("MBB exits via conditional branch/branch but the CFG "
 568                "successors don't match the actual successors!", MBB);
 569       }
 570       if (MBB->empty()) {
 571         report("MBB exits via conditional branch/branch but doesn't "
 572                "contain any instructions!", MBB);
 573       } else if (!getBundleStart(&MBB->back())->isBarrier()) {
 574         report("MBB exits via conditional branch/branch but doesn't end with a "
 575                "barrier instruction!", MBB);
 576       } else if (!getBundleStart(&MBB->back())->isTerminator()) {
 577         report("MBB exits via conditional branch/branch but the branch "
 578                "isn't a terminator instruction!", MBB);
 579       }
 580       if (Cond.empty()) {
 581         report("MBB exits via conditinal branch/branch but there's no "
 582                "condition!", MBB);
 583       }
 584     } else {
 585       report("AnalyzeBranch returned invalid data!", MBB);
 586     }
 587   }
 588
 589   regsLive.clear();
 590   for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
 591          E = MBB->livein_end(); I != E; ++I) {
 592     if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
 593       report("MBB live-in list contains non-physical register", MBB);
 594       continue;
 595     }
 596     regsLive.insert(*I);
 597     for (MCSubRegIterator SubRegs(*I, TRI); SubRegs.isValid(); ++SubRegs)
 598       regsLive.insert(*SubRegs);
 599   }
 600   regsLiveInButUnused = regsLive;
 601
 602   const MachineFrameInfo *MFI = MF->getFrameInfo();
 603   assert(MFI && "Function has no frame info");
 604   BitVector PR = MFI->getPristineRegs(MBB);
 605   for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
 606     regsLive.insert(I);
 607     for (MCSubRegIterator SubRegs(I, TRI); SubRegs.isValid(); ++SubRegs)
 608       regsLive.insert(*SubRegs);
 609   }
 610
 611   regsKilled.clear();
 612   regsDefined.clear();
 613
 614   if (Indexes)
 615     lastIndex = Indexes->getMBBStartIdx(MBB);
 616 }
 617
 618 // This function gets called for all bundle headers, including normal
 619 // stand-alone unbundled instructions.
 620 void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
 621   if (Indexes && Indexes->hasIndex(MI)) {
 622     SlotIndex idx = Indexes->getInstructionIndex(MI);
 623     if (!(idx > lastIndex)) {
 624       report("Instruction index out of order", MI);
 625       *OS << "Last instruction was at " << lastIndex << '\n';
 626     }
 627     lastIndex = idx;
 628   }
 629
 630   // Ensure non-terminators don't follow terminators.
 631   // Ignore predicated terminators formed by if conversion.
 632   // FIXME: If conversion shouldn't need to violate this rule.
 633   if (MI->isTerminator() && !TII->isPredicated(MI)) {
 634     if (!FirstTerminator)
 635       FirstTerminator = MI;
 636   } else if (FirstTerminator) {
 637     report("Non-terminator instruction after the first terminator", MI);
 638     *OS << "First terminator was:\t" << *FirstTerminator;
 639   }
 640 }
 641
 642 void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
 643   const MCInstrDesc &MCID = MI->getDesc();
 644   if (MI->getNumOperands() < MCID.getNumOperands()) {
 645     report("Too few operands", MI);
 646     *OS << MCID.getNumOperands() << " operands expected, but "
 647         << MI->getNumExplicitOperands() << " given.\n";
 648   }
 649
 650   // Check the MachineMemOperands for basic consistency.
 651   for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
 652        E = MI->memoperands_end(); I != E; ++I) {
 653     if ((*I)->isLoad() && !MI->mayLoad())
 654       report("Missing mayLoad flag", MI);
 655     if ((*I)->isStore() && !MI->mayStore())
 656       report("Missing mayStore flag", MI);
 657   }
 658
 659   // Debug values must not have a slot index.
 660   // Other instructions must have one, unless they are inside a bundle.
 661   if (LiveInts) {
 662     bool mapped = !LiveInts->isNotInMIMap(MI);
 663     if (MI->isDebugValue()) {
 664       if (mapped)
 665         report("Debug instruction has a slot index", MI);
 666     } else if (MI->isInsideBundle()) {
 667       if (mapped)
 668         report("Instruction inside bundle has a slot index", MI);
 669     } else {
 670       if (!mapped)
 671         report("Missing slot index", MI);
 672     }
 673   }
 674
 675   StringRef ErrorInfo;
 676   if (!TII->verifyInstruction(MI, ErrorInfo))
 677     report(ErrorInfo.data(), MI);
 678 }
 679
 680 void
 681 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
 682   const MachineInstr *MI = MO->getParent();
 683   const MCInstrDesc &MCID = MI->getDesc();
 684   const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
 685
 686   // The first MCID.NumDefs operands must be explicit register defines
 687   if (MONum < MCID.getNumDefs()) {
 688     if (!MO->isReg())
 689       report("Explicit definition must be a register", MO, MONum);
 690     else if (!MO->isDef() && !MCOI.isOptionalDef())
 691       report("Explicit definition marked as use", MO, MONum);
 692     else if (MO->isImplicit())
 693       report("Explicit definition marked as implicit", MO, MONum);
 694   } else if (MONum < MCID.getNumOperands()) {
 695     // Don't check if it's the last operand in a variadic instruction. See,
 696     // e.g., LDM_RET in the arm back end.
 697     if (MO->isReg() &&
 698         !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
 699       if (MO->isDef() && !MCOI.isOptionalDef())
 700           report("Explicit operand marked as def", MO, MONum);
 701       if (MO->isImplicit())
 702         report("Explicit operand marked as implicit", MO, MONum);
 703     }
 704   } else {
 705     // ARM adds %reg0 operands to indicate predicates. We'll allow that.
 706     if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
 707       report("Extra explicit operand on non-variadic instruction", MO, MONum);
 708   }
 709
 710   switch (MO->getType()) {
 711   case MachineOperand::MO_Register: {
 712     const unsigned Reg = MO->getReg();
 713     if (!Reg)
 714       return;
 715     if (MRI->tracksLiveness() && !MI->isDebugValue())
 716       checkLiveness(MO, MONum);
 717
 718     // Verify two-address constraints after leaving SSA form.
 719     unsigned DefIdx;
 720     if (!MRI->isSSA() && MO->isUse() &&
 721         MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
 722         Reg != MI->getOperand(DefIdx).getReg())
 723       report("Two-address instruction operands must be identical", MO, MONum);
 724
 725     // Check register classes.
 726     if (MONum < MCID.getNumOperands() && !MO->isImplicit()) {
 727       unsigned SubIdx = MO->getSubReg();
 728
 729       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 730         if (SubIdx) {
 731           report("Illegal subregister index for physical register", MO, MONum);
 732           return;
 733         }
 734         if (const TargetRegisterClass *DRC =
 735               TII->getRegClass(MCID, MONum, TRI, *MF)) {
 736           if (!DRC->contains(Reg)) {
 737             report("Illegal physical register for instruction", MO, MONum);
 738             *OS << TRI->getName(Reg) << " is not a "
 739                 << DRC->getName() << " register.\n";
 740           }
 741         }
 742       } else {
 743         // Virtual register.
 744         const TargetRegisterClass *RC = MRI->getRegClass(Reg);
 745         if (SubIdx) {
 746           const TargetRegisterClass *SRC =
 747             TRI->getSubClassWithSubReg(RC, SubIdx);
 748           if (!SRC) {
 749             report("Invalid subregister index for virtual register", MO, MONum);
 750             *OS << "Register class " << RC->getName()
 751                 << " does not support subreg index " << SubIdx << "\n";
 752             return;
 753           }
 754           if (RC != SRC) {
 755             report("Invalid register class for subregister index", MO, MONum);
 756             *OS << "Register class " << RC->getName()
 757                 << " does not fully support subreg index " << SubIdx << "\n";
 758             return;
 759           }
 760         }
 761         if (const TargetRegisterClass *DRC =
 762               TII->getRegClass(MCID, MONum, TRI, *MF)) {
 763           if (SubIdx) {
 764             const TargetRegisterClass *SuperRC =
 765               TRI->getLargestLegalSuperClass(RC);
 766             if (!SuperRC) {
 767               report("No largest legal super class exists.", MO, MONum);
 768               return;
 769             }
 770             DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
 771             if (!DRC) {
 772               report("No matching super-reg register class.", MO, MONum);
 773               return;
 774             }
 775           }
 776           if (!RC->hasSuperClassEq(DRC)) {
 777             report("Illegal virtual register for instruction", MO, MONum);
 778             *OS << "Expected a " << DRC->getName() << " register, but got a "
 779                 << RC->getName() << " register\n";
 780           }
 781         }
 782       }
 783     }
 784     break;
 785   }
 786
 787   case MachineOperand::MO_RegisterMask:
 788     regMasks.push_back(MO->getRegMask());
 789     break;
 790
 791   case MachineOperand::MO_MachineBasicBlock:
 792     if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
 793       report("PHI operand is not in the CFG", MO, MONum);
 794     break;
 795
 796   case MachineOperand::MO_FrameIndex:
 797     if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
 798         LiveInts && !LiveInts->isNotInMIMap(MI)) {
 799       LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
 800       SlotIndex Idx = LiveInts->getInstructionIndex(MI);
 801       if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) {
 802         report("Instruction loads from dead spill slot", MO, MONum);
 803         *OS << "Live stack: " << LI << '\n';
 804       }
 805       if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) {
 806         report("Instruction stores to dead spill slot", MO, MONum);
 807         *OS << "Live stack: " << LI << '\n';
 808       }
 809     }
 810     break;
 811
 812   default:
 813     break;
 814   }
 815 }
 816
 817 void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
 818   const MachineInstr *MI = MO->getParent();
 819   const unsigned Reg = MO->getReg();
 820
 821   // Both use and def operands can read a register.
 822   if (MO->readsReg()) {
 823     regsLiveInButUnused.erase(Reg);
 824
 825     if (MO->isKill())
 826       addRegWithSubRegs(regsKilled, Reg);
 827
 828     // Check that LiveVars knows this kill.
 829     if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
 830         MO->isKill()) {
 831       LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
 832       if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end())
 833         report("Kill missing from LiveVariables", MO, MONum);
 834     }
 835
 836     // Check LiveInts liveness and kill.
 837     if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
 838       SlotIndex UseIdx = LiveInts->getInstructionIndex(MI);
 839       // Check the cached regunit intervals.
 840       if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
 841         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
 842           if (const LiveInterval *LI = LiveInts->getCachedRegUnit(*Units)) {
 843             LiveRangeQuery LRQ(*LI, UseIdx);
 844             if (!LRQ.valueIn()) {
 845               report("No live range at use", MO, MONum);
 846               *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI)
 847                   << ' ' << *LI << '\n';
 848             }
 849             if (MO->isKill() && !LRQ.isKill()) {
 850               report("Live range continues after kill flag", MO, MONum);
 851               *OS << PrintRegUnit(*Units, TRI) << ' ' << *LI << '\n';
 852             }
 853           }
 854         }
 855       }
 856
 857       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 858         if (LiveInts->hasInterval(Reg)) {
 859           // This is a virtual register interval.
 860           const LiveInterval &LI = LiveInts->getInterval(Reg);
 861           LiveRangeQuery LRQ(LI, UseIdx);
 862           if (!LRQ.valueIn()) {
 863             report("No live range at use", MO, MONum);
 864             *OS << UseIdx << " is not live in " << LI << '\n';
 865           }
 866           // Check for extra kill flags.
 867           // Note that we allow missing kill flags for now.
 868           if (MO->isKill() && !LRQ.isKill()) {
 869             report("Live range continues after kill flag", MO, MONum);
 870             *OS << "Live range: " << LI << '\n';
 871           }
 872         } else {
 873           report("Virtual register has no live interval", MO, MONum);
 874         }
 875       }
 876     }
 877
 878     // Use of a dead register.
 879     if (!regsLive.count(Reg)) {
 880       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 881         // Reserved registers may be used even when 'dead'.
 882         if (!isReserved(Reg))
 883           report("Using an undefined physical register", MO, MONum);
 884       } else if (MRI->def_empty(Reg)) {
 885         report("Reading virtual register without a def", MO, MONum);
 886       } else {
 887         BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 888         // We don't know which virtual registers are live in, so only complain
 889         // if vreg was killed in this MBB. Otherwise keep track of vregs that
 890         // must be live in. PHI instructions are handled separately.
 891         if (MInfo.regsKilled.count(Reg))
 892           report("Using a killed virtual register", MO, MONum);
 893         else if (!MI->isPHI())
 894           MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
 895       }
 896     }
 897   }
 898
 899   if (MO->isDef()) {
 900     // Register defined.
 901     // TODO: verify that earlyclobber ops are not used.
 902     if (MO->isDead())
 903       addRegWithSubRegs(regsDead, Reg);
 904     else
 905       addRegWithSubRegs(regsDefined, Reg);
 906
 907     // Verify SSA form.
 908     if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
 909         llvm::next(MRI->def_begin(Reg)) != MRI->def_end())
 910       report("Multiple virtual register defs in SSA form", MO, MONum);
 911
 912     // Check LiveInts for a live range, but only for virtual registers.
 913     if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
 914         !LiveInts->isNotInMIMap(MI)) {
 915       SlotIndex DefIdx = LiveInts->getInstructionIndex(MI);
 916       DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
 917       if (LiveInts->hasInterval(Reg)) {
 918         const LiveInterval &LI = LiveInts->getInterval(Reg);
 919         if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
 920           assert(VNI && "NULL valno is not allowed");
 921           if (VNI->def != DefIdx) {
 922             report("Inconsistent valno->def", MO, MONum);
 923             *OS << "Valno " << VNI->id << " is not defined at "
 924               << DefIdx << " in " << LI << '\n';
 925           }
 926         } else {
 927           report("No live range at def", MO, MONum);
 928           *OS << DefIdx << " is not live in " << LI << '\n';
 929         }
 930       } else {
 931         report("Virtual register has no Live interval", MO, MONum);
 932       }
 933     }
 934   }
 935 }
 936
 937 void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
 938 }
 939
 940 // This function gets called after visiting all instructions in a bundle. The
 941 // argument points to the bundle header.
 942 // Normal stand-alone instructions are also considered 'bundles', and this
 943 // function is called for all of them.
 944 void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
 945   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 946   set_union(MInfo.regsKilled, regsKilled);
 947   set_subtract(regsLive, regsKilled); regsKilled.clear();
 948   // Kill any masked registers.
 949   while (!regMasks.empty()) {
 950     const uint32_t *Mask = regMasks.pop_back_val();
 951     for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
 952       if (TargetRegisterInfo::isPhysicalRegister(*I) &&
 953           MachineOperand::clobbersPhysReg(Mask, *I))
 954         regsDead.push_back(*I);
 955   }
 956   set_subtract(regsLive, regsDead);   regsDead.clear();
 957   set_union(regsLive, regsDefined);   regsDefined.clear();
 958 }
 959
 960 void
 961 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
 962   MBBInfoMap[MBB].regsLiveOut = regsLive;
 963   regsLive.clear();
 964
 965   if (Indexes) {
 966     SlotIndex stop = Indexes->getMBBEndIdx(MBB);
 967     if (!(stop > lastIndex)) {
 968       report("Block ends before last instruction index", MBB);
 969       *OS << "Block ends at " << stop
 970           << " last instruction was at " << lastIndex << '\n';
 971     }
 972     lastIndex = stop;
 973   }
 974 }
 975
 976 // Calculate the largest possible vregsPassed sets. These are the registers that
 977 // can pass through an MBB live, but may not be live every time. It is assumed
 978 // that all vregsPassed sets are empty before the call.
 979 void MachineVerifier::calcRegsPassed() {
 980   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
 981   // have any vregsPassed.
 982   SmallPtrSet<const MachineBasicBlock*, 8> todo;
 983   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 984        MFI != MFE; ++MFI) {
 985     const MachineBasicBlock &MBB(*MFI);
 986     BBInfo &MInfo = MBBInfoMap[&MBB];
 987     if (!MInfo.reachable)
 988       continue;
 989     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
 990            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
 991       BBInfo &SInfo = MBBInfoMap[*SuI];
 992       if (SInfo.addPassed(MInfo.regsLiveOut))
 993         todo.insert(*SuI);
 994     }
 995   }
 996
 997   // Iteratively push vregsPassed to successors. This will converge to the same
 998   // final state regardless of DenseSet iteration order.
 999   while (!todo.empty()) {
1000     const MachineBasicBlock *MBB = *todo.begin();
1001     todo.erase(MBB);
1002     BBInfo &MInfo = MBBInfoMap[MBB];
1003     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
1004            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
1005       if (*SuI == MBB)
1006         continue;
1007       BBInfo &SInfo = MBBInfoMap[*SuI];
1008       if (SInfo.addPassed(MInfo.vregsPassed))
1009         todo.insert(*SuI);
1010     }
1011   }
1012 }
1013
1014 // Calculate the set of virtual registers that must be passed through each basic
1015 // block in order to satisfy the requirements of successor blocks. This is very
1016 // similar to calcRegsPassed, only backwards.
1017 void MachineVerifier::calcRegsRequired() {
1018   // First push live-in regs to predecessors' vregsRequired.
1019   SmallPtrSet<const MachineBasicBlock*, 8> todo;
1020   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1021        MFI != MFE; ++MFI) {
1022     const MachineBasicBlock &MBB(*MFI);
1023     BBInfo &MInfo = MBBInfoMap[&MBB];
1024     for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
1025            PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
1026       BBInfo &PInfo = MBBInfoMap[*PrI];
1027       if (PInfo.addRequired(MInfo.vregsLiveIn))
1028         todo.insert(*PrI);
1029     }
1030   }
1031
1032   // Iteratively push vregsRequired to predecessors. This will converge to the
1033   // same final state regardless of DenseSet iteration order.
1034   while (!todo.empty()) {
1035     const MachineBasicBlock *MBB = *todo.begin();
1036     todo.erase(MBB);
1037     BBInfo &MInfo = MBBInfoMap[MBB];
1038     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1039            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1040       if (*PrI == MBB)
1041         continue;
1042       BBInfo &SInfo = MBBInfoMap[*PrI];
1043       if (SInfo.addRequired(MInfo.vregsRequired))
1044         todo.insert(*PrI);
1045     }
1046   }
1047 }
1048
1049 // Check PHI instructions at the beginning of MBB. It is assumed that
1050 // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
1051 void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
1052   SmallPtrSet<const MachineBasicBlock*, 8> seen;
1053   for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
1054        BBI != BBE && BBI->isPHI(); ++BBI) {
1055     seen.clear();
1056
1057     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
1058       unsigned Reg = BBI->getOperand(i).getReg();
1059       const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
1060       if (!Pre->isSuccessor(MBB))
1061         continue;
1062       seen.insert(Pre);
1063       BBInfo &PrInfo = MBBInfoMap[Pre];
1064       if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
1065         report("PHI operand is not live-out from predecessor",
1066                &BBI->getOperand(i), i);
1067     }
1068
1069     // Did we see all predecessors?
1070     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1071            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1072       if (!seen.count(*PrI)) {
1073         report("Missing PHI operand", BBI);
1074         *OS << "BB#" << (*PrI)->getNumber()
1075             << " is a predecessor according to the CFG.\n";
1076       }
1077     }
1078   }
1079 }
1080
1081 void MachineVerifier::visitMachineFunctionAfter() {
1082   calcRegsPassed();
1083
1084   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1085        MFI != MFE; ++MFI) {
1086     BBInfo &MInfo = MBBInfoMap[MFI];
1087
1088     // Skip unreachable MBBs.
1089     if (!MInfo.reachable)
1090       continue;
1091
1092     checkPHIOps(MFI);
1093   }
1094
1095   // Now check liveness info if available
1096   calcRegsRequired();
1097
1098   // Check for killed virtual registers that should be live out.
1099   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1100        MFI != MFE; ++MFI) {
1101     BBInfo &MInfo = MBBInfoMap[MFI];
1102     for (RegSet::iterator
1103          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1104          ++I)
1105       if (MInfo.regsKilled.count(*I)) {
1106         report("Virtual register killed in block, but needed live out.", MFI);
1107         *OS << "Virtual register " << PrintReg(*I)
1108             << " is used after the block.\n";
1109       }
1110   }
1111
1112   if (!MF->empty()) {
1113     BBInfo &MInfo = MBBInfoMap[&MF->front()];
1114     for (RegSet::iterator
1115          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1116          ++I)
1117       report("Virtual register def doesn't dominate all uses.",
1118              MRI->getVRegDef(*I));
1119   }
1120
1121   if (LiveVars)
1122     verifyLiveVariables();
1123   if (LiveInts)
1124     verifyLiveIntervals();
1125 }
1126
1127 void MachineVerifier::verifyLiveVariables() {
1128   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
1129   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1130     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1131     LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1132     for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1133          MFI != MFE; ++MFI) {
1134       BBInfo &MInfo = MBBInfoMap[MFI];
1135
1136       // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1137       if (MInfo.vregsRequired.count(Reg)) {
1138         if (!VI.AliveBlocks.test(MFI->getNumber())) {
1139           report("LiveVariables: Block missing from AliveBlocks", MFI);
1140           *OS << "Virtual register " << PrintReg(Reg)
1141               << " must be live through the block.\n";
1142         }
1143       } else {
1144         if (VI.AliveBlocks.test(MFI->getNumber())) {
1145           report("LiveVariables: Block should not be in AliveBlocks", MFI);
1146           *OS << "Virtual register " << PrintReg(Reg)
1147               << " is not needed live through the block.\n";
1148         }
1149       }
1150     }
1151   }
1152 }
1153
1154 void MachineVerifier::verifyLiveIntervals() {
1155   assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
1156   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1157     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1158
1159     // Spilling and splitting may leave unused registers around. Skip them.
1160     if (MRI->reg_nodbg_empty(Reg))
1161       continue;
1162
1163     if (!LiveInts->hasInterval(Reg)) {
1164       report("Missing live interval for virtual register", MF);
1165       *OS << PrintReg(Reg, TRI) << " still has defs or uses\n";
1166       continue;
1167     }
1168
1169     const LiveInterval &LI = LiveInts->getInterval(Reg);
1170     assert(Reg == LI.reg && "Invalid reg to interval mapping");
1171     verifyLiveInterval(LI);
1172   }
1173
1174   // Verify all the cached regunit intervals.
1175   for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
1176     if (const LiveInterval *LI = LiveInts->getCachedRegUnit(i))
1177       verifyLiveInterval(*LI);
1178 }
1179
1180 void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI,
1181                                               VNInfo *VNI) {
1182   if (VNI->isUnused())
1183     return;
1184
1185   const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
1186
1187   if (!DefVNI) {
1188     report("Valno not live at def and not marked unused", MF, LI);
1189     *OS << "Valno #" << VNI->id << '\n';
1190     return;
1191   }
1192
1193   if (DefVNI != VNI) {
1194     report("Live range at def has different valno", MF, LI);
1195     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1196         << " where valno #" << DefVNI->id << " is live\n";
1197     return;
1198   }
1199
1200   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1201   if (!MBB) {
1202     report("Invalid definition index", MF, LI);
1203     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1204         << " in " << LI << '\n';
1205     return;
1206   }
1207
1208   if (VNI->isPHIDef()) {
1209     if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1210       report("PHIDef value is not defined at MBB start", MBB, LI);
1211       *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1212           << ", not at the beginning of BB#" << MBB->getNumber() << '\n';
1213     }
1214     return;
1215   }
1216
1217   // Non-PHI def.
1218   const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1219   if (!MI) {
1220     report("No instruction at def index", MBB, LI);
1221     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1222     return;
1223   }
1224
1225   bool hasDef = false;
1226   bool isEarlyClobber = false;
1227   for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1228     if (!MOI->isReg() || !MOI->isDef())
1229       continue;
1230     if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1231       if (MOI->getReg() != LI.reg)
1232         continue;
1233     } else {
1234       if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1235           !TRI->hasRegUnit(MOI->getReg(), LI.reg))
1236         continue;
1237     }
1238     hasDef = true;
1239     if (MOI->isEarlyClobber())
1240       isEarlyClobber = true;
1241   }
1242
1243   if (!hasDef) {
1244     report("Defining instruction does not modify register", MI);
1245     *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1246   }
1247
1248   // Early clobber defs begin at USE slots, but other defs must begin at
1249   // DEF slots.
1250   if (isEarlyClobber) {
1251     if (!VNI->def.isEarlyClobber()) {
1252       report("Early clobber def must be at an early-clobber slot", MBB, LI);
1253       *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1254     }
1255   } else if (!VNI->def.isRegister()) {
1256     report("Non-PHI, non-early clobber def must be at a register slot",
1257            MBB, LI);
1258     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1259   }
1260 }
1261
1262 void
1263 MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI,
1264                                            LiveInterval::const_iterator I) {
1265   const VNInfo *VNI = I->valno;
1266   assert(VNI && "Live range has no valno");
1267
1268   if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
1269     report("Foreign valno in live range", MF, LI);
1270     *OS << *I << " has a bad valno\n";
1271   }
1272
1273   if (VNI->isUnused()) {
1274     report("Live range valno is marked unused", MF, LI);
1275     *OS << *I << '\n';
1276   }
1277
1278   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
1279   if (!MBB) {
1280     report("Bad start of live segment, no basic block", MF, LI);
1281     *OS << *I << '\n';
1282     return;
1283   }
1284   SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1285   if (I->start != MBBStartIdx && I->start != VNI->def) {
1286     report("Live segment must begin at MBB entry or valno def", MBB, LI);
1287     *OS << *I << '\n';
1288   }
1289
1290   const MachineBasicBlock *EndMBB =
1291     LiveInts->getMBBFromIndex(I->end.getPrevSlot());
1292   if (!EndMBB) {
1293     report("Bad end of live segment, no basic block", MF, LI);
1294     *OS << *I << '\n';
1295     return;
1296   }
1297
1298   // No more checks for live-out segments.
1299   if (I->end == LiveInts->getMBBEndIdx(EndMBB))
1300     return;
1301
1302   // RegUnit intervals are allowed dead phis.
1303   if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && VNI->isPHIDef() &&
1304       I->start == VNI->def && I->end == VNI->def.getDeadSlot())
1305     return;
1306
1307   // The live segment is ending inside EndMBB
1308   const MachineInstr *MI =
1309     LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
1310   if (!MI) {
1311     report("Live segment doesn't end at a valid instruction", EndMBB, LI);
1312     *OS << *I << '\n';
1313     return;
1314   }
1315
1316   // The block slot must refer to a basic block boundary.
1317   if (I->end.isBlock()) {
1318     report("Live segment ends at B slot of an instruction", EndMBB, LI);
1319     *OS << *I << '\n';
1320   }
1321
1322   if (I->end.isDead()) {
1323     // Segment ends on the dead slot.
1324     // That means there must be a dead def.
1325     if (!SlotIndex::isSameInstr(I->start, I->end)) {
1326       report("Live segment ending at dead slot spans instructions", EndMBB, LI);
1327       *OS << *I << '\n';
1328     }
1329   }
1330
1331   // A live segment can only end at an early-clobber slot if it is being
1332   // redefined by an early-clobber def.
1333   if (I->end.isEarlyClobber()) {
1334     if (I+1 == LI.end() || (I+1)->start != I->end) {
1335       report("Live segment ending at early clobber slot must be "
1336              "redefined by an EC def in the same instruction", EndMBB, LI);
1337       *OS << *I << '\n';
1338     }
1339   }
1340
1341   // The following checks only apply to virtual registers. Physreg liveness
1342   // is too weird to check.
1343   if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1344     // A live range can end with either a redefinition, a kill flag on a
1345     // use, or a dead flag on a def.
1346     bool hasRead = false;
1347     bool hasDeadDef = false;
1348     for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1349       if (!MOI->isReg() || MOI->getReg() != LI.reg)
1350         continue;
1351       if (MOI->readsReg())
1352         hasRead = true;
1353       if (MOI->isDef() && MOI->isDead())
1354         hasDeadDef = true;
1355     }
1356
1357     if (I->end.isDead()) {
1358       if (!hasDeadDef) {
1359         report("Instruction doesn't have a dead def operand", MI);
1360         I->print(*OS);
1361         *OS << " in " << LI << '\n';
1362       }
1363     } else {
1364       if (!hasRead) {
1365         report("Instruction ending live range doesn't read the register", MI);
1366         *OS << *I << " in " << LI << '\n';
1367       }
1368     }
1369   }
1370
1371   // Now check all the basic blocks in this live segment.
1372   MachineFunction::const_iterator MFI = MBB;
1373   // Is this live range the beginning of a non-PHIDef VN?
1374   if (I->start == VNI->def && !VNI->isPHIDef()) {
1375     // Not live-in to any blocks.
1376     if (MBB == EndMBB)
1377       return;
1378     // Skip this block.
1379     ++MFI;
1380   }
1381   for (;;) {
1382     assert(LiveInts->isLiveInToMBB(LI, MFI));
1383     // We don't know how to track physregs into a landing pad.
1384     if (!TargetRegisterInfo::isVirtualRegister(LI.reg) &&
1385         MFI->isLandingPad()) {
1386       if (&*MFI == EndMBB)
1387         break;
1388       ++MFI;
1389       continue;
1390     }
1391
1392     // Is VNI a PHI-def in the current block?
1393     bool IsPHI = VNI->isPHIDef() &&
1394       VNI->def == LiveInts->getMBBStartIdx(MFI);
1395
1396     // Check that VNI is live-out of all predecessors.
1397     for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1398          PE = MFI->pred_end(); PI != PE; ++PI) {
1399       SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
1400       const VNInfo *PVNI = LI.getVNInfoBefore(PEnd);
1401
1402       // All predecessors must have a live-out value.
1403       if (!PVNI) {
1404         report("Register not marked live out of predecessor", *PI, LI);
1405         *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1406             << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
1407             << PEnd << '\n';
1408         continue;
1409       }
1410
1411       // Only PHI-defs can take different predecessor values.
1412       if (!IsPHI && PVNI != VNI) {
1413         report("Different value live out of predecessor", *PI, LI);
1414         *OS << "Valno #" << PVNI->id << " live out of BB#"
1415             << (*PI)->getNumber() << '@' << PEnd
1416             << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1417             << '@' << LiveInts->getMBBStartIdx(MFI) << '\n';
1418       }
1419     }
1420     if (&*MFI == EndMBB)
1421       break;
1422     ++MFI;
1423   }
1424 }
1425
1426 void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
1427   for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
1428        I!=E; ++I)
1429     verifyLiveIntervalValue(LI, *I);
1430
1431   for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I)
1432     verifyLiveIntervalSegment(LI, I);
1433
1434   // Check the LI only has one connected component.
1435   if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1436     ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1437     unsigned NumComp = ConEQ.Classify(&LI);
1438     if (NumComp > 1) {
1439       report("Multiple connected components in live interval", MF, LI);
1440       for (unsigned comp = 0; comp != NumComp; ++comp) {
1441         *OS << comp << ": valnos";
1442         for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1443              E = LI.vni_end(); I!=E; ++I)
1444           if (comp == ConEQ.getEqClass(*I))
1445             *OS << ' ' << (*I)->id;
1446         *OS << '\n';
1447       }
1448     }
1449   }
1450 }