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
 685   // The first MCID.NumDefs operands must be explicit register defines
 686   if (MONum < MCID.getNumDefs()) {
 687     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
 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     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
 696     // Don't check if it's the last operand in a variadic instruction. See,
 697     // e.g., LDM_RET in the arm back end.
 698     if (MO->isReg() &&
 699         !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
 700       if (MO->isDef() && !MCOI.isOptionalDef())
 701           report("Explicit operand marked as def", MO, MONum);
 702       if (MO->isImplicit())
 703         report("Explicit operand marked as implicit", MO, MONum);
 704     }
 705   } else {
 706     // ARM adds %reg0 operands to indicate predicates. We'll allow that.
 707     if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
 708       report("Extra explicit operand on non-variadic instruction", MO, MONum);
 709   }
 710
 711   switch (MO->getType()) {
 712   case MachineOperand::MO_Register: {
 713     const unsigned Reg = MO->getReg();
 714     if (!Reg)
 715       return;
 716     if (MRI->tracksLiveness() && !MI->isDebugValue())
 717       checkLiveness(MO, MONum);
 718
 719     // Verify two-address constraints after leaving SSA form.
 720     unsigned DefIdx;
 721     if (!MRI->isSSA() && MO->isUse() &&
 722         MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
 723         Reg != MI->getOperand(DefIdx).getReg())
 724       report("Two-address instruction operands must be identical", MO, MONum);
 725
 726     // Check register classes.
 727     if (MONum < MCID.getNumOperands() && !MO->isImplicit()) {
 728       unsigned SubIdx = MO->getSubReg();
 729
 730       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 731         if (SubIdx) {
 732           report("Illegal subregister index for physical register", MO, MONum);
 733           return;
 734         }
 735         if (const TargetRegisterClass *DRC =
 736               TII->getRegClass(MCID, MONum, TRI, *MF)) {
 737           if (!DRC->contains(Reg)) {
 738             report("Illegal physical register for instruction", MO, MONum);
 739             *OS << TRI->getName(Reg) << " is not a "
 740                 << DRC->getName() << " register.\n";
 741           }
 742         }
 743       } else {
 744         // Virtual register.
 745         const TargetRegisterClass *RC = MRI->getRegClass(Reg);
 746         if (SubIdx) {
 747           const TargetRegisterClass *SRC =
 748             TRI->getSubClassWithSubReg(RC, SubIdx);
 749           if (!SRC) {
 750             report("Invalid subregister index for virtual register", MO, MONum);
 751             *OS << "Register class " << RC->getName()
 752                 << " does not support subreg index " << SubIdx << "\n";
 753             return;
 754           }
 755           if (RC != SRC) {
 756             report("Invalid register class for subregister index", MO, MONum);
 757             *OS << "Register class " << RC->getName()
 758                 << " does not fully support subreg index " << SubIdx << "\n";
 759             return;
 760           }
 761         }
 762         if (const TargetRegisterClass *DRC =
 763               TII->getRegClass(MCID, MONum, TRI, *MF)) {
 764           if (SubIdx) {
 765             const TargetRegisterClass *SuperRC =
 766               TRI->getLargestLegalSuperClass(RC);
 767             if (!SuperRC) {
 768               report("No largest legal super class exists.", MO, MONum);
 769               return;
 770             }
 771             DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
 772             if (!DRC) {
 773               report("No matching super-reg register class.", MO, MONum);
 774               return;
 775             }
 776           }
 777           if (!RC->hasSuperClassEq(DRC)) {
 778             report("Illegal virtual register for instruction", MO, MONum);
 779             *OS << "Expected a " << DRC->getName() << " register, but got a "
 780                 << RC->getName() << " register\n";
 781           }
 782         }
 783       }
 784     }
 785     break;
 786   }
 787
 788   case MachineOperand::MO_RegisterMask:
 789     regMasks.push_back(MO->getRegMask());
 790     break;
 791
 792   case MachineOperand::MO_MachineBasicBlock:
 793     if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
 794       report("PHI operand is not in the CFG", MO, MONum);
 795     break;
 796
 797   case MachineOperand::MO_FrameIndex:
 798     if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
 799         LiveInts && !LiveInts->isNotInMIMap(MI)) {
 800       LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
 801       SlotIndex Idx = LiveInts->getInstructionIndex(MI);
 802       if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) {
 803         report("Instruction loads from dead spill slot", MO, MONum);
 804         *OS << "Live stack: " << LI << '\n';
 805       }
 806       if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) {
 807         report("Instruction stores to dead spill slot", MO, MONum);
 808         *OS << "Live stack: " << LI << '\n';
 809       }
 810     }
 811     break;
 812
 813   default:
 814     break;
 815   }
 816 }
 817
 818 void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
 819   const MachineInstr *MI = MO->getParent();
 820   const unsigned Reg = MO->getReg();
 821
 822   // Both use and def operands can read a register.
 823   if (MO->readsReg()) {
 824     regsLiveInButUnused.erase(Reg);
 825
 826     if (MO->isKill())
 827       addRegWithSubRegs(regsKilled, Reg);
 828
 829     // Check that LiveVars knows this kill.
 830     if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
 831         MO->isKill()) {
 832       LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
 833       if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end())
 834         report("Kill missing from LiveVariables", MO, MONum);
 835     }
 836
 837     // Check LiveInts liveness and kill.
 838     if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
 839       SlotIndex UseIdx = LiveInts->getInstructionIndex(MI);
 840       // Check the cached regunit intervals.
 841       if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
 842         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
 843           if (const LiveInterval *LI = LiveInts->getCachedRegUnit(*Units)) {
 844             LiveRangeQuery LRQ(*LI, UseIdx);
 845             if (!LRQ.valueIn()) {
 846               report("No live range at use", MO, MONum);
 847               *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI)
 848                   << ' ' << *LI << '\n';
 849             }
 850             if (MO->isKill() && !LRQ.isKill()) {
 851               report("Live range continues after kill flag", MO, MONum);
 852               *OS << PrintRegUnit(*Units, TRI) << ' ' << *LI << '\n';
 853             }
 854           }
 855         }
 856       }
 857
 858       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 859         if (LiveInts->hasInterval(Reg)) {
 860           // This is a virtual register interval.
 861           const LiveInterval &LI = LiveInts->getInterval(Reg);
 862           LiveRangeQuery LRQ(LI, UseIdx);
 863           if (!LRQ.valueIn()) {
 864             report("No live range at use", MO, MONum);
 865             *OS << UseIdx << " is not live in " << LI << '\n';
 866           }
 867           // Check for extra kill flags.
 868           // Note that we allow missing kill flags for now.
 869           if (MO->isKill() && !LRQ.isKill()) {
 870             report("Live range continues after kill flag", MO, MONum);
 871             *OS << "Live range: " << LI << '\n';
 872           }
 873         } else {
 874           report("Virtual register has no live interval", MO, MONum);
 875         }
 876       }
 877     }
 878
 879     // Use of a dead register.
 880     if (!regsLive.count(Reg)) {
 881       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 882         // Reserved registers may be used even when 'dead'.
 883         if (!isReserved(Reg))
 884           report("Using an undefined physical register", MO, MONum);
 885       } else if (MRI->def_empty(Reg)) {
 886         report("Reading virtual register without a def", MO, MONum);
 887       } else {
 888         BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 889         // We don't know which virtual registers are live in, so only complain
 890         // if vreg was killed in this MBB. Otherwise keep track of vregs that
 891         // must be live in. PHI instructions are handled separately.
 892         if (MInfo.regsKilled.count(Reg))
 893           report("Using a killed virtual register", MO, MONum);
 894         else if (!MI->isPHI())
 895           MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
 896       }
 897     }
 898   }
 899
 900   if (MO->isDef()) {
 901     // Register defined.
 902     // TODO: verify that earlyclobber ops are not used.
 903     if (MO->isDead())
 904       addRegWithSubRegs(regsDead, Reg);
 905     else
 906       addRegWithSubRegs(regsDefined, Reg);
 907
 908     // Verify SSA form.
 909     if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
 910         llvm::next(MRI->def_begin(Reg)) != MRI->def_end())
 911       report("Multiple virtual register defs in SSA form", MO, MONum);
 912
 913     // Check LiveInts for a live range, but only for virtual registers.
 914     if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
 915         !LiveInts->isNotInMIMap(MI)) {
 916       SlotIndex DefIdx = LiveInts->getInstructionIndex(MI);
 917       DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
 918       if (LiveInts->hasInterval(Reg)) {
 919         const LiveInterval &LI = LiveInts->getInterval(Reg);
 920         if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
 921           assert(VNI && "NULL valno is not allowed");
 922           if (VNI->def != DefIdx) {
 923             report("Inconsistent valno->def", MO, MONum);
 924             *OS << "Valno " << VNI->id << " is not defined at "
 925               << DefIdx << " in " << LI << '\n';
 926           }
 927         } else {
 928           report("No live range at def", MO, MONum);
 929           *OS << DefIdx << " is not live in " << LI << '\n';
 930         }
 931       } else {
 932         report("Virtual register has no Live interval", MO, MONum);
 933       }
 934     }
 935   }
 936 }
 937
 938 void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
 939 }
 940
 941 // This function gets called after visiting all instructions in a bundle. The
 942 // argument points to the bundle header.
 943 // Normal stand-alone instructions are also considered 'bundles', and this
 944 // function is called for all of them.
 945 void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
 946   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 947   set_union(MInfo.regsKilled, regsKilled);
 948   set_subtract(regsLive, regsKilled); regsKilled.clear();
 949   // Kill any masked registers.
 950   while (!regMasks.empty()) {
 951     const uint32_t *Mask = regMasks.pop_back_val();
 952     for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
 953       if (TargetRegisterInfo::isPhysicalRegister(*I) &&
 954           MachineOperand::clobbersPhysReg(Mask, *I))
 955         regsDead.push_back(*I);
 956   }
 957   set_subtract(regsLive, regsDead);   regsDead.clear();
 958   set_union(regsLive, regsDefined);   regsDefined.clear();
 959 }
 960
 961 void
 962 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
 963   MBBInfoMap[MBB].regsLiveOut = regsLive;
 964   regsLive.clear();
 965
 966   if (Indexes) {
 967     SlotIndex stop = Indexes->getMBBEndIdx(MBB);
 968     if (!(stop > lastIndex)) {
 969       report("Block ends before last instruction index", MBB);
 970       *OS << "Block ends at " << stop
 971           << " last instruction was at " << lastIndex << '\n';
 972     }
 973     lastIndex = stop;
 974   }
 975 }
 976
 977 // Calculate the largest possible vregsPassed sets. These are the registers that
 978 // can pass through an MBB live, but may not be live every time. It is assumed
 979 // that all vregsPassed sets are empty before the call.
 980 void MachineVerifier::calcRegsPassed() {
 981   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
 982   // have any vregsPassed.
 983   SmallPtrSet<const MachineBasicBlock*, 8> todo;
 984   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 985        MFI != MFE; ++MFI) {
 986     const MachineBasicBlock &MBB(*MFI);
 987     BBInfo &MInfo = MBBInfoMap[&MBB];
 988     if (!MInfo.reachable)
 989       continue;
 990     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
 991            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
 992       BBInfo &SInfo = MBBInfoMap[*SuI];
 993       if (SInfo.addPassed(MInfo.regsLiveOut))
 994         todo.insert(*SuI);
 995     }
 996   }
 997
 998   // Iteratively push vregsPassed to successors. This will converge to the same
 999   // final state regardless of DenseSet iteration order.
1000   while (!todo.empty()) {
1001     const MachineBasicBlock *MBB = *todo.begin();
1002     todo.erase(MBB);
1003     BBInfo &MInfo = MBBInfoMap[MBB];
1004     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
1005            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
1006       if (*SuI == MBB)
1007         continue;
1008       BBInfo &SInfo = MBBInfoMap[*SuI];
1009       if (SInfo.addPassed(MInfo.vregsPassed))
1010         todo.insert(*SuI);
1011     }
1012   }
1013 }
1014
1015 // Calculate the set of virtual registers that must be passed through each basic
1016 // block in order to satisfy the requirements of successor blocks. This is very
1017 // similar to calcRegsPassed, only backwards.
1018 void MachineVerifier::calcRegsRequired() {
1019   // First push live-in regs to predecessors' vregsRequired.
1020   SmallPtrSet<const MachineBasicBlock*, 8> todo;
1021   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1022        MFI != MFE; ++MFI) {
1023     const MachineBasicBlock &MBB(*MFI);
1024     BBInfo &MInfo = MBBInfoMap[&MBB];
1025     for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
1026            PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
1027       BBInfo &PInfo = MBBInfoMap[*PrI];
1028       if (PInfo.addRequired(MInfo.vregsLiveIn))
1029         todo.insert(*PrI);
1030     }
1031   }
1032
1033   // Iteratively push vregsRequired to predecessors. This will converge to the
1034   // same final state regardless of DenseSet iteration order.
1035   while (!todo.empty()) {
1036     const MachineBasicBlock *MBB = *todo.begin();
1037     todo.erase(MBB);
1038     BBInfo &MInfo = MBBInfoMap[MBB];
1039     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1040            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1041       if (*PrI == MBB)
1042         continue;
1043       BBInfo &SInfo = MBBInfoMap[*PrI];
1044       if (SInfo.addRequired(MInfo.vregsRequired))
1045         todo.insert(*PrI);
1046     }
1047   }
1048 }
1049
1050 // Check PHI instructions at the beginning of MBB. It is assumed that
1051 // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
1052 void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
1053   SmallPtrSet<const MachineBasicBlock*, 8> seen;
1054   for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
1055        BBI != BBE && BBI->isPHI(); ++BBI) {
1056     seen.clear();
1057
1058     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
1059       unsigned Reg = BBI->getOperand(i).getReg();
1060       const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
1061       if (!Pre->isSuccessor(MBB))
1062         continue;
1063       seen.insert(Pre);
1064       BBInfo &PrInfo = MBBInfoMap[Pre];
1065       if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
1066         report("PHI operand is not live-out from predecessor",
1067                &BBI->getOperand(i), i);
1068     }
1069
1070     // Did we see all predecessors?
1071     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1072            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1073       if (!seen.count(*PrI)) {
1074         report("Missing PHI operand", BBI);
1075         *OS << "BB#" << (*PrI)->getNumber()
1076             << " is a predecessor according to the CFG.\n";
1077       }
1078     }
1079   }
1080 }
1081
1082 void MachineVerifier::visitMachineFunctionAfter() {
1083   calcRegsPassed();
1084
1085   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1086        MFI != MFE; ++MFI) {
1087     BBInfo &MInfo = MBBInfoMap[MFI];
1088
1089     // Skip unreachable MBBs.
1090     if (!MInfo.reachable)
1091       continue;
1092
1093     checkPHIOps(MFI);
1094   }
1095
1096   // Now check liveness info if available
1097   calcRegsRequired();
1098
1099   // Check for killed virtual registers that should be live out.
1100   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1101        MFI != MFE; ++MFI) {
1102     BBInfo &MInfo = MBBInfoMap[MFI];
1103     for (RegSet::iterator
1104          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1105          ++I)
1106       if (MInfo.regsKilled.count(*I)) {
1107         report("Virtual register killed in block, but needed live out.", MFI);
1108         *OS << "Virtual register " << PrintReg(*I)
1109             << " is used after the block.\n";
1110       }
1111   }
1112
1113   if (!MF->empty()) {
1114     BBInfo &MInfo = MBBInfoMap[&MF->front()];
1115     for (RegSet::iterator
1116          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1117          ++I)
1118       report("Virtual register def doesn't dominate all uses.",
1119              MRI->getVRegDef(*I));
1120   }
1121
1122   if (LiveVars)
1123     verifyLiveVariables();
1124   if (LiveInts)
1125     verifyLiveIntervals();
1126 }
1127
1128 void MachineVerifier::verifyLiveVariables() {
1129   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
1130   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1131     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1132     LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1133     for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1134          MFI != MFE; ++MFI) {
1135       BBInfo &MInfo = MBBInfoMap[MFI];
1136
1137       // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1138       if (MInfo.vregsRequired.count(Reg)) {
1139         if (!VI.AliveBlocks.test(MFI->getNumber())) {
1140           report("LiveVariables: Block missing from AliveBlocks", MFI);
1141           *OS << "Virtual register " << PrintReg(Reg)
1142               << " must be live through the block.\n";
1143         }
1144       } else {
1145         if (VI.AliveBlocks.test(MFI->getNumber())) {
1146           report("LiveVariables: Block should not be in AliveBlocks", MFI);
1147           *OS << "Virtual register " << PrintReg(Reg)
1148               << " is not needed live through the block.\n";
1149         }
1150       }
1151     }
1152   }
1153 }
1154
1155 void MachineVerifier::verifyLiveIntervals() {
1156   assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
1157   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1158     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1159
1160     // Spilling and splitting may leave unused registers around. Skip them.
1161     if (MRI->reg_nodbg_empty(Reg))
1162       continue;
1163
1164     if (!LiveInts->hasInterval(Reg)) {
1165       report("Missing live interval for virtual register", MF);
1166       *OS << PrintReg(Reg, TRI) << " still has defs or uses\n";
1167       continue;
1168     }
1169
1170     const LiveInterval &LI = LiveInts->getInterval(Reg);
1171     assert(Reg == LI.reg && "Invalid reg to interval mapping");
1172     verifyLiveInterval(LI);
1173   }
1174
1175   // Verify all the cached regunit intervals.
1176   for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
1177     if (const LiveInterval *LI = LiveInts->getCachedRegUnit(i))
1178       verifyLiveInterval(*LI);
1179 }
1180
1181 void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI,
1182                                               VNInfo *VNI) {
1183   if (VNI->isUnused())
1184     return;
1185
1186   const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
1187
1188   if (!DefVNI) {
1189     report("Valno not live at def and not marked unused", MF, LI);
1190     *OS << "Valno #" << VNI->id << '\n';
1191     return;
1192   }
1193
1194   if (DefVNI != VNI) {
1195     report("Live range at def has different valno", MF, LI);
1196     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1197         << " where valno #" << DefVNI->id << " is live\n";
1198     return;
1199   }
1200
1201   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1202   if (!MBB) {
1203     report("Invalid definition index", MF, LI);
1204     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1205         << " in " << LI << '\n';
1206     return;
1207   }
1208
1209   if (VNI->isPHIDef()) {
1210     if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1211       report("PHIDef value is not defined at MBB start", MBB, LI);
1212       *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1213           << ", not at the beginning of BB#" << MBB->getNumber() << '\n';
1214     }
1215     return;
1216   }
1217
1218   // Non-PHI def.
1219   const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1220   if (!MI) {
1221     report("No instruction at def index", MBB, LI);
1222     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1223     return;
1224   }
1225
1226   bool hasDef = false;
1227   bool isEarlyClobber = false;
1228   for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1229     if (!MOI->isReg() || !MOI->isDef())
1230       continue;
1231     if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1232       if (MOI->getReg() != LI.reg)
1233         continue;
1234     } else {
1235       if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1236           !TRI->hasRegUnit(MOI->getReg(), LI.reg))
1237         continue;
1238     }
1239     hasDef = true;
1240     if (MOI->isEarlyClobber())
1241       isEarlyClobber = true;
1242   }
1243
1244   if (!hasDef) {
1245     report("Defining instruction does not modify register", MI);
1246     *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1247   }
1248
1249   // Early clobber defs begin at USE slots, but other defs must begin at
1250   // DEF slots.
1251   if (isEarlyClobber) {
1252     if (!VNI->def.isEarlyClobber()) {
1253       report("Early clobber def must be at an early-clobber slot", MBB, LI);
1254       *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1255     }
1256   } else if (!VNI->def.isRegister()) {
1257     report("Non-PHI, non-early clobber def must be at a register slot",
1258            MBB, LI);
1259     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1260   }
1261 }
1262
1263 void
1264 MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI,
1265                                            LiveInterval::const_iterator I) {
1266   const VNInfo *VNI = I->valno;
1267   assert(VNI && "Live range has no valno");
1268
1269   if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
1270     report("Foreign valno in live range", MF, LI);
1271     *OS << *I << " has a bad valno\n";
1272   }
1273
1274   if (VNI->isUnused()) {
1275     report("Live range valno is marked unused", MF, LI);
1276     *OS << *I << '\n';
1277   }
1278
1279   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
1280   if (!MBB) {
1281     report("Bad start of live segment, no basic block", MF, LI);
1282     *OS << *I << '\n';
1283     return;
1284   }
1285   SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1286   if (I->start != MBBStartIdx && I->start != VNI->def) {
1287     report("Live segment must begin at MBB entry or valno def", MBB, LI);
1288     *OS << *I << '\n';
1289   }
1290
1291   const MachineBasicBlock *EndMBB =
1292     LiveInts->getMBBFromIndex(I->end.getPrevSlot());
1293   if (!EndMBB) {
1294     report("Bad end of live segment, no basic block", MF, LI);
1295     *OS << *I << '\n';
1296     return;
1297   }
1298
1299   // No more checks for live-out segments.
1300   if (I->end == LiveInts->getMBBEndIdx(EndMBB))
1301     return;
1302
1303   // RegUnit intervals are allowed dead phis.
1304   if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && VNI->isPHIDef() &&
1305       I->start == VNI->def && I->end == VNI->def.getDeadSlot())
1306     return;
1307
1308   // The live segment is ending inside EndMBB
1309   const MachineInstr *MI =
1310     LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
1311   if (!MI) {
1312     report("Live segment doesn't end at a valid instruction", EndMBB, LI);
1313     *OS << *I << '\n';
1314     return;
1315   }
1316
1317   // The block slot must refer to a basic block boundary.
1318   if (I->end.isBlock()) {
1319     report("Live segment ends at B slot of an instruction", EndMBB, LI);
1320     *OS << *I << '\n';
1321   }
1322
1323   if (I->end.isDead()) {
1324     // Segment ends on the dead slot.
1325     // That means there must be a dead def.
1326     if (!SlotIndex::isSameInstr(I->start, I->end)) {
1327       report("Live segment ending at dead slot spans instructions", EndMBB, LI);
1328       *OS << *I << '\n';
1329     }
1330   }
1331
1332   // A live segment can only end at an early-clobber slot if it is being
1333   // redefined by an early-clobber def.
1334   if (I->end.isEarlyClobber()) {
1335     if (I+1 == LI.end() || (I+1)->start != I->end) {
1336       report("Live segment ending at early clobber slot must be "
1337              "redefined by an EC def in the same instruction", EndMBB, LI);
1338       *OS << *I << '\n';
1339     }
1340   }
1341
1342   // The following checks only apply to virtual registers. Physreg liveness
1343   // is too weird to check.
1344   if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1345     // A live range can end with either a redefinition, a kill flag on a
1346     // use, or a dead flag on a def.
1347     bool hasRead = false;
1348     bool hasDeadDef = false;
1349     for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1350       if (!MOI->isReg() || MOI->getReg() != LI.reg)
1351         continue;
1352       if (MOI->readsReg())
1353         hasRead = true;
1354       if (MOI->isDef() && MOI->isDead())
1355         hasDeadDef = true;
1356     }
1357
1358     if (I->end.isDead()) {
1359       if (!hasDeadDef) {
1360         report("Instruction doesn't have a dead def operand", MI);
1361         I->print(*OS);
1362         *OS << " in " << LI << '\n';
1363       }
1364     } else {
1365       if (!hasRead) {
1366         report("Instruction ending live range doesn't read the register", MI);
1367         *OS << *I << " in " << LI << '\n';
1368       }
1369     }
1370   }
1371
1372   // Now check all the basic blocks in this live segment.
1373   MachineFunction::const_iterator MFI = MBB;
1374   // Is this live range the beginning of a non-PHIDef VN?
1375   if (I->start == VNI->def && !VNI->isPHIDef()) {
1376     // Not live-in to any blocks.
1377     if (MBB == EndMBB)
1378       return;
1379     // Skip this block.
1380     ++MFI;
1381   }
1382   for (;;) {
1383     assert(LiveInts->isLiveInToMBB(LI, MFI));
1384     // We don't know how to track physregs into a landing pad.
1385     if (!TargetRegisterInfo::isVirtualRegister(LI.reg) &&
1386         MFI->isLandingPad()) {
1387       if (&*MFI == EndMBB)
1388         break;
1389       ++MFI;
1390       continue;
1391     }
1392
1393     // Is VNI a PHI-def in the current block?
1394     bool IsPHI = VNI->isPHIDef() &&
1395       VNI->def == LiveInts->getMBBStartIdx(MFI);
1396
1397     // Check that VNI is live-out of all predecessors.
1398     for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1399          PE = MFI->pred_end(); PI != PE; ++PI) {
1400       SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
1401       const VNInfo *PVNI = LI.getVNInfoBefore(PEnd);
1402
1403       // All predecessors must have a live-out value.
1404       if (!PVNI) {
1405         report("Register not marked live out of predecessor", *PI, LI);
1406         *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1407             << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
1408             << PEnd << '\n';
1409         continue;
1410       }
1411
1412       // Only PHI-defs can take different predecessor values.
1413       if (!IsPHI && PVNI != VNI) {
1414         report("Different value live out of predecessor", *PI, LI);
1415         *OS << "Valno #" << PVNI->id << " live out of BB#"
1416             << (*PI)->getNumber() << '@' << PEnd
1417             << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1418             << '@' << LiveInts->getMBBStartIdx(MFI) << '\n';
1419       }
1420     }
1421     if (&*MFI == EndMBB)
1422       break;
1423     ++MFI;
1424   }
1425 }
1426
1427 void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
1428   for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
1429        I!=E; ++I)
1430     verifyLiveIntervalValue(LI, *I);
1431
1432   for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I)
1433     verifyLiveIntervalSegment(LI, I);
1434
1435   // Check the LI only has one connected component.
1436   if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1437     ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1438     unsigned NumComp = ConEQ.Classify(&LI);
1439     if (NumComp > 1) {
1440       report("Multiple connected components in live interval", MF, LI);
1441       for (unsigned comp = 0; comp != NumComp; ++comp) {
1442         *OS << comp << ": valnos";
1443         for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1444              E = LI.vni_end(); I!=E; ++I)
1445           if (comp == ConEQ.getEqClass(*I))
1446             *OS << ' ' << (*I)->id;
1447         *OS << '\n';
1448       }
1449     }
1450   }
1451 }