lib/CodeGen/MachineVerifier.cpp

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