lib/CodeGen/MachineVerifier.cpp

   1 //===-- MachineVerifier.cpp - Machine Code Verifier -------------*- C++ -*-===//
   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/ADT/DenseSet.h"
  27 #include "llvm/ADT/SetOperations.h"
  28 #include "llvm/ADT/SmallVector.h"
  29 #include "llvm/Function.h"
  30 #include "llvm/CodeGen/LiveVariables.h"
  31 #include "llvm/CodeGen/MachineFunctionPass.h"
  32 #include "llvm/CodeGen/MachineRegisterInfo.h"
  33 #include "llvm/CodeGen/Passes.h"
  34 #include "llvm/Target/TargetMachine.h"
  35 #include "llvm/Target/TargetRegisterInfo.h"
  36 #include "llvm/Target/TargetInstrInfo.h"
  37 #include "llvm/Support/Compiler.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/ErrorHandling.h"
  40 #include "llvm/Support/raw_ostream.h"
  41 #include <fstream>
  42
  43 using namespace llvm;
  44
  45 namespace {
  46   struct VISIBILITY_HIDDEN MachineVerifier : public MachineFunctionPass {
  47     static char ID; // Pass ID, replacement for typeid
  48
  49     MachineVerifier(bool allowDoubleDefs = false) :
  50       MachineFunctionPass(&ID),
  51       allowVirtDoubleDefs(allowDoubleDefs),
  52       allowPhysDoubleDefs(allowDoubleDefs),
  53       OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
  54         {}
  55
  56     void getAnalysisUsage(AnalysisUsage &AU) const {
  57       AU.setPreservesAll();
  58       MachineFunctionPass::getAnalysisUsage(AU);
  59     }
  60
  61     bool runOnMachineFunction(MachineFunction &MF);
  62
  63     const bool allowVirtDoubleDefs;
  64     const bool allowPhysDoubleDefs;
  65
  66     const char *const OutFileName;
  67     std::ostream *OS;
  68     const MachineFunction *MF;
  69     const TargetMachine *TM;
  70     const TargetRegisterInfo *TRI;
  71     const MachineRegisterInfo *MRI;
  72
  73     unsigned foundErrors;
  74
  75     typedef SmallVector<unsigned, 16> RegVector;
  76     typedef DenseSet<unsigned> RegSet;
  77     typedef DenseMap<unsigned, const MachineInstr*> RegMap;
  78
  79     BitVector regsReserved;
  80     RegSet regsLive;
  81     RegVector regsDefined, regsImpDefined, regsDead, regsKilled;
  82
  83     // Add Reg and any sub-registers to RV
  84     void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
  85       RV.push_back(Reg);
  86       if (TargetRegisterInfo::isPhysicalRegister(Reg))
  87         for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
  88           RV.push_back(*R);
  89     }
  90
  91     struct BBInfo {
  92       // Is this MBB reachable from the MF entry point?
  93       bool reachable;
  94
  95       // Vregs that must be live in because they are used without being
  96       // defined. Map value is the user.
  97       RegMap vregsLiveIn;
  98
  99       // Vregs that must be dead in because they are defined without being
 100       // killed first. Map value is the defining instruction.
 101       RegMap vregsDeadIn;
 102
 103       // Regs killed in MBB. They may be defined again, and will then be in both
 104       // regsKilled and regsLiveOut.
 105       RegSet regsKilled;
 106
 107       // Regs defined in MBB and live out. Note that vregs passing through may
 108       // be live out without being mentioned here.
 109       RegSet regsLiveOut;
 110
 111       // Vregs that pass through MBB untouched. This set is disjoint from
 112       // regsKilled and regsLiveOut.
 113       RegSet vregsPassed;
 114
 115       BBInfo() : reachable(false) {}
 116
 117       // Add register to vregsPassed if it belongs there. Return true if
 118       // anything changed.
 119       bool addPassed(unsigned Reg) {
 120         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 121           return false;
 122         if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
 123           return false;
 124         return vregsPassed.insert(Reg).second;
 125       }
 126
 127       // Same for a full set.
 128       bool addPassed(const RegSet &RS) {
 129         bool changed = false;
 130         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
 131           if (addPassed(*I))
 132             changed = true;
 133         return changed;
 134       }
 135
 136       // Live-out registers are either in regsLiveOut or vregsPassed.
 137       bool isLiveOut(unsigned Reg) const {
 138         return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
 139       }
 140     };
 141
 142     // Extra register info per MBB.
 143     DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
 144
 145     bool isReserved(unsigned Reg) {
 146       return Reg < regsReserved.size() && regsReserved.test(Reg);
 147     }
 148
 149     void visitMachineFunctionBefore();
 150     void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
 151     void visitMachineInstrBefore(const MachineInstr *MI);
 152     void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
 153     void visitMachineInstrAfter(const MachineInstr *MI);
 154     void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
 155     void visitMachineFunctionAfter();
 156
 157     void report(const char *msg, const MachineFunction *MF);
 158     void report(const char *msg, const MachineBasicBlock *MBB);
 159     void report(const char *msg, const MachineInstr *MI);
 160     void report(const char *msg, const MachineOperand *MO, unsigned MONum);
 161
 162     void markReachable(const MachineBasicBlock *MBB);
 163     void calcMaxRegsPassed();
 164     void calcMinRegsPassed();
 165     void checkPHIOps(const MachineBasicBlock *MBB);
 166   };
 167 }
 168
 169 char MachineVerifier::ID = 0;
 170 static RegisterPass<MachineVerifier>
 171 MachineVer("machineverifier", "Verify generated machine code");
 172 static const PassInfo *const MachineVerifyID = &MachineVer;
 173
 174 FunctionPass *
 175 llvm::createMachineVerifierPass(bool allowPhysDoubleDefs)
 176 {
 177   return new MachineVerifier(allowPhysDoubleDefs);
 178 }
 179
 180 bool
 181 MachineVerifier::runOnMachineFunction(MachineFunction &MF)
 182 {
 183   std::ofstream OutFile;
 184   if (OutFileName) {
 185     OutFile.open(OutFileName, std::ios::out | std::ios::app);
 186     OS = &OutFile;
 187   } else {
 188     OS = cerr.stream();
 189   }
 190
 191   foundErrors = 0;
 192
 193   this->MF = &MF;
 194   TM = &MF.getTarget();
 195   TRI = TM->getRegisterInfo();
 196   MRI = &MF.getRegInfo();
 197
 198   visitMachineFunctionBefore();
 199   for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
 200        MFI!=MFE; ++MFI) {
 201     visitMachineBasicBlockBefore(MFI);
 202     for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
 203            MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
 204       visitMachineInstrBefore(MBBI);
 205       for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
 206         visitMachineOperand(&MBBI->getOperand(I), I);
 207       visitMachineInstrAfter(MBBI);
 208     }
 209     visitMachineBasicBlockAfter(MFI);
 210   }
 211   visitMachineFunctionAfter();
 212
 213   if (OutFileName)
 214     OutFile.close();
 215   else if (foundErrors) {
 216     std::string msg;
 217     raw_string_ostream Msg(msg);
 218     Msg << "Found " << foundErrors << " machine code errors.";
 219     llvm_report_error(Msg.str());
 220   }
 221
 222   return false;                 // no changes
 223 }
 224
 225 void
 226 MachineVerifier::report(const char *msg, const MachineFunction *MF)
 227 {
 228   assert(MF);
 229   *OS << "\n";
 230   if (!foundErrors++)
 231     MF->print(OS);
 232   *OS << "*** Bad machine code: " << msg << " ***\n"
 233       << "- function:    " << MF->getFunction()->getNameStr() << "\n";
 234 }
 235
 236 void
 237 MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB)
 238 {
 239   assert(MBB);
 240   report(msg, MBB->getParent());
 241   *OS << "- basic block: " << MBB->getBasicBlock()->getNameStr()
 242       << " " << (void*)MBB
 243       << " (#" << MBB->getNumber() << ")\n";
 244 }
 245
 246 void
 247 MachineVerifier::report(const char *msg, const MachineInstr *MI)
 248 {
 249   assert(MI);
 250   report(msg, MI->getParent());
 251   *OS << "- instruction: ";
 252   MI->print(OS, TM);
 253 }
 254
 255 void
 256 MachineVerifier::report(const char *msg,
 257                         const MachineOperand *MO, unsigned MONum)
 258 {
 259   assert(MO);
 260   report(msg, MO->getParent());
 261   *OS << "- operand " << MONum << ":   ";
 262   MO->print(*OS, TM);
 263   *OS << "\n";
 264 }
 265
 266 void
 267 MachineVerifier::markReachable(const MachineBasicBlock *MBB)
 268 {
 269   BBInfo &MInfo = MBBInfoMap[MBB];
 270   if (!MInfo.reachable) {
 271     MInfo.reachable = true;
 272     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
 273            SuE = MBB->succ_end(); SuI != SuE; ++SuI)
 274       markReachable(*SuI);
 275   }
 276 }
 277
 278 void
 279 MachineVerifier::visitMachineFunctionBefore()
 280 {
 281   regsReserved = TRI->getReservedRegs(*MF);
 282
 283   // A sub-register of a reserved register is also reserved
 284   for (int Reg = regsReserved.find_first(); Reg>=0;
 285        Reg = regsReserved.find_next(Reg)) {
 286     for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
 287       // FIXME: This should probably be:
 288       // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
 289       regsReserved.set(*Sub);
 290     }
 291   }
 292   markReachable(&MF->front());
 293 }
 294
 295 void
 296 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB)
 297 {
 298   regsLive.clear();
 299   for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
 300          E = MBB->livein_end(); I != E; ++I) {
 301     if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
 302       report("MBB live-in list contains non-physical register", MBB);
 303       continue;
 304     }
 305     regsLive.insert(*I);
 306     for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
 307       regsLive.insert(*R);
 308   }
 309   regsKilled.clear();
 310   regsDefined.clear();
 311   regsImpDefined.clear();
 312 }
 313
 314 void
 315 MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI)
 316 {
 317   const TargetInstrDesc &TI = MI->getDesc();
 318   if (MI->getNumExplicitOperands() < TI.getNumOperands()) {
 319     report("Too few operands", MI);
 320     *OS << TI.getNumOperands() << " operands expected, but "
 321         << MI->getNumExplicitOperands() << " given.\n";
 322   }
 323   if (!TI.isVariadic()) {
 324     if (MI->getNumExplicitOperands() > TI.getNumOperands()) {
 325       report("Too many operands", MI);
 326       *OS << TI.getNumOperands() << " operands expected, but "
 327           << MI->getNumExplicitOperands() << " given.\n";
 328     }
 329   }
 330 }
 331
 332 void
 333 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum)
 334 {
 335   const MachineInstr *MI = MO->getParent();
 336   const TargetInstrDesc &TI = MI->getDesc();
 337
 338   // The first TI.NumDefs operands must be explicit register defines
 339   if (MONum < TI.getNumDefs()) {
 340     if (!MO->isReg())
 341       report("Explicit definition must be a register", MO, MONum);
 342     else if (!MO->isDef())
 343       report("Explicit definition marked as use", MO, MONum);
 344     else if (MO->isImplicit())
 345       report("Explicit definition marked as implicit", MO, MONum);
 346   }
 347
 348   switch (MO->getType()) {
 349   case MachineOperand::MO_Register: {
 350     const unsigned Reg = MO->getReg();
 351     if (!Reg)
 352       return;
 353
 354     // Check Live Variables.
 355     if (MO->isUse()) {
 356       if (MO->isKill()) {
 357         addRegWithSubRegs(regsKilled, Reg);
 358         // Tied operands on two-address instuctions MUST NOT have a <kill> flag.
 359         if (MI->isRegTiedToDefOperand(MONum))
 360             report("Illegal kill flag on two-address instruction operand",
 361                    MO, MONum);
 362       } else {
 363         // TwoAddress instr modifying a reg is treated as kill+def.
 364         unsigned defIdx;
 365         if (MI->isRegTiedToDefOperand(MONum, &defIdx) &&
 366             MI->getOperand(defIdx).getReg() == Reg)
 367           addRegWithSubRegs(regsKilled, Reg);
 368       }
 369       // Use of a dead register. A register use marked <undef> is OK.
 370       if (!MO->isUndef() && !regsLive.count(Reg)) {
 371         if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 372           // Reserved registers may be used even when 'dead'.
 373           if (!isReserved(Reg))
 374             report("Using an undefined physical register", MO, MONum);
 375         } else {
 376           BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 377           // We don't know which virtual registers are live in, so only complain
 378           // if vreg was killed in this MBB. Otherwise keep track of vregs that
 379           // must be live in. PHI instructions are handled separately.
 380           if (MInfo.regsKilled.count(Reg))
 381             report("Using a killed virtual register", MO, MONum);
 382           else if (MI->getOpcode() != TargetInstrInfo::PHI)
 383             MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
 384         }
 385       }
 386     } else {
 387       // Register defined.
 388       // TODO: verify that earlyclobber ops are not used.
 389       addRegWithSubRegs(regsDefined, Reg);
 390
 391       if (MO->isDead())
 392         addRegWithSubRegs(regsDead, Reg);
 393     }
 394
 395     // Check register classes.
 396     if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
 397       const TargetOperandInfo &TOI = TI.OpInfo[MONum];
 398       unsigned SubIdx = MO->getSubReg();
 399
 400       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 401         unsigned sr = Reg;
 402         if (SubIdx) {
 403           unsigned s = TRI->getSubReg(Reg, SubIdx);
 404           if (!s) {
 405             report("Invalid subregister index for physical register",
 406                    MO, MONum);
 407             return;
 408           }
 409           sr = s;
 410         }
 411         if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
 412           if (!DRC->contains(sr)) {
 413             report("Illegal physical register for instruction", MO, MONum);
 414             *OS << TRI->getName(sr) << " is not a "
 415                 << DRC->getName() << " register.\n";
 416           }
 417         }
 418       } else {
 419         // Virtual register.
 420         const TargetRegisterClass *RC = MRI->getRegClass(Reg);
 421         if (SubIdx) {
 422           if (RC->subregclasses_begin()+SubIdx >= RC->subregclasses_end()) {
 423             report("Invalid subregister index for virtual register", MO, MONum);
 424             return;
 425           }
 426           RC = *(RC->subregclasses_begin()+SubIdx);
 427         }
 428         if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
 429           if (RC != DRC && !RC->hasSuperClass(DRC)) {
 430             report("Illegal virtual register for instruction", MO, MONum);
 431             *OS << "Expected a " << DRC->getName() << " register, but got a "
 432                 << RC->getName() << " register\n";
 433           }
 434         }
 435       }
 436     }
 437     break;
 438   }
 439     // Can PHI instrs refer to MBBs not in the CFG? X86 and ARM do.
 440     // case MachineOperand::MO_MachineBasicBlock:
 441     //   if (MI->getOpcode() == TargetInstrInfo::PHI) {
 442     //     if (!MO->getMBB()->isSuccessor(MI->getParent()))
 443     //       report("PHI operand is not in the CFG", MO, MONum);
 444     //   }
 445     //   break;
 446   default:
 447     break;
 448   }
 449 }
 450
 451 void
 452 MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI)
 453 {
 454   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 455   set_union(MInfo.regsKilled, regsKilled);
 456   set_subtract(regsLive, regsKilled);
 457   regsKilled.clear();
 458
 459   for (RegVector::const_iterator I = regsDefined.begin(),
 460          E = regsDefined.end(); I != E; ++I) {
 461     if (regsLive.count(*I)) {
 462       if (TargetRegisterInfo::isPhysicalRegister(*I)) {
 463         if (!allowPhysDoubleDefs && !isReserved(*I)) {
 464           report("Redefining a live physical register", MI);
 465           *OS << "Register " << TRI->getName(*I)
 466               << " was defined but already live.\n";
 467         }
 468       } else {
 469         if (!allowVirtDoubleDefs) {
 470           report("Redefining a live virtual register", MI);
 471           *OS << "Virtual register %reg" << *I
 472               << " was defined but already live.\n";
 473         }
 474       }
 475     } else if (TargetRegisterInfo::isVirtualRegister(*I) &&
 476                !MInfo.regsKilled.count(*I)) {
 477       // Virtual register defined without being killed first must be dead on
 478       // entry.
 479       MInfo.vregsDeadIn.insert(std::make_pair(*I, MI));
 480     }
 481   }
 482
 483   set_union(regsLive, regsDefined); regsDefined.clear();
 484   set_union(regsLive, regsImpDefined); regsImpDefined.clear();
 485   set_subtract(regsLive, regsDead); regsDead.clear();
 486 }
 487
 488 void
 489 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB)
 490 {
 491   MBBInfoMap[MBB].regsLiveOut = regsLive;
 492   regsLive.clear();
 493 }
 494
 495 // Calculate the largest possible vregsPassed sets. These are the registers that
 496 // can pass through an MBB live, but may not be live every time. It is assumed
 497 // that all vregsPassed sets are empty before the call.
 498 void
 499 MachineVerifier::calcMaxRegsPassed()
 500 {
 501   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
 502   // have any vregsPassed.
 503   DenseSet<const MachineBasicBlock*> todo;
 504   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 505        MFI != MFE; ++MFI) {
 506     const MachineBasicBlock &MBB(*MFI);
 507     BBInfo &MInfo = MBBInfoMap[&MBB];
 508     if (!MInfo.reachable)
 509       continue;
 510     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
 511            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
 512       BBInfo &SInfo = MBBInfoMap[*SuI];
 513       if (SInfo.addPassed(MInfo.regsLiveOut))
 514         todo.insert(*SuI);
 515     }
 516   }
 517
 518   // Iteratively push vregsPassed to successors. This will converge to the same
 519   // final state regardless of DenseSet iteration order.
 520   while (!todo.empty()) {
 521     const MachineBasicBlock *MBB = *todo.begin();
 522     todo.erase(MBB);
 523     BBInfo &MInfo = MBBInfoMap[MBB];
 524     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
 525            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
 526       if (*SuI == MBB)
 527         continue;
 528       BBInfo &SInfo = MBBInfoMap[*SuI];
 529       if (SInfo.addPassed(MInfo.vregsPassed))
 530         todo.insert(*SuI);
 531     }
 532   }
 533 }
 534
 535 // Calculate the minimum vregsPassed set. These are the registers that always
 536 // pass live through an MBB. The calculation assumes that calcMaxRegsPassed has
 537 // been called earlier.
 538 void
 539 MachineVerifier::calcMinRegsPassed()
 540 {
 541   DenseSet<const MachineBasicBlock*> todo;
 542   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 543        MFI != MFE; ++MFI)
 544     todo.insert(MFI);
 545
 546   while (!todo.empty()) {
 547     const MachineBasicBlock *MBB = *todo.begin();
 548     todo.erase(MBB);
 549     BBInfo &MInfo = MBBInfoMap[MBB];
 550
 551     // Remove entries from vRegsPassed that are not live out from all
 552     // reachable predecessors.
 553     RegSet dead;
 554     for (RegSet::iterator I = MInfo.vregsPassed.begin(),
 555            E = MInfo.vregsPassed.end(); I != E; ++I) {
 556       for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
 557              PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
 558         BBInfo &PrInfo = MBBInfoMap[*PrI];
 559         if (PrInfo.reachable && !PrInfo.isLiveOut(*I)) {
 560           dead.insert(*I);
 561           break;
 562         }
 563       }
 564     }
 565     // If any regs removed, we need to recheck successors.
 566     if (!dead.empty()) {
 567       set_subtract(MInfo.vregsPassed, dead);
 568       todo.insert(MBB->succ_begin(), MBB->succ_end());
 569     }
 570   }
 571 }
 572
 573 // Check PHI instructions at the beginning of MBB. It is assumed that
 574 // calcMinRegsPassed has been run so BBInfo::isLiveOut is valid.
 575 void
 576 MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB)
 577 {
 578   for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
 579        BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
 580     DenseSet<const MachineBasicBlock*> seen;
 581
 582     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
 583       unsigned Reg = BBI->getOperand(i).getReg();
 584       const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
 585       if (!Pre->isSuccessor(MBB))
 586         continue;
 587       seen.insert(Pre);
 588       BBInfo &PrInfo = MBBInfoMap[Pre];
 589       if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
 590         report("PHI operand is not live-out from predecessor",
 591                &BBI->getOperand(i), i);
 592     }
 593
 594     // Did we see all predecessors?
 595     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
 596            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
 597       if (!seen.count(*PrI)) {
 598         report("Missing PHI operand", BBI);
 599         *OS << "MBB #" << (*PrI)->getNumber()
 600             << " is a predecessor according to the CFG.\n";
 601       }
 602     }
 603   }
 604 }
 605
 606 void
 607 MachineVerifier::visitMachineFunctionAfter()
 608 {
 609   calcMaxRegsPassed();
 610
 611   // With the maximal set of vregsPassed we can verify dead-in registers.
 612   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 613        MFI != MFE; ++MFI) {
 614     BBInfo &MInfo = MBBInfoMap[MFI];
 615
 616     // Skip unreachable MBBs.
 617     if (!MInfo.reachable)
 618       continue;
 619
 620     for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
 621            PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
 622       BBInfo &PrInfo = MBBInfoMap[*PrI];
 623       if (!PrInfo.reachable)
 624         continue;
 625
 626       // Verify physical live-ins. EH landing pads have magic live-ins so we
 627       // ignore them.
 628       if (!MFI->isLandingPad()) {
 629         for (MachineBasicBlock::const_livein_iterator I = MFI->livein_begin(),
 630                E = MFI->livein_end(); I != E; ++I) {
 631           if (TargetRegisterInfo::isPhysicalRegister(*I) &&
 632               !isReserved (*I) && !PrInfo.isLiveOut(*I)) {
 633             report("Live-in physical register is not live-out from predecessor",
 634                    MFI);
 635             *OS << "Register " << TRI->getName(*I)
 636                 << " is not live-out from MBB #" << (*PrI)->getNumber()
 637                 << ".\n";
 638           }
 639         }
 640       }
 641
 642
 643       // Verify dead-in virtual registers.
 644       if (!allowVirtDoubleDefs) {
 645         for (RegMap::iterator I = MInfo.vregsDeadIn.begin(),
 646                E = MInfo.vregsDeadIn.end(); I != E; ++I) {
 647           // DeadIn register must be in neither regsLiveOut or vregsPassed of
 648           // any predecessor.
 649           if (PrInfo.isLiveOut(I->first)) {
 650             report("Live-in virtual register redefined", I->second);
 651             *OS << "Register %reg" << I->first
 652                 << " was live-out from predecessor MBB #"
 653                 << (*PrI)->getNumber() << ".\n";
 654           }
 655         }
 656       }
 657     }
 658   }
 659
 660   calcMinRegsPassed();
 661
 662   // With the minimal set of vregsPassed we can verify live-in virtual
 663   // registers, including PHI instructions.
 664   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 665        MFI != MFE; ++MFI) {
 666     BBInfo &MInfo = MBBInfoMap[MFI];
 667
 668     // Skip unreachable MBBs.
 669     if (!MInfo.reachable)
 670       continue;
 671
 672     checkPHIOps(MFI);
 673
 674     for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
 675            PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
 676       BBInfo &PrInfo = MBBInfoMap[*PrI];
 677       if (!PrInfo.reachable)
 678         continue;
 679
 680       for (RegMap::iterator I = MInfo.vregsLiveIn.begin(),
 681              E = MInfo.vregsLiveIn.end(); I != E; ++I) {
 682         if (!PrInfo.isLiveOut(I->first)) {
 683           report("Used virtual register is not live-in", I->second);
 684           *OS << "Register %reg" << I->first
 685               << " is not live-out from predecessor MBB #"
 686               << (*PrI)->getNumber()
 687               << ".\n";
 688         }
 689       }
 690     }
 691   }
 692 }