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"
48using namespace llvm;
49
50namespace {
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
254char MachineVerifierPass::ID = 0;
255INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
256                "Verify generated machine code", false, false)
257
258FunctionPass *llvm::createMachineVerifierPass(const char *Banner) {
259  return new MachineVerifierPass(Banner);
260}
261
262void MachineFunction::verify(Pass *p, const char *Banner) const {
263  MachineVerifier(p, Banner)
264    .runOnMachineFunction(const_cast<MachineFunction&>(*this));
265}
266
267bool 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
370void 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
382void 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
394void 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
403void 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
412void 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
423void 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
434void 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
444void 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
477// Does iterator point to a and b as the first two elements?
478static bool matchPair(MachineBasicBlock::const_succ_iterator i,
479                      const MachineBasicBlock *a, const MachineBasicBlock *b) {
480  if (*i == a)
481    return *++i == b;
482  if (*i == b)
483    return *++i == a;
484  return false;
485}
486
487void
488MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
489  FirstTerminator = 0;
490
491  if (MRI->isSSA()) {
492    // If this block has allocatable physical registers live-in, check that
493    // it is an entry block or landing pad.
494    for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
495           LE = MBB->livein_end();
496         LI != LE; ++LI) {
497      unsigned reg = *LI;
498      if (isAllocatable(reg) && !MBB->isLandingPad() &&
499          MBB != MBB->getParent()->begin()) {
500        report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB);
501      }
502    }
503  }
504
505  // Count the number of landing pad successors.
506  SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
507  for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
508       E = MBB->succ_end(); I != E; ++I) {
509    if ((*I)->isLandingPad())
510      LandingPadSuccs.insert(*I);
511    if (!FunctionBlocks.count(*I))
512      report("MBB has successor that isn't part of the function.", MBB);
513    if (!MBBInfoMap[*I].Preds.count(MBB)) {
514      report("Inconsistent CFG", MBB);
515      *OS << "MBB is not in the predecessor list of the successor BB#"
516          << (*I)->getNumber() << ".\n";
517    }
518  }
519
520  // Check the predecessor list.
521  for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
522       E = MBB->pred_end(); I != E; ++I) {
523    if (!FunctionBlocks.count(*I))
524      report("MBB has predecessor that isn't part of the function.", MBB);
525    if (!MBBInfoMap[*I].Succs.count(MBB)) {
526      report("Inconsistent CFG", MBB);
527      *OS << "MBB is not in the successor list of the predecessor BB#"
528          << (*I)->getNumber() << ".\n";
529    }
530  }
531
532  const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
533  const BasicBlock *BB = MBB->getBasicBlock();
534  if (LandingPadSuccs.size() > 1 &&
535      !(AsmInfo &&
536        AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
537        BB && isa<SwitchInst>(BB->getTerminator())))
538    report("MBB has more than one landing pad successor", MBB);
539
540  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
541  MachineBasicBlock *TBB = 0, *FBB = 0;
542  SmallVector<MachineOperand, 4> Cond;
543  if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
544                          TBB, FBB, Cond)) {
545    // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
546    // check whether its answers match up with reality.
547    if (!TBB && !FBB) {
548      // Block falls through to its successor.
549      MachineFunction::const_iterator MBBI = MBB;
550      ++MBBI;
551      if (MBBI == MF->end()) {
552        // It's possible that the block legitimately ends with a noreturn
553        // call or an unreachable, in which case it won't actually fall
554        // out the bottom of the function.
555      } else if (MBB->succ_size() == LandingPadSuccs.size()) {
556        // It's possible that the block legitimately ends with a noreturn
557        // call or an unreachable, in which case it won't actuall fall
558        // out of the block.
559      } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
560        report("MBB exits via unconditional fall-through but doesn't have "
561               "exactly one CFG successor!", MBB);
562      } else if (!MBB->isSuccessor(MBBI)) {
563        report("MBB exits via unconditional fall-through but its successor "
564               "differs from its CFG successor!", MBB);
565      }
566      if (!MBB->empty() && getBundleStart(&MBB->back())->isBarrier() &&
567          !TII->isPredicated(getBundleStart(&MBB->back()))) {
568        report("MBB exits via unconditional fall-through but ends with a "
569               "barrier instruction!", MBB);
570      }
571      if (!Cond.empty()) {
572        report("MBB exits via unconditional fall-through but has a condition!",
573               MBB);
574      }
575    } else if (TBB && !FBB && Cond.empty()) {
576      // Block unconditionally branches somewhere.
577      if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
578        report("MBB exits via unconditional branch but doesn't have "
579               "exactly one CFG successor!", MBB);
580      } else if (!MBB->isSuccessor(TBB)) {
581        report("MBB exits via unconditional branch but the CFG "
582               "successor doesn't match the actual successor!", MBB);
583      }
584      if (MBB->empty()) {
585        report("MBB exits via unconditional branch but doesn't contain "
586               "any instructions!", MBB);
587      } else if (!getBundleStart(&MBB->back())->isBarrier()) {
588        report("MBB exits via unconditional branch but doesn't end with a "
589               "barrier instruction!", MBB);
590      } else if (!getBundleStart(&MBB->back())->isTerminator()) {
591        report("MBB exits via unconditional branch but the branch isn't a "
592               "terminator instruction!", MBB);
593      }
594    } else if (TBB && !FBB && !Cond.empty()) {
595      // Block conditionally branches somewhere, otherwise falls through.
596      MachineFunction::const_iterator MBBI = MBB;
597      ++MBBI;
598      if (MBBI == MF->end()) {
599        report("MBB conditionally falls through out of function!", MBB);
600      } else if (MBB->succ_size() == 1) {
601        // A conditional branch with only one successor is weird, but allowed.
602        if (&*MBBI != TBB)
603          report("MBB exits via conditional branch/fall-through but only has "
604                 "one CFG successor!", MBB);
605        else if (TBB != *MBB->succ_begin())
606          report("MBB exits via conditional branch/fall-through but the CFG "
607                 "successor don't match the actual successor!", MBB);
608      } else if (MBB->succ_size() != 2) {
609        report("MBB exits via conditional branch/fall-through but doesn't have "
610               "exactly two CFG successors!", MBB);
611      } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
612        report("MBB exits via conditional branch/fall-through but the CFG "
613               "successors don't match the actual successors!", MBB);
614      }
615      if (MBB->empty()) {
616        report("MBB exits via conditional branch/fall-through but doesn't "
617               "contain any instructions!", MBB);
618      } else if (getBundleStart(&MBB->back())->isBarrier()) {
619        report("MBB exits via conditional branch/fall-through but ends with a "
620               "barrier instruction!", MBB);
621      } else if (!getBundleStart(&MBB->back())->isTerminator()) {
622        report("MBB exits via conditional branch/fall-through but the branch "
623               "isn't a terminator instruction!", MBB);
624      }
625    } else if (TBB && FBB) {
626      // Block conditionally branches somewhere, otherwise branches
627      // somewhere else.
628      if (MBB->succ_size() == 1) {
629        // A conditional branch with only one successor is weird, but allowed.
630        if (FBB != TBB)
631          report("MBB exits via conditional branch/branch through but only has "
632                 "one CFG successor!", MBB);
633        else if (TBB != *MBB->succ_begin())
634          report("MBB exits via conditional branch/branch through but the CFG "
635                 "successor don't match the actual successor!", MBB);
636      } else if (MBB->succ_size() != 2) {
637        report("MBB exits via conditional branch/branch but doesn't have "
638               "exactly two CFG successors!", MBB);
639      } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
640        report("MBB exits via conditional branch/branch but the CFG "
641               "successors don't match the actual successors!", MBB);
642      }
643      if (MBB->empty()) {
644        report("MBB exits via conditional branch/branch but doesn't "
645               "contain any instructions!", MBB);
646      } else if (!getBundleStart(&MBB->back())->isBarrier()) {
647        report("MBB exits via conditional branch/branch but doesn't end with a "
648               "barrier instruction!", MBB);
649      } else if (!getBundleStart(&MBB->back())->isTerminator()) {
650        report("MBB exits via conditional branch/branch but the branch "
651               "isn't a terminator instruction!", MBB);
652      }
653      if (Cond.empty()) {
654        report("MBB exits via conditinal branch/branch but there's no "
655               "condition!", MBB);
656      }
657    } else {
658      report("AnalyzeBranch returned invalid data!", MBB);
659    }
660  }
661
662  regsLive.clear();
663  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
664         E = MBB->livein_end(); I != E; ++I) {
665    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
666      report("MBB live-in list contains non-physical register", MBB);
667      continue;
668    }
669    regsLive.insert(*I);
670    for (MCSubRegIterator SubRegs(*I, TRI); SubRegs.isValid(); ++SubRegs)
671      regsLive.insert(*SubRegs);
672  }
673  regsLiveInButUnused = regsLive;
674
675  const MachineFrameInfo *MFI = MF->getFrameInfo();
676  assert(MFI && "Function has no frame info");
677  BitVector PR = MFI->getPristineRegs(MBB);
678  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
679    regsLive.insert(I);
680    for (MCSubRegIterator SubRegs(I, TRI); SubRegs.isValid(); ++SubRegs)
681      regsLive.insert(*SubRegs);
682  }
683
684  regsKilled.clear();
685  regsDefined.clear();
686
687  if (Indexes)
688    lastIndex = Indexes->getMBBStartIdx(MBB);
689}
690
691// This function gets called for all bundle headers, including normal
692// stand-alone unbundled instructions.
693void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
694  if (Indexes && Indexes->hasIndex(MI)) {
695    SlotIndex idx = Indexes->getInstructionIndex(MI);
696    if (!(idx > lastIndex)) {
697      report("Instruction index out of order", MI);
698      *OS << "Last instruction was at " << lastIndex << '\n';
699    }
700    lastIndex = idx;
701  }
702
703  // Ensure non-terminators don't follow terminators.
704  // Ignore predicated terminators formed by if conversion.
705  // FIXME: If conversion shouldn't need to violate this rule.
706  if (MI->isTerminator() && !TII->isPredicated(MI)) {
707    if (!FirstTerminator)
708      FirstTerminator = MI;
709  } else if (FirstTerminator) {
710    report("Non-terminator instruction after the first terminator", MI);
711    *OS << "First terminator was:\t" << *FirstTerminator;
712  }
713}
714
715// The operands on an INLINEASM instruction must follow a template.
716// Verify that the flag operands make sense.
717void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
718  // The first two operands on INLINEASM are the asm string and global flags.
719  if (MI->getNumOperands() < 2) {
720    report("Too few operands on inline asm", MI);
721    return;
722  }
723  if (!MI->getOperand(0).isSymbol())
724    report("Asm string must be an external symbol", MI);
725  if (!MI->getOperand(1).isImm())
726    report("Asm flags must be an immediate", MI);
727  // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
728  // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16.
729  if (!isUInt<5>(MI->getOperand(1).getImm()))
730    report("Unknown asm flags", &MI->getOperand(1), 1);
731
732  assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed");
733
734  unsigned OpNo = InlineAsm::MIOp_FirstOperand;
735  unsigned NumOps;
736  for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
737    const MachineOperand &MO = MI->getOperand(OpNo);
738    // There may be implicit ops after the fixed operands.
739    if (!MO.isImm())
740      break;
741    NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
742  }
743
744  if (OpNo > MI->getNumOperands())
745    report("Missing operands in last group", MI);
746
747  // An optional MDNode follows the groups.
748  if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
749    ++OpNo;
750
751  // All trailing operands must be implicit registers.
752  for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
753    const MachineOperand &MO = MI->getOperand(OpNo);
754    if (!MO.isReg() || !MO.isImplicit())
755      report("Expected implicit register after groups", &MO, OpNo);
756  }
757}
758
759void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
760  const MCInstrDesc &MCID = MI->getDesc();
761  if (MI->getNumOperands() < MCID.getNumOperands()) {
762    report("Too few operands", MI);
763    *OS << MCID.getNumOperands() << " operands expected, but "
764        << MI->getNumExplicitOperands() << " given.\n";
765  }
766
767  // Check the tied operands.
768  if (MI->isInlineAsm())
769    verifyInlineAsm(MI);
770
771  // Check the MachineMemOperands for basic consistency.
772  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
773       E = MI->memoperands_end(); I != E; ++I) {
774    if ((*I)->isLoad() && !MI->mayLoad())
775      report("Missing mayLoad flag", MI);
776    if ((*I)->isStore() && !MI->mayStore())
777      report("Missing mayStore flag", MI);
778  }
779
780  // Debug values must not have a slot index.
781  // Other instructions must have one, unless they are inside a bundle.
782  if (LiveInts) {
783    bool mapped = !LiveInts->isNotInMIMap(MI);
784    if (MI->isDebugValue()) {
785      if (mapped)
786        report("Debug instruction has a slot index", MI);
787    } else if (MI->isInsideBundle()) {
788      if (mapped)
789        report("Instruction inside bundle has a slot index", MI);
790    } else {
791      if (!mapped)
792        report("Missing slot index", MI);
793    }
794  }
795
796  StringRef ErrorInfo;
797  if (!TII->verifyInstruction(MI, ErrorInfo))
798    report(ErrorInfo.data(), MI);
799}
800
801void
802MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
803  const MachineInstr *MI = MO->getParent();
804  const MCInstrDesc &MCID = MI->getDesc();
805
806  // The first MCID.NumDefs operands must be explicit register defines
807  if (MONum < MCID.getNumDefs()) {
808    const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
809    if (!MO->isReg())
810      report("Explicit definition must be a register", MO, MONum);
811    else if (!MO->isDef() && !MCOI.isOptionalDef())
812      report("Explicit definition marked as use", MO, MONum);
813    else if (MO->isImplicit())
814      report("Explicit definition marked as implicit", MO, MONum);
815  } else if (MONum < MCID.getNumOperands()) {
816    const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
817    // Don't check if it's the last operand in a variadic instruction. See,
818    // e.g., LDM_RET in the arm back end.
819    if (MO->isReg() &&
820        !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
821      if (MO->isDef() && !MCOI.isOptionalDef())
822          report("Explicit operand marked as def", MO, MONum);
823      if (MO->isImplicit())
824        report("Explicit operand marked as implicit", MO, MONum);
825    }
826
827    int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
828    if (TiedTo != -1) {
829      if (!MO->isReg())
830        report("Tied use must be a register", MO, MONum);
831      else if (!MO->isTied())
832        report("Operand should be tied", MO, MONum);
833      else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
834        report("Tied def doesn't match MCInstrDesc", MO, MONum);
835    } else if (MO->isReg() && MO->isTied())
836      report("Explicit operand should not be tied", MO, MONum);
837  } else {
838    // ARM adds %reg0 operands to indicate predicates. We'll allow that.
839    if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
840      report("Extra explicit operand on non-variadic instruction", MO, MONum);
841  }
842
843  switch (MO->getType()) {
844  case MachineOperand::MO_Register: {
845    const unsigned Reg = MO->getReg();
846    if (!Reg)
847      return;
848    if (MRI->tracksLiveness() && !MI->isDebugValue())
849      checkLiveness(MO, MONum);
850
851    // Verify the consistency of tied operands.
852    if (MO->isTied()) {
853      unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
854      const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
855      if (!OtherMO.isReg())
856        report("Must be tied to a register", MO, MONum);
857      if (!OtherMO.isTied())
858        report("Missing tie flags on tied operand", MO, MONum);
859      if (MI->findTiedOperandIdx(OtherIdx) != MONum)
860        report("Inconsistent tie links", MO, MONum);
861      if (MONum < MCID.getNumDefs()) {
862        if (OtherIdx < MCID.getNumOperands()) {
863          if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
864            report("Explicit def tied to explicit use without tie constraint",
865                   MO, MONum);
866        } else {
867          if (!OtherMO.isImplicit())
868            report("Explicit def should be tied to implicit use", MO, MONum);
869        }
870      }
871    }
872
873    // Verify two-address constraints after leaving SSA form.
874    unsigned DefIdx;
875    if (!MRI->isSSA() && MO->isUse() &&
876        MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
877        Reg != MI->getOperand(DefIdx).getReg())
878      report("Two-address instruction operands must be identical", MO, MONum);
879
880    // Check register classes.
881    if (MONum < MCID.getNumOperands() && !MO->isImplicit()) {
882      unsigned SubIdx = MO->getSubReg();
883
884      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
885        if (SubIdx) {
886          report("Illegal subregister index for physical register", MO, MONum);
887          return;
888        }
889        if (const TargetRegisterClass *DRC =
890              TII->getRegClass(MCID, MONum, TRI, *MF)) {
891          if (!DRC->contains(Reg)) {
892            report("Illegal physical register for instruction", MO, MONum);
893            *OS << TRI->getName(Reg) << " is not a "
894                << DRC->getName() << " register.\n";
895          }
896        }
897      } else {
898        // Virtual register.
899        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
900        if (SubIdx) {
901          const TargetRegisterClass *SRC =
902            TRI->getSubClassWithSubReg(RC, SubIdx);
903          if (!SRC) {
904            report("Invalid subregister index for virtual register", MO, MONum);
905            *OS << "Register class " << RC->getName()
906                << " does not support subreg index " << SubIdx << "\n";
907            return;
908          }
909          if (RC != SRC) {
910            report("Invalid register class for subregister index", MO, MONum);
911            *OS << "Register class " << RC->getName()
912                << " does not fully support subreg index " << SubIdx << "\n";
913            return;
914          }
915        }
916        if (const TargetRegisterClass *DRC =
917              TII->getRegClass(MCID, MONum, TRI, *MF)) {
918          if (SubIdx) {
919            const TargetRegisterClass *SuperRC =
920              TRI->getLargestLegalSuperClass(RC);
921            if (!SuperRC) {
922              report("No largest legal super class exists.", MO, MONum);
923              return;
924            }
925            DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
926            if (!DRC) {
927              report("No matching super-reg register class.", MO, MONum);
928              return;
929            }
930          }
931          if (!RC->hasSuperClassEq(DRC)) {
932            report("Illegal virtual register for instruction", MO, MONum);
933            *OS << "Expected a " << DRC->getName() << " register, but got a "
934                << RC->getName() << " register\n";
935          }
936        }
937      }
938    }
939    break;
940  }
941
942  case MachineOperand::MO_RegisterMask:
943    regMasks.push_back(MO->getRegMask());
944    break;
945
946  case MachineOperand::MO_MachineBasicBlock:
947    if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
948      report("PHI operand is not in the CFG", MO, MONum);
949    break;
950
951  case MachineOperand::MO_FrameIndex:
952    if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
953        LiveInts && !LiveInts->isNotInMIMap(MI)) {
954      LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
955      SlotIndex Idx = LiveInts->getInstructionIndex(MI);
956      if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) {
957        report("Instruction loads from dead spill slot", MO, MONum);
958        *OS << "Live stack: " << LI << '\n';
959      }
960      if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) {
961        report("Instruction stores to dead spill slot", MO, MONum);
962        *OS << "Live stack: " << LI << '\n';
963      }
964    }
965    break;
966
967  default:
968    break;
969  }
970}
971
972void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
973  const MachineInstr *MI = MO->getParent();
974  const unsigned Reg = MO->getReg();
975
976  // Both use and def operands can read a register.
977  if (MO->readsReg()) {
978    regsLiveInButUnused.erase(Reg);
979
980    if (MO->isKill())
981      addRegWithSubRegs(regsKilled, Reg);
982
983    // Check that LiveVars knows this kill.
984    if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
985        MO->isKill()) {
986      LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
987      if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end())
988        report("Kill missing from LiveVariables", MO, MONum);
989    }
990
991    // Check LiveInts liveness and kill.
992    if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
993      SlotIndex UseIdx = LiveInts->getInstructionIndex(MI);
994      // Check the cached regunit intervals.
995      if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
996        for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
997          if (const LiveInterval *LI = LiveInts->getCachedRegUnit(*Units)) {
998            LiveRangeQuery LRQ(*LI, UseIdx);
999            if (!LRQ.valueIn()) {
1000              report("No live range at use", MO, MONum);
1001              *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI)
1002                  << ' ' << *LI << '\n';
1003            }
1004            if (MO->isKill() && !LRQ.isKill()) {
1005              report("Live range continues after kill flag", MO, MONum);
1006              *OS << PrintRegUnit(*Units, TRI) << ' ' << *LI << '\n';
1007            }
1008          }
1009        }
1010      }
1011
1012      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1013        if (LiveInts->hasInterval(Reg)) {
1014          // This is a virtual register interval.
1015          const LiveInterval &LI = LiveInts->getInterval(Reg);
1016          LiveRangeQuery LRQ(LI, UseIdx);
1017          if (!LRQ.valueIn()) {
1018            report("No live range at use", MO, MONum);
1019            *OS << UseIdx << " is not live in " << LI << '\n';
1020          }
1021          // Check for extra kill flags.
1022          // Note that we allow missing kill flags for now.
1023          if (MO->isKill() && !LRQ.isKill()) {
1024            report("Live range continues after kill flag", MO, MONum);
1025            *OS << "Live range: " << LI << '\n';
1026          }
1027        } else {
1028          report("Virtual register has no live interval", MO, MONum);
1029        }
1030      }
1031    }
1032
1033    // Use of a dead register.
1034    if (!regsLive.count(Reg)) {
1035      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1036        // Reserved registers may be used even when 'dead'.
1037        if (!isReserved(Reg))
1038          report("Using an undefined physical register", MO, MONum);
1039      } else if (MRI->def_empty(Reg)) {
1040        report("Reading virtual register without a def", MO, MONum);
1041      } else {
1042        BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1043        // We don't know which virtual registers are live in, so only complain
1044        // if vreg was killed in this MBB. Otherwise keep track of vregs that
1045        // must be live in. PHI instructions are handled separately.
1046        if (MInfo.regsKilled.count(Reg))
1047          report("Using a killed virtual register", MO, MONum);
1048        else if (!MI->isPHI())
1049          MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
1050      }
1051    }
1052  }
1053
1054  if (MO->isDef()) {
1055    // Register defined.
1056    // TODO: verify that earlyclobber ops are not used.
1057    if (MO->isDead())
1058      addRegWithSubRegs(regsDead, Reg);
1059    else
1060      addRegWithSubRegs(regsDefined, Reg);
1061
1062    // Verify SSA form.
1063    if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
1064        llvm::next(MRI->def_begin(Reg)) != MRI->def_end())
1065      report("Multiple virtual register defs in SSA form", MO, MONum);
1066
1067    // Check LiveInts for a live range, but only for virtual registers.
1068    if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
1069        !LiveInts->isNotInMIMap(MI)) {
1070      SlotIndex DefIdx = LiveInts->getInstructionIndex(MI);
1071      DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
1072      if (LiveInts->hasInterval(Reg)) {
1073        const LiveInterval &LI = LiveInts->getInterval(Reg);
1074        if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
1075          assert(VNI && "NULL valno is not allowed");
1076          if (VNI->def != DefIdx) {
1077            report("Inconsistent valno->def", MO, MONum);
1078            *OS << "Valno " << VNI->id << " is not defined at "
1079              << DefIdx << " in " << LI << '\n';
1080          }
1081        } else {
1082          report("No live range at def", MO, MONum);
1083          *OS << DefIdx << " is not live in " << LI << '\n';
1084        }
1085      } else {
1086        report("Virtual register has no Live interval", MO, MONum);
1087      }
1088    }
1089  }
1090}
1091
1092void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
1093}
1094
1095// This function gets called after visiting all instructions in a bundle. The
1096// argument points to the bundle header.
1097// Normal stand-alone instructions are also considered 'bundles', and this
1098// function is called for all of them.
1099void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
1100  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1101  set_union(MInfo.regsKilled, regsKilled);
1102  set_subtract(regsLive, regsKilled); regsKilled.clear();
1103  // Kill any masked registers.
1104  while (!regMasks.empty()) {
1105    const uint32_t *Mask = regMasks.pop_back_val();
1106    for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
1107      if (TargetRegisterInfo::isPhysicalRegister(*I) &&
1108          MachineOperand::clobbersPhysReg(Mask, *I))
1109        regsDead.push_back(*I);
1110  }
1111  set_subtract(regsLive, regsDead);   regsDead.clear();
1112  set_union(regsLive, regsDefined);   regsDefined.clear();
1113}
1114
1115void
1116MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
1117  MBBInfoMap[MBB].regsLiveOut = regsLive;
1118  regsLive.clear();
1119
1120  if (Indexes) {
1121    SlotIndex stop = Indexes->getMBBEndIdx(MBB);
1122    if (!(stop > lastIndex)) {
1123      report("Block ends before last instruction index", MBB);
1124      *OS << "Block ends at " << stop
1125          << " last instruction was at " << lastIndex << '\n';
1126    }
1127    lastIndex = stop;
1128  }
1129}
1130
1131// Calculate the largest possible vregsPassed sets. These are the registers that
1132// can pass through an MBB live, but may not be live every time. It is assumed
1133// that all vregsPassed sets are empty before the call.
1134void MachineVerifier::calcRegsPassed() {
1135  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
1136  // have any vregsPassed.
1137  SmallPtrSet<const MachineBasicBlock*, 8> todo;
1138  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1139       MFI != MFE; ++MFI) {
1140    const MachineBasicBlock &MBB(*MFI);
1141    BBInfo &MInfo = MBBInfoMap[&MBB];
1142    if (!MInfo.reachable)
1143      continue;
1144    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
1145           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
1146      BBInfo &SInfo = MBBInfoMap[*SuI];
1147      if (SInfo.addPassed(MInfo.regsLiveOut))
1148        todo.insert(*SuI);
1149    }
1150  }
1151
1152  // Iteratively push vregsPassed to successors. This will converge to the same
1153  // final state regardless of DenseSet iteration order.
1154  while (!todo.empty()) {
1155    const MachineBasicBlock *MBB = *todo.begin();
1156    todo.erase(MBB);
1157    BBInfo &MInfo = MBBInfoMap[MBB];
1158    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
1159           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
1160      if (*SuI == MBB)
1161        continue;
1162      BBInfo &SInfo = MBBInfoMap[*SuI];
1163      if (SInfo.addPassed(MInfo.vregsPassed))
1164        todo.insert(*SuI);
1165    }
1166  }
1167}
1168
1169// Calculate the set of virtual registers that must be passed through each basic
1170// block in order to satisfy the requirements of successor blocks. This is very
1171// similar to calcRegsPassed, only backwards.
1172void MachineVerifier::calcRegsRequired() {
1173  // First push live-in regs to predecessors' vregsRequired.
1174  SmallPtrSet<const MachineBasicBlock*, 8> todo;
1175  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1176       MFI != MFE; ++MFI) {
1177    const MachineBasicBlock &MBB(*MFI);
1178    BBInfo &MInfo = MBBInfoMap[&MBB];
1179    for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
1180           PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
1181      BBInfo &PInfo = MBBInfoMap[*PrI];
1182      if (PInfo.addRequired(MInfo.vregsLiveIn))
1183        todo.insert(*PrI);
1184    }
1185  }
1186
1187  // Iteratively push vregsRequired to predecessors. This will converge to the
1188  // same final state regardless of DenseSet iteration order.
1189  while (!todo.empty()) {
1190    const MachineBasicBlock *MBB = *todo.begin();
1191    todo.erase(MBB);
1192    BBInfo &MInfo = MBBInfoMap[MBB];
1193    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1194           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1195      if (*PrI == MBB)
1196        continue;
1197      BBInfo &SInfo = MBBInfoMap[*PrI];
1198      if (SInfo.addRequired(MInfo.vregsRequired))
1199        todo.insert(*PrI);
1200    }
1201  }
1202}
1203
1204// Check PHI instructions at the beginning of MBB. It is assumed that
1205// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
1206void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
1207  SmallPtrSet<const MachineBasicBlock*, 8> seen;
1208  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
1209       BBI != BBE && BBI->isPHI(); ++BBI) {
1210    seen.clear();
1211
1212    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
1213      unsigned Reg = BBI->getOperand(i).getReg();
1214      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
1215      if (!Pre->isSuccessor(MBB))
1216        continue;
1217      seen.insert(Pre);
1218      BBInfo &PrInfo = MBBInfoMap[Pre];
1219      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
1220        report("PHI operand is not live-out from predecessor",
1221               &BBI->getOperand(i), i);
1222    }
1223
1224    // Did we see all predecessors?
1225    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1226           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1227      if (!seen.count(*PrI)) {
1228        report("Missing PHI operand", BBI);
1229        *OS << "BB#" << (*PrI)->getNumber()
1230            << " is a predecessor according to the CFG.\n";
1231      }
1232    }
1233  }
1234}
1235
1236void MachineVerifier::visitMachineFunctionAfter() {
1237  calcRegsPassed();
1238
1239  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1240       MFI != MFE; ++MFI) {
1241    BBInfo &MInfo = MBBInfoMap[MFI];
1242
1243    // Skip unreachable MBBs.
1244    if (!MInfo.reachable)
1245      continue;
1246
1247    checkPHIOps(MFI);
1248  }
1249
1250  // Now check liveness info if available
1251  calcRegsRequired();
1252
1253  // Check for killed virtual registers that should be live out.
1254  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1255       MFI != MFE; ++MFI) {
1256    BBInfo &MInfo = MBBInfoMap[MFI];
1257    for (RegSet::iterator
1258         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1259         ++I)
1260      if (MInfo.regsKilled.count(*I)) {
1261        report("Virtual register killed in block, but needed live out.", MFI);
1262        *OS << "Virtual register " << PrintReg(*I)
1263            << " is used after the block.\n";
1264      }
1265  }
1266
1267  if (!MF->empty()) {
1268    BBInfo &MInfo = MBBInfoMap[&MF->front()];
1269    for (RegSet::iterator
1270         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1271         ++I)
1272      report("Virtual register def doesn't dominate all uses.",
1273             MRI->getVRegDef(*I));
1274  }
1275
1276  if (LiveVars)
1277    verifyLiveVariables();
1278  if (LiveInts)
1279    verifyLiveIntervals();
1280}
1281
1282void MachineVerifier::verifyLiveVariables() {
1283  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
1284  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1285    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1286    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1287    for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1288         MFI != MFE; ++MFI) {
1289      BBInfo &MInfo = MBBInfoMap[MFI];
1290
1291      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1292      if (MInfo.vregsRequired.count(Reg)) {
1293        if (!VI.AliveBlocks.test(MFI->getNumber())) {
1294          report("LiveVariables: Block missing from AliveBlocks", MFI);
1295          *OS << "Virtual register " << PrintReg(Reg)
1296              << " must be live through the block.\n";
1297        }
1298      } else {
1299        if (VI.AliveBlocks.test(MFI->getNumber())) {
1300          report("LiveVariables: Block should not be in AliveBlocks", MFI);
1301          *OS << "Virtual register " << PrintReg(Reg)
1302              << " is not needed live through the block.\n";
1303        }
1304      }
1305    }
1306  }
1307}
1308
1309void MachineVerifier::verifyLiveIntervals() {
1310  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
1311  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1312    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1313
1314    // Spilling and splitting may leave unused registers around. Skip them.
1315    if (MRI->reg_nodbg_empty(Reg))
1316      continue;
1317
1318    if (!LiveInts->hasInterval(Reg)) {
1319      report("Missing live interval for virtual register", MF);
1320      *OS << PrintReg(Reg, TRI) << " still has defs or uses\n";
1321      continue;
1322    }
1323
1324    const LiveInterval &LI = LiveInts->getInterval(Reg);
1325    assert(Reg == LI.reg && "Invalid reg to interval mapping");
1326    verifyLiveInterval(LI);
1327  }
1328
1329  // Verify all the cached regunit intervals.
1330  for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
1331    if (const LiveInterval *LI = LiveInts->getCachedRegUnit(i))
1332      verifyLiveInterval(*LI);
1333}
1334
1335void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI,
1336                                              VNInfo *VNI) {
1337  if (VNI->isUnused())
1338    return;
1339
1340  const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
1341
1342  if (!DefVNI) {
1343    report("Valno not live at def and not marked unused", MF, LI);
1344    *OS << "Valno #" << VNI->id << '\n';
1345    return;
1346  }
1347
1348  if (DefVNI != VNI) {
1349    report("Live range at def has different valno", MF, LI);
1350    *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1351        << " where valno #" << DefVNI->id << " is live\n";
1352    return;
1353  }
1354
1355  const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1356  if (!MBB) {
1357    report("Invalid definition index", MF, LI);
1358    *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1359        << " in " << LI << '\n';
1360    return;
1361  }
1362
1363  if (VNI->isPHIDef()) {
1364    if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1365      report("PHIDef value is not defined at MBB start", MBB, LI);
1366      *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1367          << ", not at the beginning of BB#" << MBB->getNumber() << '\n';
1368    }
1369    return;
1370  }
1371
1372  // Non-PHI def.
1373  const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1374  if (!MI) {
1375    report("No instruction at def index", MBB, LI);
1376    *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1377    return;
1378  }
1379
1380  bool hasDef = false;
1381  bool isEarlyClobber = false;
1382  for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1383    if (!MOI->isReg() || !MOI->isDef())
1384      continue;
1385    if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1386      if (MOI->getReg() != LI.reg)
1387        continue;
1388    } else {
1389      if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1390          !TRI->hasRegUnit(MOI->getReg(), LI.reg))
1391        continue;
1392    }
1393    hasDef = true;
1394    if (MOI->isEarlyClobber())
1395      isEarlyClobber = true;
1396  }
1397
1398  if (!hasDef) {
1399    report("Defining instruction does not modify register", MI);
1400    *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1401  }
1402
1403  // Early clobber defs begin at USE slots, but other defs must begin at
1404  // DEF slots.
1405  if (isEarlyClobber) {
1406    if (!VNI->def.isEarlyClobber()) {
1407      report("Early clobber def must be at an early-clobber slot", MBB, LI);
1408      *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1409    }
1410  } else if (!VNI->def.isRegister()) {
1411    report("Non-PHI, non-early clobber def must be at a register slot",
1412           MBB, LI);
1413    *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1414  }
1415}
1416
1417void
1418MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI,
1419                                           LiveInterval::const_iterator I) {
1420  const VNInfo *VNI = I->valno;
1421  assert(VNI && "Live range has no valno");
1422
1423  if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
1424    report("Foreign valno in live range", MF, LI);
1425    *OS << *I << " has a bad valno\n";
1426  }
1427
1428  if (VNI->isUnused()) {
1429    report("Live range valno is marked unused", MF, LI);
1430    *OS << *I << '\n';
1431  }
1432
1433  const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
1434  if (!MBB) {
1435    report("Bad start of live segment, no basic block", MF, LI);
1436    *OS << *I << '\n';
1437    return;
1438  }
1439  SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1440  if (I->start != MBBStartIdx && I->start != VNI->def) {
1441    report("Live segment must begin at MBB entry or valno def", MBB, LI);
1442    *OS << *I << '\n';
1443  }
1444
1445  const MachineBasicBlock *EndMBB =
1446    LiveInts->getMBBFromIndex(I->end.getPrevSlot());
1447  if (!EndMBB) {
1448    report("Bad end of live segment, no basic block", MF, LI);
1449    *OS << *I << '\n';
1450    return;
1451  }
1452
1453  // No more checks for live-out segments.
1454  if (I->end == LiveInts->getMBBEndIdx(EndMBB))
1455    return;
1456
1457  // RegUnit intervals are allowed dead phis.
1458  if (!TargetRegisterInfo::isVirtualRegister(LI.reg) && VNI->isPHIDef() &&
1459      I->start == VNI->def && I->end == VNI->def.getDeadSlot())
1460    return;
1461
1462  // The live segment is ending inside EndMBB
1463  const MachineInstr *MI =
1464    LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
1465  if (!MI) {
1466    report("Live segment doesn't end at a valid instruction", EndMBB, LI);
1467    *OS << *I << '\n';
1468    return;
1469  }
1470
1471  // The block slot must refer to a basic block boundary.
1472  if (I->end.isBlock()) {
1473    report("Live segment ends at B slot of an instruction", EndMBB, LI);
1474    *OS << *I << '\n';
1475  }
1476
1477  if (I->end.isDead()) {
1478    // Segment ends on the dead slot.
1479    // That means there must be a dead def.
1480    if (!SlotIndex::isSameInstr(I->start, I->end)) {
1481      report("Live segment ending at dead slot spans instructions", EndMBB, LI);
1482      *OS << *I << '\n';
1483    }
1484  }
1485
1486  // A live segment can only end at an early-clobber slot if it is being
1487  // redefined by an early-clobber def.
1488  if (I->end.isEarlyClobber()) {
1489    if (I+1 == LI.end() || (I+1)->start != I->end) {
1490      report("Live segment ending at early clobber slot must be "
1491             "redefined by an EC def in the same instruction", EndMBB, LI);
1492      *OS << *I << '\n';
1493    }
1494  }
1495
1496  // The following checks only apply to virtual registers. Physreg liveness
1497  // is too weird to check.
1498  if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1499    // A live range can end with either a redefinition, a kill flag on a
1500    // use, or a dead flag on a def.
1501    bool hasRead = false;
1502    bool hasDeadDef = false;
1503    for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1504      if (!MOI->isReg() || MOI->getReg() != LI.reg)
1505        continue;
1506      if (MOI->readsReg())
1507        hasRead = true;
1508      if (MOI->isDef() && MOI->isDead())
1509        hasDeadDef = true;
1510    }
1511
1512    if (I->end.isDead()) {
1513      if (!hasDeadDef) {
1514        report("Instruction doesn't have a dead def operand", MI);
1515        I->print(*OS);
1516        *OS << " in " << LI << '\n';
1517      }
1518    } else {
1519      if (!hasRead) {
1520        report("Instruction ending live range doesn't read the register", MI);
1521        *OS << *I << " in " << LI << '\n';
1522      }
1523    }
1524  }
1525
1526  // Now check all the basic blocks in this live segment.
1527  MachineFunction::const_iterator MFI = MBB;
1528  // Is this live range the beginning of a non-PHIDef VN?
1529  if (I->start == VNI->def && !VNI->isPHIDef()) {
1530    // Not live-in to any blocks.
1531    if (MBB == EndMBB)
1532      return;
1533    // Skip this block.
1534    ++MFI;
1535  }
1536  for (;;) {
1537    assert(LiveInts->isLiveInToMBB(LI, MFI));
1538    // We don't know how to track physregs into a landing pad.
1539    if (!TargetRegisterInfo::isVirtualRegister(LI.reg) &&
1540        MFI->isLandingPad()) {
1541      if (&*MFI == EndMBB)
1542        break;
1543      ++MFI;
1544      continue;
1545    }
1546
1547    // Is VNI a PHI-def in the current block?
1548    bool IsPHI = VNI->isPHIDef() &&
1549      VNI->def == LiveInts->getMBBStartIdx(MFI);
1550
1551    // Check that VNI is live-out of all predecessors.
1552    for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1553         PE = MFI->pred_end(); PI != PE; ++PI) {
1554      SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
1555      const VNInfo *PVNI = LI.getVNInfoBefore(PEnd);
1556
1557      // All predecessors must have a live-out value.
1558      if (!PVNI) {
1559        report("Register not marked live out of predecessor", *PI, LI);
1560        *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1561            << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
1562            << PEnd << '\n';
1563        continue;
1564      }
1565
1566      // Only PHI-defs can take different predecessor values.
1567      if (!IsPHI && PVNI != VNI) {
1568        report("Different value live out of predecessor", *PI, LI);
1569        *OS << "Valno #" << PVNI->id << " live out of BB#"
1570            << (*PI)->getNumber() << '@' << PEnd
1571            << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1572            << '@' << LiveInts->getMBBStartIdx(MFI) << '\n';
1573      }
1574    }
1575    if (&*MFI == EndMBB)
1576      break;
1577    ++MFI;
1578  }
1579}
1580
1581void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
1582  for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
1583       I!=E; ++I)
1584    verifyLiveIntervalValue(LI, *I);
1585
1586  for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I)
1587    verifyLiveIntervalSegment(LI, I);
1588
1589  // Check the LI only has one connected component.
1590  if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1591    ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1592    unsigned NumComp = ConEQ.Classify(&LI);
1593    if (NumComp > 1) {
1594      report("Multiple connected components in live interval", MF, LI);
1595      for (unsigned comp = 0; comp != NumComp; ++comp) {
1596        *OS << comp << ": valnos";
1597        for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1598             E = LI.vni_end(); I!=E; ++I)
1599          if (comp == ConEQ.getEqClass(*I))
1600            *OS << ' ' << (*I)->id;
1601        *OS << '\n';
1602      }
1603    }
1604  }
1605}
1606