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
 236 MachineVerifier::report(const char *msg, const MachineFunction *MF)
 237 {
 238   assert(MF);
 239   *OS << "\n";
 240   if (!foundErrors++)
 241     MF->print(OS);
 242   *OS << "*** Bad machine code: " << msg << " ***\n"
 243       << "- function:    " << MF->getFunction()->getNameStr() << "\n";
 244 }
 245
 246 void
 247 MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB)
 248 {
 249   assert(MBB);
 250   report(msg, MBB->getParent());
 251   *OS << "- basic block: " << MBB->getBasicBlock()->getNameStr()
 252       << " " << (void*)MBB
 253       << " (#" << MBB->getNumber() << ")\n";
 254 }
 255
 256 void
 257 MachineVerifier::report(const char *msg, const MachineInstr *MI)
 258 {
 259   assert(MI);
 260   report(msg, MI->getParent());
 261   *OS << "- instruction: ";
 262   MI->print(OS, TM);
 263 }
 264
 265 void
 266 MachineVerifier::report(const char *msg,
 267                         const MachineOperand *MO, unsigned MONum)
 268 {
 269   assert(MO);
 270   report(msg, MO->getParent());
 271   *OS << "- operand " << MONum << ":   ";
 272   MO->print(*OS, TM);
 273   *OS << "\n";
 274 }
 275
 276 void
 277 MachineVerifier::markReachable(const MachineBasicBlock *MBB)
 278 {
 279   BBInfo &MInfo = MBBInfoMap[MBB];
 280   if (!MInfo.reachable) {
 281     MInfo.reachable = true;
 282     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
 283            SuE = MBB->succ_end(); SuI != SuE; ++SuI)
 284       markReachable(*SuI);
 285   }
 286 }
 287
 288 void
 289 MachineVerifier::visitMachineFunctionBefore()
 290 {
 291   regsReserved = TRI->getReservedRegs(*MF);
 292
 293   // A sub-register of a reserved register is also reserved
 294   for (int Reg = regsReserved.find_first(); Reg>=0;
 295        Reg = regsReserved.find_next(Reg)) {
 296     for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
 297       // FIXME: This should probably be:
 298       // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
 299       regsReserved.set(*Sub);
 300     }
 301   }
 302   markReachable(&MF->front());
 303 }
 304
 305 void
 306 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB)
 307 {
 308   regsLive.clear();
 309   for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
 310          E = MBB->livein_end(); I != E; ++I) {
 311     if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
 312       report("MBB live-in list contains non-physical register", MBB);
 313       continue;
 314     }
 315     regsLive.insert(*I);
 316     for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
 317       regsLive.insert(*R);
 318   }
 319   regsLiveInButUnused = regsLive;
 320
 321   const MachineFrameInfo *MFI = MF->getFrameInfo();
 322   assert(MFI && "Function has no frame info");
 323   BitVector PR = MFI->getPristineRegs(MBB);
 324   for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
 325     regsLive.insert(I);
 326     for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
 327       regsLive.insert(*R);
 328   }
 329
 330   regsKilled.clear();
 331   regsDefined.clear();
 332 }
 333
 334 void
 335 MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI)
 336 {
 337   const TargetInstrDesc &TI = MI->getDesc();
 338   if (MI->getNumExplicitOperands() < TI.getNumOperands()) {
 339     report("Too few operands", MI);
 340     *OS << TI.getNumOperands() << " operands expected, but "
 341         << MI->getNumExplicitOperands() << " given.\n";
 342   }
 343   if (!TI.isVariadic()) {
 344     if (MI->getNumExplicitOperands() > TI.getNumOperands()) {
 345       report("Too many operands", MI);
 346       *OS << TI.getNumOperands() << " operands expected, but "
 347           << MI->getNumExplicitOperands() << " given.\n";
 348     }
 349   }
 350 }
 351
 352 void
 353 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum)
 354 {
 355   const MachineInstr *MI = MO->getParent();
 356   const TargetInstrDesc &TI = MI->getDesc();
 357
 358   // The first TI.NumDefs operands must be explicit register defines
 359   if (MONum < TI.getNumDefs()) {
 360     if (!MO->isReg())
 361       report("Explicit definition must be a register", MO, MONum);
 362     else if (!MO->isDef())
 363       report("Explicit definition marked as use", MO, MONum);
 364     else if (MO->isImplicit())
 365       report("Explicit definition marked as implicit", MO, MONum);
 366   }
 367
 368   switch (MO->getType()) {
 369   case MachineOperand::MO_Register: {
 370     const unsigned Reg = MO->getReg();
 371     if (!Reg)
 372       return;
 373
 374     // Check Live Variables.
 375     if (MO->isUndef()) {
 376       // An <undef> doesn't refer to any register, so just skip it.
 377     } else if (MO->isUse()) {
 378       regsLiveInButUnused.erase(Reg);
 379
 380       if (MO->isKill()) {
 381         addRegWithSubRegs(regsKilled, Reg);
 382         // Tied operands on two-address instuctions MUST NOT have a <kill> flag.
 383         if (MI->isRegTiedToDefOperand(MONum))
 384             report("Illegal kill flag on two-address instruction operand",
 385                    MO, MONum);
 386       } else {
 387         // TwoAddress instr modifying a reg is treated as kill+def.
 388         unsigned defIdx;
 389         if (MI->isRegTiedToDefOperand(MONum, &defIdx) &&
 390             MI->getOperand(defIdx).getReg() == Reg)
 391           addRegWithSubRegs(regsKilled, Reg);
 392       }
 393       // Use of a dead register.
 394       if (!regsLive.count(Reg)) {
 395         if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 396           // Reserved registers may be used even when 'dead'.
 397           if (!isReserved(Reg))
 398             report("Using an undefined physical register", MO, MONum);
 399         } else {
 400           BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 401           // We don't know which virtual registers are live in, so only complain
 402           // if vreg was killed in this MBB. Otherwise keep track of vregs that
 403           // must be live in. PHI instructions are handled separately.
 404           if (MInfo.regsKilled.count(Reg))
 405             report("Using a killed virtual register", MO, MONum);
 406           else if (MI->getOpcode() != TargetInstrInfo::PHI)
 407             MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
 408         }
 409       }
 410     } else {
 411       assert(MO->isDef());
 412       // Register defined.
 413       // TODO: verify that earlyclobber ops are not used.
 414       if (MO->isDead())
 415         addRegWithSubRegs(regsDead, Reg);
 416       else
 417         addRegWithSubRegs(regsDefined, Reg);
 418     }
 419
 420     // Check register classes.
 421     if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
 422       const TargetOperandInfo &TOI = TI.OpInfo[MONum];
 423       unsigned SubIdx = MO->getSubReg();
 424
 425       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 426         unsigned sr = Reg;
 427         if (SubIdx) {
 428           unsigned s = TRI->getSubReg(Reg, SubIdx);
 429           if (!s) {
 430             report("Invalid subregister index for physical register",
 431                    MO, MONum);
 432             return;
 433           }
 434           sr = s;
 435         }
 436         if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
 437           if (!DRC->contains(sr)) {
 438             report("Illegal physical register for instruction", MO, MONum);
 439             *OS << TRI->getName(sr) << " is not a "
 440                 << DRC->getName() << " register.\n";
 441           }
 442         }
 443       } else {
 444         // Virtual register.
 445         const TargetRegisterClass *RC = MRI->getRegClass(Reg);
 446         if (SubIdx) {
 447           if (RC->subregclasses_begin()+SubIdx >= RC->subregclasses_end()) {
 448             report("Invalid subregister index for virtual register", MO, MONum);
 449             return;
 450           }
 451           RC = *(RC->subregclasses_begin()+SubIdx);
 452         }
 453         if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
 454           if (RC != DRC && !RC->hasSuperClass(DRC)) {
 455             report("Illegal virtual register for instruction", MO, MONum);
 456             *OS << "Expected a " << DRC->getName() << " register, but got a "
 457                 << RC->getName() << " register\n";
 458           }
 459         }
 460       }
 461     }
 462     break;
 463   }
 464     // Can PHI instrs refer to MBBs not in the CFG? X86 and ARM do.
 465     // case MachineOperand::MO_MachineBasicBlock:
 466     //   if (MI->getOpcode() == TargetInstrInfo::PHI) {
 467     //     if (!MO->getMBB()->isSuccessor(MI->getParent()))
 468     //       report("PHI operand is not in the CFG", MO, MONum);
 469     //   }
 470     //   break;
 471   default:
 472     break;
 473   }
 474 }
 475
 476 void
 477 MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI)
 478 {
 479   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
 480   set_union(MInfo.regsKilled, regsKilled);
 481   set_subtract(regsLive, regsKilled);
 482   regsKilled.clear();
 483
 484   // Verify that both <def> and <def,dead> operands refer to dead registers.
 485   RegVector defs(regsDefined);
 486   defs.append(regsDead.begin(), regsDead.end());
 487
 488   for (RegVector::const_iterator I = defs.begin(), E = defs.end();
 489        I != E; ++I) {
 490     if (regsLive.count(*I)) {
 491       if (TargetRegisterInfo::isPhysicalRegister(*I)) {
 492         if (!allowPhysDoubleDefs && !isReserved(*I) &&
 493             !regsLiveInButUnused.count(*I)) {
 494           report("Redefining a live physical register", MI);
 495           *OS << "Register " << TRI->getName(*I)
 496               << " was defined but already live.\n";
 497         }
 498       } else {
 499         if (!allowVirtDoubleDefs) {
 500           report("Redefining a live virtual register", MI);
 501           *OS << "Virtual register %reg" << *I
 502               << " was defined but already live.\n";
 503         }
 504       }
 505     } else if (TargetRegisterInfo::isVirtualRegister(*I) &&
 506                !MInfo.regsKilled.count(*I)) {
 507       // Virtual register defined without being killed first must be dead on
 508       // entry.
 509       MInfo.vregsDeadIn.insert(std::make_pair(*I, MI));
 510     }
 511   }
 512
 513   set_subtract(regsLive, regsDead); regsDead.clear();
 514   set_union(regsLive, regsDefined); regsDefined.clear();
 515 }
 516
 517 void
 518 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB)
 519 {
 520   MBBInfoMap[MBB].regsLiveOut = regsLive;
 521   regsLive.clear();
 522 }
 523
 524 // Calculate the largest possible vregsPassed sets. These are the registers that
 525 // can pass through an MBB live, but may not be live every time. It is assumed
 526 // that all vregsPassed sets are empty before the call.
 527 void
 528 MachineVerifier::calcMaxRegsPassed()
 529 {
 530   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
 531   // have any vregsPassed.
 532   DenseSet<const MachineBasicBlock*> todo;
 533   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 534        MFI != MFE; ++MFI) {
 535     const MachineBasicBlock &MBB(*MFI);
 536     BBInfo &MInfo = MBBInfoMap[&MBB];
 537     if (!MInfo.reachable)
 538       continue;
 539     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
 540            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
 541       BBInfo &SInfo = MBBInfoMap[*SuI];
 542       if (SInfo.addPassed(MInfo.regsLiveOut))
 543         todo.insert(*SuI);
 544     }
 545   }
 546
 547   // Iteratively push vregsPassed to successors. This will converge to the same
 548   // final state regardless of DenseSet iteration order.
 549   while (!todo.empty()) {
 550     const MachineBasicBlock *MBB = *todo.begin();
 551     todo.erase(MBB);
 552     BBInfo &MInfo = MBBInfoMap[MBB];
 553     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
 554            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
 555       if (*SuI == MBB)
 556         continue;
 557       BBInfo &SInfo = MBBInfoMap[*SuI];
 558       if (SInfo.addPassed(MInfo.vregsPassed))
 559         todo.insert(*SuI);
 560     }
 561   }
 562 }
 563
 564 // Calculate the minimum vregsPassed set. These are the registers that always
 565 // pass live through an MBB. The calculation assumes that calcMaxRegsPassed has
 566 // been called earlier.
 567 void
 568 MachineVerifier::calcMinRegsPassed()
 569 {
 570   DenseSet<const MachineBasicBlock*> todo;
 571   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 572        MFI != MFE; ++MFI)
 573     todo.insert(MFI);
 574
 575   while (!todo.empty()) {
 576     const MachineBasicBlock *MBB = *todo.begin();
 577     todo.erase(MBB);
 578     BBInfo &MInfo = MBBInfoMap[MBB];
 579
 580     // Remove entries from vRegsPassed that are not live out from all
 581     // reachable predecessors.
 582     RegSet dead;
 583     for (RegSet::iterator I = MInfo.vregsPassed.begin(),
 584            E = MInfo.vregsPassed.end(); I != E; ++I) {
 585       for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
 586              PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
 587         BBInfo &PrInfo = MBBInfoMap[*PrI];
 588         if (PrInfo.reachable && !PrInfo.isLiveOut(*I)) {
 589           dead.insert(*I);
 590           break;
 591         }
 592       }
 593     }
 594     // If any regs removed, we need to recheck successors.
 595     if (!dead.empty()) {
 596       set_subtract(MInfo.vregsPassed, dead);
 597       todo.insert(MBB->succ_begin(), MBB->succ_end());
 598     }
 599   }
 600 }
 601
 602 // Check PHI instructions at the beginning of MBB. It is assumed that
 603 // calcMinRegsPassed has been run so BBInfo::isLiveOut is valid.
 604 void
 605 MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB)
 606 {
 607   for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
 608        BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
 609     DenseSet<const MachineBasicBlock*> seen;
 610
 611     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
 612       unsigned Reg = BBI->getOperand(i).getReg();
 613       const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
 614       if (!Pre->isSuccessor(MBB))
 615         continue;
 616       seen.insert(Pre);
 617       BBInfo &PrInfo = MBBInfoMap[Pre];
 618       if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
 619         report("PHI operand is not live-out from predecessor",
 620                &BBI->getOperand(i), i);
 621     }
 622
 623     // Did we see all predecessors?
 624     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
 625            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
 626       if (!seen.count(*PrI)) {
 627         report("Missing PHI operand", BBI);
 628         *OS << "MBB #" << (*PrI)->getNumber()
 629             << " is a predecessor according to the CFG.\n";
 630       }
 631     }
 632   }
 633 }
 634
 635 void
 636 MachineVerifier::visitMachineFunctionAfter()
 637 {
 638   calcMaxRegsPassed();
 639
 640   // With the maximal set of vregsPassed we can verify dead-in registers.
 641   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 642        MFI != MFE; ++MFI) {
 643     BBInfo &MInfo = MBBInfoMap[MFI];
 644
 645     // Skip unreachable MBBs.
 646     if (!MInfo.reachable)
 647       continue;
 648
 649     for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
 650            PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
 651       BBInfo &PrInfo = MBBInfoMap[*PrI];
 652       if (!PrInfo.reachable)
 653         continue;
 654
 655       // Verify physical live-ins. EH landing pads have magic live-ins so we
 656       // ignore them.
 657       if (!MFI->isLandingPad()) {
 658         for (MachineBasicBlock::const_livein_iterator I = MFI->livein_begin(),
 659                E = MFI->livein_end(); I != E; ++I) {
 660           if (TargetRegisterInfo::isPhysicalRegister(*I) &&
 661               !isReserved (*I) && !PrInfo.isLiveOut(*I)) {
 662             report("Live-in physical register is not live-out from predecessor",
 663                    MFI);
 664             *OS << "Register " << TRI->getName(*I)
 665                 << " is not live-out from MBB #" << (*PrI)->getNumber()
 666                 << ".\n";
 667           }
 668         }
 669       }
 670
 671
 672       // Verify dead-in virtual registers.
 673       if (!allowVirtDoubleDefs) {
 674         for (RegMap::iterator I = MInfo.vregsDeadIn.begin(),
 675                E = MInfo.vregsDeadIn.end(); I != E; ++I) {
 676           // DeadIn register must be in neither regsLiveOut or vregsPassed of
 677           // any predecessor.
 678           if (PrInfo.isLiveOut(I->first)) {
 679             report("Live-in virtual register redefined", I->second);
 680             *OS << "Register %reg" << I->first
 681                 << " was live-out from predecessor MBB #"
 682                 << (*PrI)->getNumber() << ".\n";
 683           }
 684         }
 685       }
 686     }
 687   }
 688
 689   calcMinRegsPassed();
 690
 691   // With the minimal set of vregsPassed we can verify live-in virtual
 692   // registers, including PHI instructions.
 693   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 694        MFI != MFE; ++MFI) {
 695     BBInfo &MInfo = MBBInfoMap[MFI];
 696
 697     // Skip unreachable MBBs.
 698     if (!MInfo.reachable)
 699       continue;
 700
 701     checkPHIOps(MFI);
 702
 703     for (MachineBasicBlock::const_pred_iterator PrI = MFI->pred_begin(),
 704            PrE = MFI->pred_end(); PrI != PrE; ++PrI) {
 705       BBInfo &PrInfo = MBBInfoMap[*PrI];
 706       if (!PrInfo.reachable)
 707         continue;
 708
 709       for (RegMap::iterator I = MInfo.vregsLiveIn.begin(),
 710              E = MInfo.vregsLiveIn.end(); I != E; ++I) {
 711         if (!PrInfo.isLiveOut(I->first)) {
 712           report("Used virtual register is not live-in", I->second);
 713           *OS << "Register %reg" << I->first
 714               << " is not live-out from predecessor MBB #"
 715               << (*PrI)->getNumber()
 716               << ".\n";
 717         }
 718       }
 719     }
 720   }
 721 }