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/DepthFirstIterator.h"
29#include "llvm/ADT/SetOperations.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/CodeGen/LiveIntervalAnalysis.h"
32#include "llvm/CodeGen/LiveStackAnalysis.h"
33#include "llvm/CodeGen/LiveVariables.h"
34#include "llvm/CodeGen/MachineFrameInfo.h"
35#include "llvm/CodeGen/MachineFunctionPass.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/FileSystem.h"
45#include "llvm/Support/Format.h"
46#include "llvm/Support/raw_ostream.h"
47#include "llvm/Target/TargetInstrInfo.h"
48#include "llvm/Target/TargetMachine.h"
49#include "llvm/Target/TargetRegisterInfo.h"
50#include "llvm/Target/TargetSubtargetInfo.h"
51using namespace llvm;
52
53namespace {
54  struct MachineVerifier {
55
56    MachineVerifier(Pass *pass, const char *b) :
57      PASS(pass),
58      Banner(b)
59      {}
60
61    bool runOnMachineFunction(MachineFunction &MF);
62
63    Pass *const PASS;
64    const char *Banner;
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    void report(const char *msg, const MachineFunction *MF,
216                const LiveRange &LR, unsigned Reg, unsigned LaneMask);
217    void report(const char *msg, const MachineBasicBlock *MBB,
218                const LiveRange &LR, unsigned Reg, unsigned LaneMask);
219
220    void verifyInlineAsm(const MachineInstr *MI);
221
222    void checkLiveness(const MachineOperand *MO, unsigned MONum);
223    void markReachable(const MachineBasicBlock *MBB);
224    void calcRegsPassed();
225    void checkPHIOps(const MachineBasicBlock *MBB);
226
227    void calcRegsRequired();
228    void verifyLiveVariables();
229    void verifyLiveIntervals();
230    void verifyLiveInterval(const LiveInterval&);
231    void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned,
232                              unsigned);
233    void verifyLiveRangeSegment(const LiveRange&,
234                                const LiveRange::const_iterator I, unsigned,
235                                unsigned);
236    void verifyLiveRange(const LiveRange&, unsigned, unsigned LaneMask = 0);
237
238    void verifyStackFrame();
239  };
240
241  struct MachineVerifierPass : public MachineFunctionPass {
242    static char ID; // Pass ID, replacement for typeid
243    const std::string Banner;
244
245    MachineVerifierPass(const std::string &banner = nullptr)
246      : MachineFunctionPass(ID), Banner(banner) {
247        initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
248      }
249
250    void getAnalysisUsage(AnalysisUsage &AU) const override {
251      AU.setPreservesAll();
252      MachineFunctionPass::getAnalysisUsage(AU);
253    }
254
255    bool runOnMachineFunction(MachineFunction &MF) override {
256      MF.verify(this, Banner.c_str());
257      return false;
258    }
259  };
260
261}
262
263char MachineVerifierPass::ID = 0;
264INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
265                "Verify generated machine code", false, false)
266
267FunctionPass *llvm::createMachineVerifierPass(const std::string &Banner) {
268  return new MachineVerifierPass(Banner);
269}
270
271void MachineFunction::verify(Pass *p, const char *Banner) const {
272  MachineVerifier(p, Banner)
273    .runOnMachineFunction(const_cast<MachineFunction&>(*this));
274}
275
276bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
277  foundErrors = 0;
278
279  this->MF = &MF;
280  TM = &MF.getTarget();
281  TII = MF.getSubtarget().getInstrInfo();
282  TRI = MF.getSubtarget().getRegisterInfo();
283  MRI = &MF.getRegInfo();
284
285  LiveVars = nullptr;
286  LiveInts = nullptr;
287  LiveStks = nullptr;
288  Indexes = nullptr;
289  if (PASS) {
290    LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
291    // We don't want to verify LiveVariables if LiveIntervals is available.
292    if (!LiveInts)
293      LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
294    LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
295    Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
296  }
297
298  visitMachineFunctionBefore();
299  for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
300       MFI!=MFE; ++MFI) {
301    visitMachineBasicBlockBefore(MFI);
302    // Keep track of the current bundle header.
303    const MachineInstr *CurBundle = nullptr;
304    // Do we expect the next instruction to be part of the same bundle?
305    bool InBundle = false;
306
307    for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
308           MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
309      if (MBBI->getParent() != MFI) {
310        report("Bad instruction parent pointer", MFI);
311        errs() << "Instruction: " << *MBBI;
312        continue;
313      }
314
315      // Check for consistent bundle flags.
316      if (InBundle && !MBBI->isBundledWithPred())
317        report("Missing BundledPred flag, "
318               "BundledSucc was set on predecessor", MBBI);
319      if (!InBundle && MBBI->isBundledWithPred())
320        report("BundledPred flag is set, "
321               "but BundledSucc not set on predecessor", MBBI);
322
323      // Is this a bundle header?
324      if (!MBBI->isInsideBundle()) {
325        if (CurBundle)
326          visitMachineBundleAfter(CurBundle);
327        CurBundle = MBBI;
328        visitMachineBundleBefore(CurBundle);
329      } else if (!CurBundle)
330        report("No bundle header", MBBI);
331      visitMachineInstrBefore(MBBI);
332      for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
333        visitMachineOperand(&MBBI->getOperand(I), I);
334      visitMachineInstrAfter(MBBI);
335
336      // Was this the last bundled instruction?
337      InBundle = MBBI->isBundledWithSucc();
338    }
339    if (CurBundle)
340      visitMachineBundleAfter(CurBundle);
341    if (InBundle)
342      report("BundledSucc flag set on last instruction in block", &MFI->back());
343    visitMachineBasicBlockAfter(MFI);
344  }
345  visitMachineFunctionAfter();
346
347  if (foundErrors)
348    report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
349
350  // Clean up.
351  regsLive.clear();
352  regsDefined.clear();
353  regsDead.clear();
354  regsKilled.clear();
355  regMasks.clear();
356  regsLiveInButUnused.clear();
357  MBBInfoMap.clear();
358
359  return false;                 // no changes
360}
361
362void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
363  assert(MF);
364  errs() << '\n';
365  if (!foundErrors++) {
366    if (Banner)
367      errs() << "# " << Banner << '\n';
368    MF->print(errs(), Indexes);
369  }
370  errs() << "*** Bad machine code: " << msg << " ***\n"
371      << "- function:    " << MF->getName() << "\n";
372}
373
374void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
375  assert(MBB);
376  report(msg, MBB->getParent());
377  errs() << "- basic block: BB#" << MBB->getNumber()
378      << ' ' << MBB->getName()
379      << " (" << (const void*)MBB << ')';
380  if (Indexes)
381    errs() << " [" << Indexes->getMBBStartIdx(MBB)
382        << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
383  errs() << '\n';
384}
385
386void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
387  assert(MI);
388  report(msg, MI->getParent());
389  errs() << "- instruction: ";
390  if (Indexes && Indexes->hasIndex(MI))
391    errs() << Indexes->getInstructionIndex(MI) << '\t';
392  MI->print(errs(), TM);
393}
394
395void MachineVerifier::report(const char *msg,
396                             const MachineOperand *MO, unsigned MONum) {
397  assert(MO);
398  report(msg, MO->getParent());
399  errs() << "- operand " << MONum << ":   ";
400  MO->print(errs(), TRI);
401  errs() << "\n";
402}
403
404void MachineVerifier::report(const char *msg, const MachineFunction *MF,
405                             const LiveInterval &LI) {
406  report(msg, MF);
407  errs() << "- interval:    " << LI << '\n';
408}
409
410void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB,
411                             const LiveInterval &LI) {
412  report(msg, MBB);
413  errs() << "- interval:    " << LI << '\n';
414}
415
416void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB,
417                             const LiveRange &LR, unsigned Reg,
418                             unsigned LaneMask) {
419  report(msg, MBB);
420  errs() << "- liverange:   " << LR << '\n';
421  errs() << "- register:    " << PrintReg(Reg, TRI) << '\n';
422  if (LaneMask != 0)
423    errs() << "- lanemask:    " << format("%04X\n", LaneMask);
424}
425
426void MachineVerifier::report(const char *msg, const MachineFunction *MF,
427                             const LiveRange &LR, unsigned Reg,
428                             unsigned LaneMask) {
429  report(msg, MF);
430  errs() << "- liverange:   " << LR << '\n';
431  errs() << "- register:    " << PrintReg(Reg, TRI) << '\n';
432  if (LaneMask != 0)
433    errs() << "- lanemask:    " << format("%04X\n", LaneMask);
434}
435
436void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
437  BBInfo &MInfo = MBBInfoMap[MBB];
438  if (!MInfo.reachable) {
439    MInfo.reachable = true;
440    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
441           SuE = MBB->succ_end(); SuI != SuE; ++SuI)
442      markReachable(*SuI);
443  }
444}
445
446void MachineVerifier::visitMachineFunctionBefore() {
447  lastIndex = SlotIndex();
448  regsReserved = MRI->getReservedRegs();
449
450  // A sub-register of a reserved register is also reserved
451  for (int Reg = regsReserved.find_first(); Reg>=0;
452       Reg = regsReserved.find_next(Reg)) {
453    for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
454      // FIXME: This should probably be:
455      // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register");
456      regsReserved.set(*SubRegs);
457    }
458  }
459
460  markReachable(&MF->front());
461
462  // Build a set of the basic blocks in the function.
463  FunctionBlocks.clear();
464  for (const auto &MBB : *MF) {
465    FunctionBlocks.insert(&MBB);
466    BBInfo &MInfo = MBBInfoMap[&MBB];
467
468    MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end());
469    if (MInfo.Preds.size() != MBB.pred_size())
470      report("MBB has duplicate entries in its predecessor list.", &MBB);
471
472    MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end());
473    if (MInfo.Succs.size() != MBB.succ_size())
474      report("MBB has duplicate entries in its successor list.", &MBB);
475  }
476
477  // Check that the register use lists are sane.
478  MRI->verifyUseLists();
479
480  verifyStackFrame();
481}
482
483// Does iterator point to a and b as the first two elements?
484static bool matchPair(MachineBasicBlock::const_succ_iterator i,
485                      const MachineBasicBlock *a, const MachineBasicBlock *b) {
486  if (*i == a)
487    return *++i == b;
488  if (*i == b)
489    return *++i == a;
490  return false;
491}
492
493void
494MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
495  FirstTerminator = nullptr;
496
497  if (MRI->isSSA()) {
498    // If this block has allocatable physical registers live-in, check that
499    // it is an entry block or landing pad.
500    for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
501           LE = MBB->livein_end();
502         LI != LE; ++LI) {
503      unsigned reg = *LI;
504      if (isAllocatable(reg) && !MBB->isLandingPad() &&
505          MBB != MBB->getParent()->begin()) {
506        report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB);
507      }
508    }
509  }
510
511  // Count the number of landing pad successors.
512  SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
513  for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
514       E = MBB->succ_end(); I != E; ++I) {
515    if ((*I)->isLandingPad())
516      LandingPadSuccs.insert(*I);
517    if (!FunctionBlocks.count(*I))
518      report("MBB has successor that isn't part of the function.", MBB);
519    if (!MBBInfoMap[*I].Preds.count(MBB)) {
520      report("Inconsistent CFG", MBB);
521      errs() << "MBB is not in the predecessor list of the successor BB#"
522          << (*I)->getNumber() << ".\n";
523    }
524  }
525
526  // Check the predecessor list.
527  for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
528       E = MBB->pred_end(); I != E; ++I) {
529    if (!FunctionBlocks.count(*I))
530      report("MBB has predecessor that isn't part of the function.", MBB);
531    if (!MBBInfoMap[*I].Succs.count(MBB)) {
532      report("Inconsistent CFG", MBB);
533      errs() << "MBB is not in the successor list of the predecessor BB#"
534          << (*I)->getNumber() << ".\n";
535    }
536  }
537
538  const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
539  const BasicBlock *BB = MBB->getBasicBlock();
540  if (LandingPadSuccs.size() > 1 &&
541      !(AsmInfo &&
542        AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
543        BB && isa<SwitchInst>(BB->getTerminator())))
544    report("MBB has more than one landing pad successor", MBB);
545
546  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
547  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
548  SmallVector<MachineOperand, 4> Cond;
549  if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
550                          TBB, FBB, Cond)) {
551    // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
552    // check whether its answers match up with reality.
553    if (!TBB && !FBB) {
554      // Block falls through to its successor.
555      MachineFunction::const_iterator MBBI = MBB;
556      ++MBBI;
557      if (MBBI == MF->end()) {
558        // It's possible that the block legitimately ends with a noreturn
559        // call or an unreachable, in which case it won't actually fall
560        // out the bottom of the function.
561      } else if (MBB->succ_size() == LandingPadSuccs.size()) {
562        // It's possible that the block legitimately ends with a noreturn
563        // call or an unreachable, in which case it won't actuall fall
564        // out of the block.
565      } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
566        report("MBB exits via unconditional fall-through but doesn't have "
567               "exactly one CFG successor!", MBB);
568      } else if (!MBB->isSuccessor(MBBI)) {
569        report("MBB exits via unconditional fall-through but its successor "
570               "differs from its CFG successor!", MBB);
571      }
572      if (!MBB->empty() && MBB->back().isBarrier() &&
573          !TII->isPredicated(&MBB->back())) {
574        report("MBB exits via unconditional fall-through but ends with a "
575               "barrier instruction!", MBB);
576      }
577      if (!Cond.empty()) {
578        report("MBB exits via unconditional fall-through but has a condition!",
579               MBB);
580      }
581    } else if (TBB && !FBB && Cond.empty()) {
582      // Block unconditionally branches somewhere.
583      // If the block has exactly one successor, that happens to be a
584      // landingpad, accept it as valid control flow.
585      if (MBB->succ_size() != 1+LandingPadSuccs.size() &&
586          (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 ||
587           *MBB->succ_begin() != *LandingPadSuccs.begin())) {
588        report("MBB exits via unconditional branch but doesn't have "
589               "exactly one CFG successor!", MBB);
590      } else if (!MBB->isSuccessor(TBB)) {
591        report("MBB exits via unconditional branch but the CFG "
592               "successor doesn't match the actual successor!", MBB);
593      }
594      if (MBB->empty()) {
595        report("MBB exits via unconditional branch but doesn't contain "
596               "any instructions!", MBB);
597      } else if (!MBB->back().isBarrier()) {
598        report("MBB exits via unconditional branch but doesn't end with a "
599               "barrier instruction!", MBB);
600      } else if (!MBB->back().isTerminator()) {
601        report("MBB exits via unconditional branch but the branch isn't a "
602               "terminator instruction!", MBB);
603      }
604    } else if (TBB && !FBB && !Cond.empty()) {
605      // Block conditionally branches somewhere, otherwise falls through.
606      MachineFunction::const_iterator MBBI = MBB;
607      ++MBBI;
608      if (MBBI == MF->end()) {
609        report("MBB conditionally falls through out of function!", MBB);
610      } else if (MBB->succ_size() == 1) {
611        // A conditional branch with only one successor is weird, but allowed.
612        if (&*MBBI != TBB)
613          report("MBB exits via conditional branch/fall-through but only has "
614                 "one CFG successor!", MBB);
615        else if (TBB != *MBB->succ_begin())
616          report("MBB exits via conditional branch/fall-through but the CFG "
617                 "successor don't match the actual successor!", MBB);
618      } else if (MBB->succ_size() != 2) {
619        report("MBB exits via conditional branch/fall-through but doesn't have "
620               "exactly two CFG successors!", MBB);
621      } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
622        report("MBB exits via conditional branch/fall-through but the CFG "
623               "successors don't match the actual successors!", MBB);
624      }
625      if (MBB->empty()) {
626        report("MBB exits via conditional branch/fall-through but doesn't "
627               "contain any instructions!", MBB);
628      } else if (MBB->back().isBarrier()) {
629        report("MBB exits via conditional branch/fall-through but ends with a "
630               "barrier instruction!", MBB);
631      } else if (!MBB->back().isTerminator()) {
632        report("MBB exits via conditional branch/fall-through but the branch "
633               "isn't a terminator instruction!", MBB);
634      }
635    } else if (TBB && FBB) {
636      // Block conditionally branches somewhere, otherwise branches
637      // somewhere else.
638      if (MBB->succ_size() == 1) {
639        // A conditional branch with only one successor is weird, but allowed.
640        if (FBB != TBB)
641          report("MBB exits via conditional branch/branch through but only has "
642                 "one CFG successor!", MBB);
643        else if (TBB != *MBB->succ_begin())
644          report("MBB exits via conditional branch/branch through but the CFG "
645                 "successor don't match the actual successor!", MBB);
646      } else if (MBB->succ_size() != 2) {
647        report("MBB exits via conditional branch/branch but doesn't have "
648               "exactly two CFG successors!", MBB);
649      } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
650        report("MBB exits via conditional branch/branch but the CFG "
651               "successors don't match the actual successors!", MBB);
652      }
653      if (MBB->empty()) {
654        report("MBB exits via conditional branch/branch but doesn't "
655               "contain any instructions!", MBB);
656      } else if (!MBB->back().isBarrier()) {
657        report("MBB exits via conditional branch/branch but doesn't end with a "
658               "barrier instruction!", MBB);
659      } else if (!MBB->back().isTerminator()) {
660        report("MBB exits via conditional branch/branch but the branch "
661               "isn't a terminator instruction!", MBB);
662      }
663      if (Cond.empty()) {
664        report("MBB exits via conditinal branch/branch but there's no "
665               "condition!", MBB);
666      }
667    } else {
668      report("AnalyzeBranch returned invalid data!", MBB);
669    }
670  }
671
672  regsLive.clear();
673  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
674         E = MBB->livein_end(); I != E; ++I) {
675    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
676      report("MBB live-in list contains non-physical register", MBB);
677      continue;
678    }
679    for (MCSubRegIterator SubRegs(*I, TRI, /*IncludeSelf=*/true);
680         SubRegs.isValid(); ++SubRegs)
681      regsLive.insert(*SubRegs);
682  }
683  regsLiveInButUnused = regsLive;
684
685  const MachineFrameInfo *MFI = MF->getFrameInfo();
686  assert(MFI && "Function has no frame info");
687  BitVector PR = MFI->getPristineRegs(MBB);
688  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
689    for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
690         SubRegs.isValid(); ++SubRegs)
691      regsLive.insert(*SubRegs);
692  }
693
694  regsKilled.clear();
695  regsDefined.clear();
696
697  if (Indexes)
698    lastIndex = Indexes->getMBBStartIdx(MBB);
699}
700
701// This function gets called for all bundle headers, including normal
702// stand-alone unbundled instructions.
703void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
704  if (Indexes && Indexes->hasIndex(MI)) {
705    SlotIndex idx = Indexes->getInstructionIndex(MI);
706    if (!(idx > lastIndex)) {
707      report("Instruction index out of order", MI);
708      errs() << "Last instruction was at " << lastIndex << '\n';
709    }
710    lastIndex = idx;
711  }
712
713  // Ensure non-terminators don't follow terminators.
714  // Ignore predicated terminators formed by if conversion.
715  // FIXME: If conversion shouldn't need to violate this rule.
716  if (MI->isTerminator() && !TII->isPredicated(MI)) {
717    if (!FirstTerminator)
718      FirstTerminator = MI;
719  } else if (FirstTerminator) {
720    report("Non-terminator instruction after the first terminator", MI);
721    errs() << "First terminator was:\t" << *FirstTerminator;
722  }
723}
724
725// The operands on an INLINEASM instruction must follow a template.
726// Verify that the flag operands make sense.
727void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
728  // The first two operands on INLINEASM are the asm string and global flags.
729  if (MI->getNumOperands() < 2) {
730    report("Too few operands on inline asm", MI);
731    return;
732  }
733  if (!MI->getOperand(0).isSymbol())
734    report("Asm string must be an external symbol", MI);
735  if (!MI->getOperand(1).isImm())
736    report("Asm flags must be an immediate", MI);
737  // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
738  // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16.
739  if (!isUInt<5>(MI->getOperand(1).getImm()))
740    report("Unknown asm flags", &MI->getOperand(1), 1);
741
742  static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed");
743
744  unsigned OpNo = InlineAsm::MIOp_FirstOperand;
745  unsigned NumOps;
746  for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
747    const MachineOperand &MO = MI->getOperand(OpNo);
748    // There may be implicit ops after the fixed operands.
749    if (!MO.isImm())
750      break;
751    NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
752  }
753
754  if (OpNo > MI->getNumOperands())
755    report("Missing operands in last group", MI);
756
757  // An optional MDNode follows the groups.
758  if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
759    ++OpNo;
760
761  // All trailing operands must be implicit registers.
762  for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
763    const MachineOperand &MO = MI->getOperand(OpNo);
764    if (!MO.isReg() || !MO.isImplicit())
765      report("Expected implicit register after groups", &MO, OpNo);
766  }
767}
768
769void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
770  const MCInstrDesc &MCID = MI->getDesc();
771  if (MI->getNumOperands() < MCID.getNumOperands()) {
772    report("Too few operands", MI);
773    errs() << MCID.getNumOperands() << " operands expected, but "
774        << MI->getNumOperands() << " given.\n";
775  }
776
777  // Check the tied operands.
778  if (MI->isInlineAsm())
779    verifyInlineAsm(MI);
780
781  // Check the MachineMemOperands for basic consistency.
782  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
783       E = MI->memoperands_end(); I != E; ++I) {
784    if ((*I)->isLoad() && !MI->mayLoad())
785      report("Missing mayLoad flag", MI);
786    if ((*I)->isStore() && !MI->mayStore())
787      report("Missing mayStore flag", MI);
788  }
789
790  // Debug values must not have a slot index.
791  // Other instructions must have one, unless they are inside a bundle.
792  if (LiveInts) {
793    bool mapped = !LiveInts->isNotInMIMap(MI);
794    if (MI->isDebugValue()) {
795      if (mapped)
796        report("Debug instruction has a slot index", MI);
797    } else if (MI->isInsideBundle()) {
798      if (mapped)
799        report("Instruction inside bundle has a slot index", MI);
800    } else {
801      if (!mapped)
802        report("Missing slot index", MI);
803    }
804  }
805
806  StringRef ErrorInfo;
807  if (!TII->verifyInstruction(MI, ErrorInfo))
808    report(ErrorInfo.data(), MI);
809}
810
811void
812MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
813  const MachineInstr *MI = MO->getParent();
814  const MCInstrDesc &MCID = MI->getDesc();
815
816  // The first MCID.NumDefs operands must be explicit register defines
817  if (MONum < MCID.getNumDefs()) {
818    const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
819    if (!MO->isReg())
820      report("Explicit definition must be a register", MO, MONum);
821    else if (!MO->isDef() && !MCOI.isOptionalDef())
822      report("Explicit definition marked as use", MO, MONum);
823    else if (MO->isImplicit())
824      report("Explicit definition marked as implicit", MO, MONum);
825  } else if (MONum < MCID.getNumOperands()) {
826    const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
827    // Don't check if it's the last operand in a variadic instruction. See,
828    // e.g., LDM_RET in the arm back end.
829    if (MO->isReg() &&
830        !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
831      if (MO->isDef() && !MCOI.isOptionalDef())
832        report("Explicit operand marked as def", MO, MONum);
833      if (MO->isImplicit())
834        report("Explicit operand marked as implicit", MO, MONum);
835    }
836
837    int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
838    if (TiedTo != -1) {
839      if (!MO->isReg())
840        report("Tied use must be a register", MO, MONum);
841      else if (!MO->isTied())
842        report("Operand should be tied", MO, MONum);
843      else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
844        report("Tied def doesn't match MCInstrDesc", MO, MONum);
845    } else if (MO->isReg() && MO->isTied())
846      report("Explicit operand should not be tied", MO, MONum);
847  } else {
848    // ARM adds %reg0 operands to indicate predicates. We'll allow that.
849    if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
850      report("Extra explicit operand on non-variadic instruction", MO, MONum);
851  }
852
853  switch (MO->getType()) {
854  case MachineOperand::MO_Register: {
855    const unsigned Reg = MO->getReg();
856    if (!Reg)
857      return;
858    if (MRI->tracksLiveness() && !MI->isDebugValue())
859      checkLiveness(MO, MONum);
860
861    // Verify the consistency of tied operands.
862    if (MO->isTied()) {
863      unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
864      const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
865      if (!OtherMO.isReg())
866        report("Must be tied to a register", MO, MONum);
867      if (!OtherMO.isTied())
868        report("Missing tie flags on tied operand", MO, MONum);
869      if (MI->findTiedOperandIdx(OtherIdx) != MONum)
870        report("Inconsistent tie links", MO, MONum);
871      if (MONum < MCID.getNumDefs()) {
872        if (OtherIdx < MCID.getNumOperands()) {
873          if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
874            report("Explicit def tied to explicit use without tie constraint",
875                   MO, MONum);
876        } else {
877          if (!OtherMO.isImplicit())
878            report("Explicit def should be tied to implicit use", MO, MONum);
879        }
880      }
881    }
882
883    // Verify two-address constraints after leaving SSA form.
884    unsigned DefIdx;
885    if (!MRI->isSSA() && MO->isUse() &&
886        MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
887        Reg != MI->getOperand(DefIdx).getReg())
888      report("Two-address instruction operands must be identical", MO, MONum);
889
890    // Check register classes.
891    if (MONum < MCID.getNumOperands() && !MO->isImplicit()) {
892      unsigned SubIdx = MO->getSubReg();
893
894      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
895        if (SubIdx) {
896          report("Illegal subregister index for physical register", MO, MONum);
897          return;
898        }
899        if (const TargetRegisterClass *DRC =
900              TII->getRegClass(MCID, MONum, TRI, *MF)) {
901          if (!DRC->contains(Reg)) {
902            report("Illegal physical register for instruction", MO, MONum);
903            errs() << TRI->getName(Reg) << " is not a "
904                << TRI->getRegClassName(DRC) << " register.\n";
905          }
906        }
907      } else {
908        // Virtual register.
909        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
910        if (SubIdx) {
911          const TargetRegisterClass *SRC =
912            TRI->getSubClassWithSubReg(RC, SubIdx);
913          if (!SRC) {
914            report("Invalid subregister index for virtual register", MO, MONum);
915            errs() << "Register class " << TRI->getRegClassName(RC)
916                << " does not support subreg index " << SubIdx << "\n";
917            return;
918          }
919          if (RC != SRC) {
920            report("Invalid register class for subregister index", MO, MONum);
921            errs() << "Register class " << TRI->getRegClassName(RC)
922                << " does not fully support subreg index " << SubIdx << "\n";
923            return;
924          }
925        }
926        if (const TargetRegisterClass *DRC =
927              TII->getRegClass(MCID, MONum, TRI, *MF)) {
928          if (SubIdx) {
929            const TargetRegisterClass *SuperRC =
930                TRI->getLargestLegalSuperClass(RC, *MF);
931            if (!SuperRC) {
932              report("No largest legal super class exists.", MO, MONum);
933              return;
934            }
935            DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
936            if (!DRC) {
937              report("No matching super-reg register class.", MO, MONum);
938              return;
939            }
940          }
941          if (!RC->hasSuperClassEq(DRC)) {
942            report("Illegal virtual register for instruction", MO, MONum);
943            errs() << "Expected a " << TRI->getRegClassName(DRC)
944                << " register, but got a " << TRI->getRegClassName(RC)
945                << " register\n";
946          }
947        }
948      }
949    }
950    break;
951  }
952
953  case MachineOperand::MO_RegisterMask:
954    regMasks.push_back(MO->getRegMask());
955    break;
956
957  case MachineOperand::MO_MachineBasicBlock:
958    if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
959      report("PHI operand is not in the CFG", MO, MONum);
960    break;
961
962  case MachineOperand::MO_FrameIndex:
963    if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
964        LiveInts && !LiveInts->isNotInMIMap(MI)) {
965      LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
966      SlotIndex Idx = LiveInts->getInstructionIndex(MI);
967      if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) {
968        report("Instruction loads from dead spill slot", MO, MONum);
969        errs() << "Live stack: " << LI << '\n';
970      }
971      if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) {
972        report("Instruction stores to dead spill slot", MO, MONum);
973        errs() << "Live stack: " << LI << '\n';
974      }
975    }
976    break;
977
978  default:
979    break;
980  }
981}
982
983void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
984  const MachineInstr *MI = MO->getParent();
985  const unsigned Reg = MO->getReg();
986
987  // Both use and def operands can read a register.
988  if (MO->readsReg()) {
989    regsLiveInButUnused.erase(Reg);
990
991    if (MO->isKill())
992      addRegWithSubRegs(regsKilled, Reg);
993
994    // Check that LiveVars knows this kill.
995    if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
996        MO->isKill()) {
997      LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
998      if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end())
999        report("Kill missing from LiveVariables", MO, MONum);
1000    }
1001
1002    // Check LiveInts liveness and kill.
1003    if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
1004      SlotIndex UseIdx = LiveInts->getInstructionIndex(MI);
1005      // Check the cached regunit intervals.
1006      if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
1007        for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
1008          if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units)) {
1009            LiveQueryResult LRQ = LR->Query(UseIdx);
1010            if (!LRQ.valueIn()) {
1011              report("No live segment at use", MO, MONum);
1012              errs() << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI)
1013                  << ' ' << *LR << '\n';
1014            }
1015            if (MO->isKill() && !LRQ.isKill()) {
1016              report("Live range continues after kill flag", MO, MONum);
1017              errs() << PrintRegUnit(*Units, TRI) << ' ' << *LR << '\n';
1018            }
1019          }
1020        }
1021      }
1022
1023      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1024        if (LiveInts->hasInterval(Reg)) {
1025          // This is a virtual register interval.
1026          const LiveInterval &LI = LiveInts->getInterval(Reg);
1027          LiveQueryResult LRQ = LI.Query(UseIdx);
1028          if (!LRQ.valueIn()) {
1029            report("No live segment at use", MO, MONum);
1030            errs() << UseIdx << " is not live in " << LI << '\n';
1031          }
1032          // Check for extra kill flags.
1033          // Note that we allow missing kill flags for now.
1034          if (MO->isKill() && !LRQ.isKill()) {
1035            report("Live range continues after kill flag", MO, MONum);
1036            errs() << "Live range: " << LI << '\n';
1037          }
1038        } else {
1039          report("Virtual register has no live interval", MO, MONum);
1040        }
1041      }
1042    }
1043
1044    // Use of a dead register.
1045    if (!regsLive.count(Reg)) {
1046      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1047        // Reserved registers may be used even when 'dead'.
1048        bool Bad = !isReserved(Reg);
1049        // We are fine if just any subregister has a defined value.
1050        if (Bad) {
1051          for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid();
1052               ++SubRegs) {
1053            if (regsLive.count(*SubRegs)) {
1054              Bad = false;
1055              break;
1056            }
1057          }
1058        }
1059        // If there is an additional implicit-use of a super register we stop
1060        // here. By definition we are fine if the super register is not
1061        // (completely) dead, if the complete super register is dead we will
1062        // get a report for its operand.
1063        if (Bad) {
1064          for (const MachineOperand &MOP : MI->uses()) {
1065            if (!MOP.isReg())
1066              continue;
1067            if (!MOP.isImplicit())
1068              continue;
1069            for (MCSubRegIterator SubRegs(MOP.getReg(), TRI); SubRegs.isValid();
1070                 ++SubRegs) {
1071              if (*SubRegs == Reg) {
1072                Bad = false;
1073                break;
1074              }
1075            }
1076          }
1077        }
1078        if (Bad)
1079          report("Using an undefined physical register", MO, MONum);
1080      } else if (MRI->def_empty(Reg)) {
1081        report("Reading virtual register without a def", MO, MONum);
1082      } else {
1083        BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1084        // We don't know which virtual registers are live in, so only complain
1085        // if vreg was killed in this MBB. Otherwise keep track of vregs that
1086        // must be live in. PHI instructions are handled separately.
1087        if (MInfo.regsKilled.count(Reg))
1088          report("Using a killed virtual register", MO, MONum);
1089        else if (!MI->isPHI())
1090          MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
1091      }
1092    }
1093  }
1094
1095  if (MO->isDef()) {
1096    // Register defined.
1097    // TODO: verify that earlyclobber ops are not used.
1098    if (MO->isDead())
1099      addRegWithSubRegs(regsDead, Reg);
1100    else
1101      addRegWithSubRegs(regsDefined, Reg);
1102
1103    // Verify SSA form.
1104    if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
1105        std::next(MRI->def_begin(Reg)) != MRI->def_end())
1106      report("Multiple virtual register defs in SSA form", MO, MONum);
1107
1108    // Check LiveInts for a live segment, but only for virtual registers.
1109    if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
1110        !LiveInts->isNotInMIMap(MI)) {
1111      SlotIndex DefIdx = LiveInts->getInstructionIndex(MI);
1112      DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
1113      if (LiveInts->hasInterval(Reg)) {
1114        const LiveInterval &LI = LiveInts->getInterval(Reg);
1115        if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
1116          assert(VNI && "NULL valno is not allowed");
1117          if (VNI->def != DefIdx) {
1118            report("Inconsistent valno->def", MO, MONum);
1119            errs() << "Valno " << VNI->id << " is not defined at "
1120              << DefIdx << " in " << LI << '\n';
1121          }
1122        } else {
1123          report("No live segment at def", MO, MONum);
1124          errs() << DefIdx << " is not live in " << LI << '\n';
1125        }
1126        // Check that, if the dead def flag is present, LiveInts agree.
1127        if (MO->isDead()) {
1128          LiveQueryResult LRQ = LI.Query(DefIdx);
1129          if (!LRQ.isDeadDef()) {
1130            report("Live range continues after dead def flag", MO, MONum);
1131            errs() << "Live range: " << LI << '\n';
1132          }
1133        }
1134      } else {
1135        report("Virtual register has no Live interval", MO, MONum);
1136      }
1137    }
1138  }
1139}
1140
1141void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
1142}
1143
1144// This function gets called after visiting all instructions in a bundle. The
1145// argument points to the bundle header.
1146// Normal stand-alone instructions are also considered 'bundles', and this
1147// function is called for all of them.
1148void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
1149  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1150  set_union(MInfo.regsKilled, regsKilled);
1151  set_subtract(regsLive, regsKilled); regsKilled.clear();
1152  // Kill any masked registers.
1153  while (!regMasks.empty()) {
1154    const uint32_t *Mask = regMasks.pop_back_val();
1155    for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
1156      if (TargetRegisterInfo::isPhysicalRegister(*I) &&
1157          MachineOperand::clobbersPhysReg(Mask, *I))
1158        regsDead.push_back(*I);
1159  }
1160  set_subtract(regsLive, regsDead);   regsDead.clear();
1161  set_union(regsLive, regsDefined);   regsDefined.clear();
1162}
1163
1164void
1165MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
1166  MBBInfoMap[MBB].regsLiveOut = regsLive;
1167  regsLive.clear();
1168
1169  if (Indexes) {
1170    SlotIndex stop = Indexes->getMBBEndIdx(MBB);
1171    if (!(stop > lastIndex)) {
1172      report("Block ends before last instruction index", MBB);
1173      errs() << "Block ends at " << stop
1174          << " last instruction was at " << lastIndex << '\n';
1175    }
1176    lastIndex = stop;
1177  }
1178}
1179
1180// Calculate the largest possible vregsPassed sets. These are the registers that
1181// can pass through an MBB live, but may not be live every time. It is assumed
1182// that all vregsPassed sets are empty before the call.
1183void MachineVerifier::calcRegsPassed() {
1184  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
1185  // have any vregsPassed.
1186  SmallPtrSet<const MachineBasicBlock*, 8> todo;
1187  for (const auto &MBB : *MF) {
1188    BBInfo &MInfo = MBBInfoMap[&MBB];
1189    if (!MInfo.reachable)
1190      continue;
1191    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
1192           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
1193      BBInfo &SInfo = MBBInfoMap[*SuI];
1194      if (SInfo.addPassed(MInfo.regsLiveOut))
1195        todo.insert(*SuI);
1196    }
1197  }
1198
1199  // Iteratively push vregsPassed to successors. This will converge to the same
1200  // final state regardless of DenseSet iteration order.
1201  while (!todo.empty()) {
1202    const MachineBasicBlock *MBB = *todo.begin();
1203    todo.erase(MBB);
1204    BBInfo &MInfo = MBBInfoMap[MBB];
1205    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
1206           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
1207      if (*SuI == MBB)
1208        continue;
1209      BBInfo &SInfo = MBBInfoMap[*SuI];
1210      if (SInfo.addPassed(MInfo.vregsPassed))
1211        todo.insert(*SuI);
1212    }
1213  }
1214}
1215
1216// Calculate the set of virtual registers that must be passed through each basic
1217// block in order to satisfy the requirements of successor blocks. This is very
1218// similar to calcRegsPassed, only backwards.
1219void MachineVerifier::calcRegsRequired() {
1220  // First push live-in regs to predecessors' vregsRequired.
1221  SmallPtrSet<const MachineBasicBlock*, 8> todo;
1222  for (const auto &MBB : *MF) {
1223    BBInfo &MInfo = MBBInfoMap[&MBB];
1224    for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
1225           PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
1226      BBInfo &PInfo = MBBInfoMap[*PrI];
1227      if (PInfo.addRequired(MInfo.vregsLiveIn))
1228        todo.insert(*PrI);
1229    }
1230  }
1231
1232  // Iteratively push vregsRequired to predecessors. This will converge to the
1233  // same final state regardless of DenseSet iteration order.
1234  while (!todo.empty()) {
1235    const MachineBasicBlock *MBB = *todo.begin();
1236    todo.erase(MBB);
1237    BBInfo &MInfo = MBBInfoMap[MBB];
1238    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1239           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1240      if (*PrI == MBB)
1241        continue;
1242      BBInfo &SInfo = MBBInfoMap[*PrI];
1243      if (SInfo.addRequired(MInfo.vregsRequired))
1244        todo.insert(*PrI);
1245    }
1246  }
1247}
1248
1249// Check PHI instructions at the beginning of MBB. It is assumed that
1250// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
1251void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
1252  SmallPtrSet<const MachineBasicBlock*, 8> seen;
1253  for (const auto &BBI : *MBB) {
1254    if (!BBI.isPHI())
1255      break;
1256    seen.clear();
1257
1258    for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
1259      unsigned Reg = BBI.getOperand(i).getReg();
1260      const MachineBasicBlock *Pre = BBI.getOperand(i + 1).getMBB();
1261      if (!Pre->isSuccessor(MBB))
1262        continue;
1263      seen.insert(Pre);
1264      BBInfo &PrInfo = MBBInfoMap[Pre];
1265      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
1266        report("PHI operand is not live-out from predecessor",
1267               &BBI.getOperand(i), i);
1268    }
1269
1270    // Did we see all predecessors?
1271    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1272           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1273      if (!seen.count(*PrI)) {
1274        report("Missing PHI operand", &BBI);
1275        errs() << "BB#" << (*PrI)->getNumber()
1276            << " is a predecessor according to the CFG.\n";
1277      }
1278    }
1279  }
1280}
1281
1282void MachineVerifier::visitMachineFunctionAfter() {
1283  calcRegsPassed();
1284
1285  for (const auto &MBB : *MF) {
1286    BBInfo &MInfo = MBBInfoMap[&MBB];
1287
1288    // Skip unreachable MBBs.
1289    if (!MInfo.reachable)
1290      continue;
1291
1292    checkPHIOps(&MBB);
1293  }
1294
1295  // Now check liveness info if available
1296  calcRegsRequired();
1297
1298  // Check for killed virtual registers that should be live out.
1299  for (const auto &MBB : *MF) {
1300    BBInfo &MInfo = MBBInfoMap[&MBB];
1301    for (RegSet::iterator
1302         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1303         ++I)
1304      if (MInfo.regsKilled.count(*I)) {
1305        report("Virtual register killed in block, but needed live out.", &MBB);
1306        errs() << "Virtual register " << PrintReg(*I)
1307            << " is used after the block.\n";
1308      }
1309  }
1310
1311  if (!MF->empty()) {
1312    BBInfo &MInfo = MBBInfoMap[&MF->front()];
1313    for (RegSet::iterator
1314         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1315         ++I)
1316      report("Virtual register def doesn't dominate all uses.",
1317             MRI->getVRegDef(*I));
1318  }
1319
1320  if (LiveVars)
1321    verifyLiveVariables();
1322  if (LiveInts)
1323    verifyLiveIntervals();
1324}
1325
1326void MachineVerifier::verifyLiveVariables() {
1327  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
1328  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1329    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1330    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1331    for (const auto &MBB : *MF) {
1332      BBInfo &MInfo = MBBInfoMap[&MBB];
1333
1334      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1335      if (MInfo.vregsRequired.count(Reg)) {
1336        if (!VI.AliveBlocks.test(MBB.getNumber())) {
1337          report("LiveVariables: Block missing from AliveBlocks", &MBB);
1338          errs() << "Virtual register " << PrintReg(Reg)
1339              << " must be live through the block.\n";
1340        }
1341      } else {
1342        if (VI.AliveBlocks.test(MBB.getNumber())) {
1343          report("LiveVariables: Block should not be in AliveBlocks", &MBB);
1344          errs() << "Virtual register " << PrintReg(Reg)
1345              << " is not needed live through the block.\n";
1346        }
1347      }
1348    }
1349  }
1350}
1351
1352void MachineVerifier::verifyLiveIntervals() {
1353  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
1354  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1355    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1356
1357    // Spilling and splitting may leave unused registers around. Skip them.
1358    if (MRI->reg_nodbg_empty(Reg))
1359      continue;
1360
1361    if (!LiveInts->hasInterval(Reg)) {
1362      report("Missing live interval for virtual register", MF);
1363      errs() << PrintReg(Reg, TRI) << " still has defs or uses\n";
1364      continue;
1365    }
1366
1367    const LiveInterval &LI = LiveInts->getInterval(Reg);
1368    assert(Reg == LI.reg && "Invalid reg to interval mapping");
1369    verifyLiveInterval(LI);
1370  }
1371
1372  // Verify all the cached regunit intervals.
1373  for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
1374    if (const LiveRange *LR = LiveInts->getCachedRegUnit(i))
1375      verifyLiveRange(*LR, i);
1376}
1377
1378void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR,
1379                                           const VNInfo *VNI, unsigned Reg,
1380                                           unsigned LaneMask) {
1381  if (VNI->isUnused())
1382    return;
1383
1384  const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def);
1385
1386  if (!DefVNI) {
1387    report("Valno not live at def and not marked unused", MF, LR, Reg,
1388           LaneMask);
1389    errs() << "Valno #" << VNI->id << '\n';
1390    return;
1391  }
1392
1393  if (DefVNI != VNI) {
1394    report("Live segment at def has different valno", MF, LR, Reg, LaneMask);
1395    errs() << "Valno #" << VNI->id << " is defined at " << VNI->def
1396        << " where valno #" << DefVNI->id << " is live\n";
1397    return;
1398  }
1399
1400  const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1401  if (!MBB) {
1402    report("Invalid definition index", MF, LR, Reg, LaneMask);
1403    errs() << "Valno #" << VNI->id << " is defined at " << VNI->def
1404        << " in " << LR << '\n';
1405    return;
1406  }
1407
1408  if (VNI->isPHIDef()) {
1409    if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1410      report("PHIDef value is not defined at MBB start", MBB, LR, Reg,
1411             LaneMask);
1412      errs() << "Valno #" << VNI->id << " is defined at " << VNI->def
1413          << ", not at the beginning of BB#" << MBB->getNumber() << '\n';
1414    }
1415    return;
1416  }
1417
1418  // Non-PHI def.
1419  const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1420  if (!MI) {
1421    report("No instruction at def index", MBB, LR, Reg, LaneMask);
1422    errs() << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1423    return;
1424  }
1425
1426  if (Reg != 0) {
1427    bool hasDef = false;
1428    bool isEarlyClobber = false;
1429    for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1430      if (!MOI->isReg() || !MOI->isDef())
1431        continue;
1432      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1433        if (MOI->getReg() != Reg)
1434          continue;
1435      } else {
1436        if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1437            !TRI->hasRegUnit(MOI->getReg(), Reg))
1438          continue;
1439      }
1440      if (LaneMask != 0 &&
1441          (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask) == 0)
1442        continue;
1443      hasDef = true;
1444      if (MOI->isEarlyClobber())
1445        isEarlyClobber = true;
1446    }
1447
1448    if (!hasDef) {
1449      report("Defining instruction does not modify register", MI);
1450      errs() << "Valno #" << VNI->id << " in " << LR << '\n';
1451    }
1452
1453    // Early clobber defs begin at USE slots, but other defs must begin at
1454    // DEF slots.
1455    if (isEarlyClobber) {
1456      if (!VNI->def.isEarlyClobber()) {
1457        report("Early clobber def must be at an early-clobber slot", MBB, LR,
1458               Reg, LaneMask);
1459        errs() << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1460      }
1461    } else if (!VNI->def.isRegister()) {
1462      report("Non-PHI, non-early clobber def must be at a register slot",
1463             MBB, LR, Reg, LaneMask);
1464      errs() << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1465    }
1466  }
1467}
1468
1469void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
1470                                             const LiveRange::const_iterator I,
1471                                             unsigned Reg, unsigned LaneMask) {
1472  const LiveRange::Segment &S = *I;
1473  const VNInfo *VNI = S.valno;
1474  assert(VNI && "Live segment has no valno");
1475
1476  if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) {
1477    report("Foreign valno in live segment", MF, LR, Reg, LaneMask);
1478    errs() << S << " has a bad valno\n";
1479  }
1480
1481  if (VNI->isUnused()) {
1482    report("Live segment valno is marked unused", MF, LR, Reg, LaneMask);
1483    errs() << S << '\n';
1484  }
1485
1486  const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start);
1487  if (!MBB) {
1488    report("Bad start of live segment, no basic block", MF, LR, Reg, LaneMask);
1489    errs() << S << '\n';
1490    return;
1491  }
1492  SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1493  if (S.start != MBBStartIdx && S.start != VNI->def) {
1494    report("Live segment must begin at MBB entry or valno def", MBB, LR, Reg,
1495           LaneMask);
1496    errs() << S << '\n';
1497  }
1498
1499  const MachineBasicBlock *EndMBB =
1500    LiveInts->getMBBFromIndex(S.end.getPrevSlot());
1501  if (!EndMBB) {
1502    report("Bad end of live segment, no basic block", MF, LR, Reg, LaneMask);
1503    errs() << S << '\n';
1504    return;
1505  }
1506
1507  // No more checks for live-out segments.
1508  if (S.end == LiveInts->getMBBEndIdx(EndMBB))
1509    return;
1510
1511  // RegUnit intervals are allowed dead phis.
1512  if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() &&
1513      S.start == VNI->def && S.end == VNI->def.getDeadSlot())
1514    return;
1515
1516  // The live segment is ending inside EndMBB
1517  const MachineInstr *MI =
1518    LiveInts->getInstructionFromIndex(S.end.getPrevSlot());
1519  if (!MI) {
1520    report("Live segment doesn't end at a valid instruction", EndMBB, LR, Reg,
1521           LaneMask);
1522    errs() << S << '\n';
1523    return;
1524  }
1525
1526  // The block slot must refer to a basic block boundary.
1527  if (S.end.isBlock()) {
1528    report("Live segment ends at B slot of an instruction", EndMBB, LR, Reg,
1529           LaneMask);
1530    errs() << S << '\n';
1531  }
1532
1533  if (S.end.isDead()) {
1534    // Segment ends on the dead slot.
1535    // That means there must be a dead def.
1536    if (!SlotIndex::isSameInstr(S.start, S.end)) {
1537      report("Live segment ending at dead slot spans instructions", EndMBB, LR,
1538             Reg, LaneMask);
1539      errs() << S << '\n';
1540    }
1541  }
1542
1543  // A live segment can only end at an early-clobber slot if it is being
1544  // redefined by an early-clobber def.
1545  if (S.end.isEarlyClobber()) {
1546    if (I+1 == LR.end() || (I+1)->start != S.end) {
1547      report("Live segment ending at early clobber slot must be "
1548             "redefined by an EC def in the same instruction", EndMBB, LR, Reg,
1549             LaneMask);
1550      errs() << S << '\n';
1551    }
1552  }
1553
1554  // The following checks only apply to virtual registers. Physreg liveness
1555  // is too weird to check.
1556  if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1557    // A live segment can end with either a redefinition, a kill flag on a
1558    // use, or a dead flag on a def.
1559    bool hasRead = false;
1560    bool hasSubRegDef = false;
1561    for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1562      if (!MOI->isReg() || MOI->getReg() != Reg)
1563        continue;
1564      if (LaneMask != 0 &&
1565          (LaneMask & TRI->getSubRegIndexLaneMask(MOI->getSubReg())) == 0)
1566        continue;
1567      if (MOI->isDef() && MOI->getSubReg() != 0)
1568        hasSubRegDef = true;
1569      if (MOI->readsReg())
1570        hasRead = true;
1571    }
1572    if (!S.end.isDead()) {
1573      if (!hasRead) {
1574        // When tracking subregister liveness, the main range must start new
1575        // values on partial register writes, even if there is no read.
1576        if (!MRI->shouldTrackSubRegLiveness(Reg) || LaneMask != 0 ||
1577            !hasSubRegDef) {
1578          report("Instruction ending live segment doesn't read the register",
1579                 MI);
1580          errs() << S << " in " << LR << '\n';
1581        }
1582      }
1583    }
1584  }
1585
1586  // Now check all the basic blocks in this live segment.
1587  MachineFunction::const_iterator MFI = MBB;
1588  // Is this live segment the beginning of a non-PHIDef VN?
1589  if (S.start == VNI->def && !VNI->isPHIDef()) {
1590    // Not live-in to any blocks.
1591    if (MBB == EndMBB)
1592      return;
1593    // Skip this block.
1594    ++MFI;
1595  }
1596  for (;;) {
1597    assert(LiveInts->isLiveInToMBB(LR, MFI));
1598    // We don't know how to track physregs into a landing pad.
1599    if (!TargetRegisterInfo::isVirtualRegister(Reg) &&
1600        MFI->isLandingPad()) {
1601      if (&*MFI == EndMBB)
1602        break;
1603      ++MFI;
1604      continue;
1605    }
1606
1607    // Is VNI a PHI-def in the current block?
1608    bool IsPHI = VNI->isPHIDef() &&
1609      VNI->def == LiveInts->getMBBStartIdx(MFI);
1610
1611    // Check that VNI is live-out of all predecessors.
1612    for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1613         PE = MFI->pred_end(); PI != PE; ++PI) {
1614      SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
1615      const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
1616
1617      // All predecessors must have a live-out value.
1618      if (!PVNI) {
1619        report("Register not marked live out of predecessor", *PI, LR, Reg,
1620               LaneMask);
1621        errs() << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1622            << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
1623            << PEnd << '\n';
1624        continue;
1625      }
1626
1627      // Only PHI-defs can take different predecessor values.
1628      if (!IsPHI && PVNI != VNI) {
1629        report("Different value live out of predecessor", *PI, LR, Reg,
1630               LaneMask);
1631        errs() << "Valno #" << PVNI->id << " live out of BB#"
1632            << (*PI)->getNumber() << '@' << PEnd
1633            << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1634            << '@' << LiveInts->getMBBStartIdx(MFI) << '\n';
1635      }
1636    }
1637    if (&*MFI == EndMBB)
1638      break;
1639    ++MFI;
1640  }
1641}
1642
1643void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg,
1644                                      unsigned LaneMask) {
1645  for (const VNInfo *VNI : LR.valnos)
1646    verifyLiveRangeValue(LR, VNI, Reg, LaneMask);
1647
1648  for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I)
1649    verifyLiveRangeSegment(LR, I, Reg, LaneMask);
1650}
1651
1652void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
1653  unsigned Reg = LI.reg;
1654  assert(TargetRegisterInfo::isVirtualRegister(Reg));
1655  verifyLiveRange(LI, Reg);
1656
1657  unsigned Mask = 0;
1658  unsigned MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
1659  for (const LiveInterval::SubRange &SR : LI.subranges()) {
1660    if ((Mask & SR.LaneMask) != 0)
1661      report("Lane masks of sub ranges overlap in live interval", MF, LI);
1662    if ((SR.LaneMask & ~MaxMask) != 0)
1663      report("Subrange lanemask is invalid", MF, LI);
1664    Mask |= SR.LaneMask;
1665    verifyLiveRange(SR, LI.reg, SR.LaneMask);
1666    if (!LI.covers(SR))
1667      report("A Subrange is not covered by the main range", MF, LI);
1668  }
1669
1670  // Check the LI only has one connected component.
1671  ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1672  unsigned NumComp = ConEQ.Classify(&LI);
1673  if (NumComp > 1) {
1674    report("Multiple connected components in live interval", MF, LI);
1675    for (unsigned comp = 0; comp != NumComp; ++comp) {
1676      errs() << comp << ": valnos";
1677      for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1678           E = LI.vni_end(); I!=E; ++I)
1679        if (comp == ConEQ.getEqClass(*I))
1680          errs() << ' ' << (*I)->id;
1681      errs() << '\n';
1682    }
1683  }
1684}
1685
1686namespace {
1687  // FrameSetup and FrameDestroy can have zero adjustment, so using a single
1688  // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
1689  // value is zero.
1690  // We use a bool plus an integer to capture the stack state.
1691  struct StackStateOfBB {
1692    StackStateOfBB() : EntryValue(0), ExitValue(0), EntryIsSetup(false),
1693      ExitIsSetup(false) { }
1694    StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
1695      EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
1696      ExitIsSetup(ExitSetup) { }
1697    // Can be negative, which means we are setting up a frame.
1698    int EntryValue;
1699    int ExitValue;
1700    bool EntryIsSetup;
1701    bool ExitIsSetup;
1702  };
1703}
1704
1705/// Make sure on every path through the CFG, a FrameSetup <n> is always followed
1706/// by a FrameDestroy <n>, stack adjustments are identical on all
1707/// CFG edges to a merge point, and frame is destroyed at end of a return block.
1708void MachineVerifier::verifyStackFrame() {
1709  int FrameSetupOpcode   = TII->getCallFrameSetupOpcode();
1710  int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
1711
1712  SmallVector<StackStateOfBB, 8> SPState;
1713  SPState.resize(MF->getNumBlockIDs());
1714  SmallPtrSet<const MachineBasicBlock*, 8> Reachable;
1715
1716  // Visit the MBBs in DFS order.
1717  for (df_ext_iterator<const MachineFunction*,
1718                       SmallPtrSet<const MachineBasicBlock*, 8> >
1719       DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
1720       DFI != DFE; ++DFI) {
1721    const MachineBasicBlock *MBB = *DFI;
1722
1723    StackStateOfBB BBState;
1724    // Check the exit state of the DFS stack predecessor.
1725    if (DFI.getPathLength() >= 2) {
1726      const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
1727      assert(Reachable.count(StackPred) &&
1728             "DFS stack predecessor is already visited.\n");
1729      BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
1730      BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
1731      BBState.ExitValue = BBState.EntryValue;
1732      BBState.ExitIsSetup = BBState.EntryIsSetup;
1733    }
1734
1735    // Update stack state by checking contents of MBB.
1736    for (const auto &I : *MBB) {
1737      if (I.getOpcode() == FrameSetupOpcode) {
1738        // The first operand of a FrameOpcode should be i32.
1739        int Size = I.getOperand(0).getImm();
1740        assert(Size >= 0 &&
1741          "Value should be non-negative in FrameSetup and FrameDestroy.\n");
1742
1743        if (BBState.ExitIsSetup)
1744          report("FrameSetup is after another FrameSetup", &I);
1745        BBState.ExitValue -= Size;
1746        BBState.ExitIsSetup = true;
1747      }
1748
1749      if (I.getOpcode() == FrameDestroyOpcode) {
1750        // The first operand of a FrameOpcode should be i32.
1751        int Size = I.getOperand(0).getImm();
1752        assert(Size >= 0 &&
1753          "Value should be non-negative in FrameSetup and FrameDestroy.\n");
1754
1755        if (!BBState.ExitIsSetup)
1756          report("FrameDestroy is not after a FrameSetup", &I);
1757        int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
1758                                               BBState.ExitValue;
1759        if (BBState.ExitIsSetup && AbsSPAdj != Size) {
1760          report("FrameDestroy <n> is after FrameSetup <m>", &I);
1761          errs() << "FrameDestroy <" << Size << "> is after FrameSetup <"
1762              << AbsSPAdj << ">.\n";
1763        }
1764        BBState.ExitValue += Size;
1765        BBState.ExitIsSetup = false;
1766      }
1767    }
1768    SPState[MBB->getNumber()] = BBState;
1769
1770    // Make sure the exit state of any predecessor is consistent with the entry
1771    // state.
1772    for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
1773         E = MBB->pred_end(); I != E; ++I) {
1774      if (Reachable.count(*I) &&
1775          (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue ||
1776           SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
1777        report("The exit stack state of a predecessor is inconsistent.", MBB);
1778        errs() << "Predecessor BB#" << (*I)->getNumber() << " has exit state ("
1779            << SPState[(*I)->getNumber()].ExitValue << ", "
1780            << SPState[(*I)->getNumber()].ExitIsSetup
1781            << "), while BB#" << MBB->getNumber() << " has entry state ("
1782            << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
1783      }
1784    }
1785
1786    // Make sure the entry state of any successor is consistent with the exit
1787    // state.
1788    for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
1789         E = MBB->succ_end(); I != E; ++I) {
1790      if (Reachable.count(*I) &&
1791          (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue ||
1792           SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
1793        report("The entry stack state of a successor is inconsistent.", MBB);
1794        errs() << "Successor BB#" << (*I)->getNumber() << " has entry state ("
1795            << SPState[(*I)->getNumber()].EntryValue << ", "
1796            << SPState[(*I)->getNumber()].EntryIsSetup
1797            << "), while BB#" << MBB->getNumber() << " has exit state ("
1798            << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
1799      }
1800    }
1801
1802    // Make sure a basic block with return ends with zero stack adjustment.
1803    if (!MBB->empty() && MBB->back().isReturn()) {
1804      if (BBState.ExitIsSetup)
1805        report("A return block ends with a FrameSetup.", MBB);
1806      if (BBState.ExitValue)
1807        report("A return block ends with a nonzero stack adjustment.", MBB);
1808    }
1809  }
1810}
1811