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