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