contrib/llvm/lib/CodeGen/MachineVerifier.cpp

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