lib/CodeGen/MachineVerifier.cpp

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