xref: /llvm-project/llvm/lib/CodeGen/MachineVerifier.cpp (revision 74de21d06f1137ba26b52e929d58c7f50c481866)
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 "LiveRangeCalc.h"
27 #include "llvm/ADT/BitVector.h"
28 #include "llvm/ADT/DenseMap.h"
29 #include "llvm/ADT/DenseSet.h"
30 #include "llvm/ADT/DepthFirstIterator.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/ADT/SetOperations.h"
33 #include "llvm/ADT/SmallPtrSet.h"
34 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/ADT/StringRef.h"
36 #include "llvm/ADT/Twine.h"
37 #include "llvm/Analysis/EHPersonalities.h"
38 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
39 #include "llvm/CodeGen/LiveInterval.h"
40 #include "llvm/CodeGen/LiveIntervals.h"
41 #include "llvm/CodeGen/LiveStacks.h"
42 #include "llvm/CodeGen/LiveVariables.h"
43 #include "llvm/CodeGen/MachineBasicBlock.h"
44 #include "llvm/CodeGen/MachineFrameInfo.h"
45 #include "llvm/CodeGen/MachineFunction.h"
46 #include "llvm/CodeGen/MachineFunctionPass.h"
47 #include "llvm/CodeGen/MachineInstr.h"
48 #include "llvm/CodeGen/MachineInstrBundle.h"
49 #include "llvm/CodeGen/MachineMemOperand.h"
50 #include "llvm/CodeGen/MachineOperand.h"
51 #include "llvm/CodeGen/MachineRegisterInfo.h"
52 #include "llvm/CodeGen/PseudoSourceValue.h"
53 #include "llvm/CodeGen/SlotIndexes.h"
54 #include "llvm/CodeGen/StackMaps.h"
55 #include "llvm/CodeGen/TargetInstrInfo.h"
56 #include "llvm/CodeGen/TargetOpcodes.h"
57 #include "llvm/CodeGen/TargetRegisterInfo.h"
58 #include "llvm/CodeGen/TargetSubtargetInfo.h"
59 #include "llvm/IR/BasicBlock.h"
60 #include "llvm/IR/Function.h"
61 #include "llvm/IR/InlineAsm.h"
62 #include "llvm/IR/Instructions.h"
63 #include "llvm/MC/LaneBitmask.h"
64 #include "llvm/MC/MCAsmInfo.h"
65 #include "llvm/MC/MCInstrDesc.h"
66 #include "llvm/MC/MCRegisterInfo.h"
67 #include "llvm/MC/MCTargetOptions.h"
68 #include "llvm/Pass.h"
69 #include "llvm/Support/Casting.h"
70 #include "llvm/Support/ErrorHandling.h"
71 #include "llvm/Support/LowLevelTypeImpl.h"
72 #include "llvm/Support/MathExtras.h"
73 #include "llvm/Support/raw_ostream.h"
74 #include "llvm/Target/TargetMachine.h"
75 #include <algorithm>
76 #include <cassert>
77 #include <cstddef>
78 #include <cstdint>
79 #include <iterator>
80 #include <string>
81 #include <utility>
82 
83 using namespace llvm;
84 
85 namespace {
86 
87   struct MachineVerifier {
88     MachineVerifier(Pass *pass, const char *b) : PASS(pass), Banner(b) {}
89 
90     unsigned verify(MachineFunction &MF);
91 
92     Pass *const PASS;
93     const char *Banner;
94     const MachineFunction *MF;
95     const TargetMachine *TM;
96     const TargetInstrInfo *TII;
97     const TargetRegisterInfo *TRI;
98     const MachineRegisterInfo *MRI;
99 
100     unsigned foundErrors;
101 
102     // Avoid querying the MachineFunctionProperties for each operand.
103     bool isFunctionRegBankSelected;
104     bool isFunctionSelected;
105 
106     using RegVector = SmallVector<unsigned, 16>;
107     using RegMaskVector = SmallVector<const uint32_t *, 4>;
108     using RegSet = DenseSet<unsigned>;
109     using RegMap = DenseMap<unsigned, const MachineInstr *>;
110     using BlockSet = SmallPtrSet<const MachineBasicBlock *, 8>;
111 
112     const MachineInstr *FirstTerminator;
113     BlockSet FunctionBlocks;
114 
115     BitVector regsReserved;
116     RegSet regsLive;
117     RegVector regsDefined, regsDead, regsKilled;
118     RegMaskVector regMasks;
119 
120     SlotIndex lastIndex;
121 
122     // Add Reg and any sub-registers to RV
123     void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
124       RV.push_back(Reg);
125       if (TargetRegisterInfo::isPhysicalRegister(Reg))
126         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
127           RV.push_back(*SubRegs);
128     }
129 
130     struct BBInfo {
131       // Is this MBB reachable from the MF entry point?
132       bool reachable = false;
133 
134       // Vregs that must be live in because they are used without being
135       // defined. Map value is the user.
136       RegMap vregsLiveIn;
137 
138       // Regs killed in MBB. They may be defined again, and will then be in both
139       // regsKilled and regsLiveOut.
140       RegSet regsKilled;
141 
142       // Regs defined in MBB and live out. Note that vregs passing through may
143       // be live out without being mentioned here.
144       RegSet regsLiveOut;
145 
146       // Vregs that pass through MBB untouched. This set is disjoint from
147       // regsKilled and regsLiveOut.
148       RegSet vregsPassed;
149 
150       // Vregs that must pass through MBB because they are needed by a successor
151       // block. This set is disjoint from regsLiveOut.
152       RegSet vregsRequired;
153 
154       // Set versions of block's predecessor and successor lists.
155       BlockSet Preds, Succs;
156 
157       BBInfo() = default;
158 
159       // Add register to vregsPassed if it belongs there. Return true if
160       // anything changed.
161       bool addPassed(unsigned Reg) {
162         if (!TargetRegisterInfo::isVirtualRegister(Reg))
163           return false;
164         if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
165           return false;
166         return vregsPassed.insert(Reg).second;
167       }
168 
169       // Same for a full set.
170       bool addPassed(const RegSet &RS) {
171         bool changed = false;
172         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
173           if (addPassed(*I))
174             changed = true;
175         return changed;
176       }
177 
178       // Add register to vregsRequired if it belongs there. Return true if
179       // anything changed.
180       bool addRequired(unsigned Reg) {
181         if (!TargetRegisterInfo::isVirtualRegister(Reg))
182           return false;
183         if (regsLiveOut.count(Reg))
184           return false;
185         return vregsRequired.insert(Reg).second;
186       }
187 
188       // Same for a full set.
189       bool addRequired(const RegSet &RS) {
190         bool changed = false;
191         for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
192           if (addRequired(*I))
193             changed = true;
194         return changed;
195       }
196 
197       // Same for a full map.
198       bool addRequired(const RegMap &RM) {
199         bool changed = false;
200         for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
201           if (addRequired(I->first))
202             changed = true;
203         return changed;
204       }
205 
206       // Live-out registers are either in regsLiveOut or vregsPassed.
207       bool isLiveOut(unsigned Reg) const {
208         return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
209       }
210     };
211 
212     // Extra register info per MBB.
213     DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
214 
215     bool isReserved(unsigned Reg) {
216       return Reg < regsReserved.size() && regsReserved.test(Reg);
217     }
218 
219     bool isAllocatable(unsigned Reg) const {
220       return Reg < TRI->getNumRegs() && TRI->isInAllocatableClass(Reg) &&
221         !regsReserved.test(Reg);
222     }
223 
224     // Analysis information if available
225     LiveVariables *LiveVars;
226     LiveIntervals *LiveInts;
227     LiveStacks *LiveStks;
228     SlotIndexes *Indexes;
229 
230     void visitMachineFunctionBefore();
231     void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
232     void visitMachineBundleBefore(const MachineInstr *MI);
233     void visitMachineInstrBefore(const MachineInstr *MI);
234     void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
235     void visitMachineInstrAfter(const MachineInstr *MI);
236     void visitMachineBundleAfter(const MachineInstr *MI);
237     void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
238     void visitMachineFunctionAfter();
239 
240     void report(const char *msg, const MachineFunction *MF);
241     void report(const char *msg, const MachineBasicBlock *MBB);
242     void report(const char *msg, const MachineInstr *MI);
243     void report(const char *msg, const MachineOperand *MO, unsigned MONum,
244                 LLT MOVRegType = LLT{});
245 
246     void report_context(const LiveInterval &LI) const;
247     void report_context(const LiveRange &LR, unsigned VRegUnit,
248                         LaneBitmask LaneMask) const;
249     void report_context(const LiveRange::Segment &S) const;
250     void report_context(const VNInfo &VNI) const;
251     void report_context(SlotIndex Pos) const;
252     void report_context_liverange(const LiveRange &LR) const;
253     void report_context_lanemask(LaneBitmask LaneMask) const;
254     void report_context_vreg(unsigned VReg) const;
255     void report_context_vreg_regunit(unsigned VRegOrUnit) const;
256 
257     void verifyInlineAsm(const MachineInstr *MI);
258 
259     void checkLiveness(const MachineOperand *MO, unsigned MONum);
260     void checkLivenessAtUse(const MachineOperand *MO, unsigned MONum,
261                             SlotIndex UseIdx, const LiveRange &LR, unsigned VRegOrUnit,
262                             LaneBitmask LaneMask = LaneBitmask::getNone());
263     void checkLivenessAtDef(const MachineOperand *MO, unsigned MONum,
264                             SlotIndex DefIdx, const LiveRange &LR, unsigned VRegOrUnit,
265                             bool SubRangeCheck = false,
266                             LaneBitmask LaneMask = LaneBitmask::getNone());
267 
268     void markReachable(const MachineBasicBlock *MBB);
269     void calcRegsPassed();
270     void checkPHIOps(const MachineBasicBlock &MBB);
271 
272     void calcRegsRequired();
273     void verifyLiveVariables();
274     void verifyLiveIntervals();
275     void verifyLiveInterval(const LiveInterval&);
276     void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned,
277                               LaneBitmask);
278     void verifyLiveRangeSegment(const LiveRange&,
279                                 const LiveRange::const_iterator I, unsigned,
280                                 LaneBitmask);
281     void verifyLiveRange(const LiveRange&, unsigned,
282                          LaneBitmask LaneMask = LaneBitmask::getNone());
283 
284     void verifyStackFrame();
285 
286     void verifySlotIndexes() const;
287     void verifyProperties(const MachineFunction &MF);
288   };
289 
290   struct MachineVerifierPass : public MachineFunctionPass {
291     static char ID; // Pass ID, replacement for typeid
292 
293     const std::string Banner;
294 
295     MachineVerifierPass(std::string banner = std::string())
296       : MachineFunctionPass(ID), Banner(std::move(banner)) {
297         initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
298       }
299 
300     void getAnalysisUsage(AnalysisUsage &AU) const override {
301       AU.setPreservesAll();
302       MachineFunctionPass::getAnalysisUsage(AU);
303     }
304 
305     bool runOnMachineFunction(MachineFunction &MF) override {
306       unsigned FoundErrors = MachineVerifier(this, Banner.c_str()).verify(MF);
307       if (FoundErrors)
308         report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
309       return false;
310     }
311   };
312 
313 } // end anonymous namespace
314 
315 char MachineVerifierPass::ID = 0;
316 
317 INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
318                 "Verify generated machine code", false, false)
319 
320 FunctionPass *llvm::createMachineVerifierPass(const std::string &Banner) {
321   return new MachineVerifierPass(Banner);
322 }
323 
324 bool MachineFunction::verify(Pass *p, const char *Banner, bool AbortOnErrors)
325     const {
326   MachineFunction &MF = const_cast<MachineFunction&>(*this);
327   unsigned FoundErrors = MachineVerifier(p, Banner).verify(MF);
328   if (AbortOnErrors && FoundErrors)
329     report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
330   return FoundErrors == 0;
331 }
332 
333 void MachineVerifier::verifySlotIndexes() const {
334   if (Indexes == nullptr)
335     return;
336 
337   // Ensure the IdxMBB list is sorted by slot indexes.
338   SlotIndex Last;
339   for (SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(),
340        E = Indexes->MBBIndexEnd(); I != E; ++I) {
341     assert(!Last.isValid() || I->first > Last);
342     Last = I->first;
343   }
344 }
345 
346 void MachineVerifier::verifyProperties(const MachineFunction &MF) {
347   // If a pass has introduced virtual registers without clearing the
348   // NoVRegs property (or set it without allocating the vregs)
349   // then report an error.
350   if (MF.getProperties().hasProperty(
351           MachineFunctionProperties::Property::NoVRegs) &&
352       MRI->getNumVirtRegs())
353     report("Function has NoVRegs property but there are VReg operands", &MF);
354 }
355 
356 unsigned MachineVerifier::verify(MachineFunction &MF) {
357   foundErrors = 0;
358 
359   this->MF = &MF;
360   TM = &MF.getTarget();
361   TII = MF.getSubtarget().getInstrInfo();
362   TRI = MF.getSubtarget().getRegisterInfo();
363   MRI = &MF.getRegInfo();
364 
365   const bool isFunctionFailedISel = MF.getProperties().hasProperty(
366       MachineFunctionProperties::Property::FailedISel);
367 
368   // If we're mid-GlobalISel and we already triggered the fallback path then
369   // it's expected that the MIR is somewhat broken but that's ok since we'll
370   // reset it and clear the FailedISel attribute in ResetMachineFunctions.
371   if (isFunctionFailedISel)
372     return foundErrors;
373 
374   isFunctionRegBankSelected =
375       !isFunctionFailedISel &&
376       MF.getProperties().hasProperty(
377           MachineFunctionProperties::Property::RegBankSelected);
378   isFunctionSelected = !isFunctionFailedISel &&
379                        MF.getProperties().hasProperty(
380                            MachineFunctionProperties::Property::Selected);
381   LiveVars = nullptr;
382   LiveInts = nullptr;
383   LiveStks = nullptr;
384   Indexes = nullptr;
385   if (PASS) {
386     LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
387     // We don't want to verify LiveVariables if LiveIntervals is available.
388     if (!LiveInts)
389       LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
390     LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
391     Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
392   }
393 
394   verifySlotIndexes();
395 
396   verifyProperties(MF);
397 
398   visitMachineFunctionBefore();
399   for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
400        MFI!=MFE; ++MFI) {
401     visitMachineBasicBlockBefore(&*MFI);
402     // Keep track of the current bundle header.
403     const MachineInstr *CurBundle = nullptr;
404     // Do we expect the next instruction to be part of the same bundle?
405     bool InBundle = false;
406 
407     for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
408            MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
409       if (MBBI->getParent() != &*MFI) {
410         report("Bad instruction parent pointer", &*MFI);
411         errs() << "Instruction: " << *MBBI;
412         continue;
413       }
414 
415       // Check for consistent bundle flags.
416       if (InBundle && !MBBI->isBundledWithPred())
417         report("Missing BundledPred flag, "
418                "BundledSucc was set on predecessor",
419                &*MBBI);
420       if (!InBundle && MBBI->isBundledWithPred())
421         report("BundledPred flag is set, "
422                "but BundledSucc not set on predecessor",
423                &*MBBI);
424 
425       // Is this a bundle header?
426       if (!MBBI->isInsideBundle()) {
427         if (CurBundle)
428           visitMachineBundleAfter(CurBundle);
429         CurBundle = &*MBBI;
430         visitMachineBundleBefore(CurBundle);
431       } else if (!CurBundle)
432         report("No bundle header", &*MBBI);
433       visitMachineInstrBefore(&*MBBI);
434       for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) {
435         const MachineInstr &MI = *MBBI;
436         const MachineOperand &Op = MI.getOperand(I);
437         if (Op.getParent() != &MI) {
438           // Make sure to use correct addOperand / RemoveOperand / ChangeTo
439           // functions when replacing operands of a MachineInstr.
440           report("Instruction has operand with wrong parent set", &MI);
441         }
442 
443         visitMachineOperand(&Op, I);
444       }
445 
446       visitMachineInstrAfter(&*MBBI);
447 
448       // Was this the last bundled instruction?
449       InBundle = MBBI->isBundledWithSucc();
450     }
451     if (CurBundle)
452       visitMachineBundleAfter(CurBundle);
453     if (InBundle)
454       report("BundledSucc flag set on last instruction in block", &MFI->back());
455     visitMachineBasicBlockAfter(&*MFI);
456   }
457   visitMachineFunctionAfter();
458 
459   // Clean up.
460   regsLive.clear();
461   regsDefined.clear();
462   regsDead.clear();
463   regsKilled.clear();
464   regMasks.clear();
465   MBBInfoMap.clear();
466 
467   return foundErrors;
468 }
469 
470 void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
471   assert(MF);
472   errs() << '\n';
473   if (!foundErrors++) {
474     if (Banner)
475       errs() << "# " << Banner << '\n';
476     if (LiveInts != nullptr)
477       LiveInts->print(errs());
478     else
479       MF->print(errs(), Indexes);
480   }
481   errs() << "*** Bad machine code: " << msg << " ***\n"
482       << "- function:    " << MF->getName() << "\n";
483 }
484 
485 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
486   assert(MBB);
487   report(msg, MBB->getParent());
488   errs() << "- basic block: " << printMBBReference(*MBB) << ' '
489          << MBB->getName() << " (" << (const void *)MBB << ')';
490   if (Indexes)
491     errs() << " [" << Indexes->getMBBStartIdx(MBB)
492         << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
493   errs() << '\n';
494 }
495 
496 void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
497   assert(MI);
498   report(msg, MI->getParent());
499   errs() << "- instruction: ";
500   if (Indexes && Indexes->hasIndex(*MI))
501     errs() << Indexes->getInstructionIndex(*MI) << '\t';
502   MI->print(errs(), /*SkipOpers=*/true);
503 }
504 
505 void MachineVerifier::report(const char *msg, const MachineOperand *MO,
506                              unsigned MONum, LLT MOVRegType) {
507   assert(MO);
508   report(msg, MO->getParent());
509   errs() << "- operand " << MONum << ":   ";
510   MO->print(errs(), MOVRegType, TRI);
511   errs() << "\n";
512 }
513 
514 void MachineVerifier::report_context(SlotIndex Pos) const {
515   errs() << "- at:          " << Pos << '\n';
516 }
517 
518 void MachineVerifier::report_context(const LiveInterval &LI) const {
519   errs() << "- interval:    " << LI << '\n';
520 }
521 
522 void MachineVerifier::report_context(const LiveRange &LR, unsigned VRegUnit,
523                                      LaneBitmask LaneMask) const {
524   report_context_liverange(LR);
525   report_context_vreg_regunit(VRegUnit);
526   if (LaneMask.any())
527     report_context_lanemask(LaneMask);
528 }
529 
530 void MachineVerifier::report_context(const LiveRange::Segment &S) const {
531   errs() << "- segment:     " << S << '\n';
532 }
533 
534 void MachineVerifier::report_context(const VNInfo &VNI) const {
535   errs() << "- ValNo:       " << VNI.id << " (def " << VNI.def << ")\n";
536 }
537 
538 void MachineVerifier::report_context_liverange(const LiveRange &LR) const {
539   errs() << "- liverange:   " << LR << '\n';
540 }
541 
542 void MachineVerifier::report_context_vreg(unsigned VReg) const {
543   errs() << "- v. register: " << printReg(VReg, TRI) << '\n';
544 }
545 
546 void MachineVerifier::report_context_vreg_regunit(unsigned VRegOrUnit) const {
547   if (TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) {
548     report_context_vreg(VRegOrUnit);
549   } else {
550     errs() << "- regunit:     " << printRegUnit(VRegOrUnit, TRI) << '\n';
551   }
552 }
553 
554 void MachineVerifier::report_context_lanemask(LaneBitmask LaneMask) const {
555   errs() << "- lanemask:    " << PrintLaneMask(LaneMask) << '\n';
556 }
557 
558 void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
559   BBInfo &MInfo = MBBInfoMap[MBB];
560   if (!MInfo.reachable) {
561     MInfo.reachable = true;
562     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
563            SuE = MBB->succ_end(); SuI != SuE; ++SuI)
564       markReachable(*SuI);
565   }
566 }
567 
568 void MachineVerifier::visitMachineFunctionBefore() {
569   lastIndex = SlotIndex();
570   regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs()
571                                            : TRI->getReservedRegs(*MF);
572 
573   if (!MF->empty())
574     markReachable(&MF->front());
575 
576   // Build a set of the basic blocks in the function.
577   FunctionBlocks.clear();
578   for (const auto &MBB : *MF) {
579     FunctionBlocks.insert(&MBB);
580     BBInfo &MInfo = MBBInfoMap[&MBB];
581 
582     MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end());
583     if (MInfo.Preds.size() != MBB.pred_size())
584       report("MBB has duplicate entries in its predecessor list.", &MBB);
585 
586     MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end());
587     if (MInfo.Succs.size() != MBB.succ_size())
588       report("MBB has duplicate entries in its successor list.", &MBB);
589   }
590 
591   // Check that the register use lists are sane.
592   MRI->verifyUseLists();
593 
594   if (!MF->empty())
595     verifyStackFrame();
596 }
597 
598 // Does iterator point to a and b as the first two elements?
599 static bool matchPair(MachineBasicBlock::const_succ_iterator i,
600                       const MachineBasicBlock *a, const MachineBasicBlock *b) {
601   if (*i == a)
602     return *++i == b;
603   if (*i == b)
604     return *++i == a;
605   return false;
606 }
607 
608 void
609 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
610   FirstTerminator = nullptr;
611 
612   if (!MF->getProperties().hasProperty(
613       MachineFunctionProperties::Property::NoPHIs) && MRI->tracksLiveness()) {
614     // If this block has allocatable physical registers live-in, check that
615     // it is an entry block or landing pad.
616     for (const auto &LI : MBB->liveins()) {
617       if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() &&
618           MBB->getIterator() != MBB->getParent()->begin()) {
619         report("MBB has allocatable live-in, but isn't entry or landing-pad.", MBB);
620       }
621     }
622   }
623 
624   // Count the number of landing pad successors.
625   SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
626   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
627        E = MBB->succ_end(); I != E; ++I) {
628     if ((*I)->isEHPad())
629       LandingPadSuccs.insert(*I);
630     if (!FunctionBlocks.count(*I))
631       report("MBB has successor that isn't part of the function.", MBB);
632     if (!MBBInfoMap[*I].Preds.count(MBB)) {
633       report("Inconsistent CFG", MBB);
634       errs() << "MBB is not in the predecessor list of the successor "
635              << printMBBReference(*(*I)) << ".\n";
636     }
637   }
638 
639   // Check the predecessor list.
640   for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
641        E = MBB->pred_end(); I != E; ++I) {
642     if (!FunctionBlocks.count(*I))
643       report("MBB has predecessor that isn't part of the function.", MBB);
644     if (!MBBInfoMap[*I].Succs.count(MBB)) {
645       report("Inconsistent CFG", MBB);
646       errs() << "MBB is not in the successor list of the predecessor "
647              << printMBBReference(*(*I)) << ".\n";
648     }
649   }
650 
651   const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
652   const BasicBlock *BB = MBB->getBasicBlock();
653   const Function &F = MF->getFunction();
654   if (LandingPadSuccs.size() > 1 &&
655       !(AsmInfo &&
656         AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
657         BB && isa<SwitchInst>(BB->getTerminator())) &&
658       !isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
659     report("MBB has more than one landing pad successor", MBB);
660 
661   // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
662   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
663   SmallVector<MachineOperand, 4> Cond;
664   if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB,
665                           Cond)) {
666     // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
667     // check whether its answers match up with reality.
668     if (!TBB && !FBB) {
669       // Block falls through to its successor.
670       MachineFunction::const_iterator MBBI = MBB->getIterator();
671       ++MBBI;
672       if (MBBI == MF->end()) {
673         // It's possible that the block legitimately ends with a noreturn
674         // call or an unreachable, in which case it won't actually fall
675         // out the bottom of the function.
676       } else if (MBB->succ_size() == LandingPadSuccs.size()) {
677         // It's possible that the block legitimately ends with a noreturn
678         // call or an unreachable, in which case it won't actuall fall
679         // out of the block.
680       } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
681         report("MBB exits via unconditional fall-through but doesn't have "
682                "exactly one CFG successor!", MBB);
683       } else if (!MBB->isSuccessor(&*MBBI)) {
684         report("MBB exits via unconditional fall-through but its successor "
685                "differs from its CFG successor!", MBB);
686       }
687       if (!MBB->empty() && MBB->back().isBarrier() &&
688           !TII->isPredicated(MBB->back())) {
689         report("MBB exits via unconditional fall-through but ends with a "
690                "barrier instruction!", MBB);
691       }
692       if (!Cond.empty()) {
693         report("MBB exits via unconditional fall-through but has a condition!",
694                MBB);
695       }
696     } else if (TBB && !FBB && Cond.empty()) {
697       // Block unconditionally branches somewhere.
698       // If the block has exactly one successor, that happens to be a
699       // landingpad, accept it as valid control flow.
700       if (MBB->succ_size() != 1+LandingPadSuccs.size() &&
701           (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 ||
702            *MBB->succ_begin() != *LandingPadSuccs.begin())) {
703         report("MBB exits via unconditional branch but doesn't have "
704                "exactly one CFG successor!", MBB);
705       } else if (!MBB->isSuccessor(TBB)) {
706         report("MBB exits via unconditional branch but the CFG "
707                "successor doesn't match the actual successor!", MBB);
708       }
709       if (MBB->empty()) {
710         report("MBB exits via unconditional branch but doesn't contain "
711                "any instructions!", MBB);
712       } else if (!MBB->back().isBarrier()) {
713         report("MBB exits via unconditional branch but doesn't end with a "
714                "barrier instruction!", MBB);
715       } else if (!MBB->back().isTerminator()) {
716         report("MBB exits via unconditional branch but the branch isn't a "
717                "terminator instruction!", MBB);
718       }
719     } else if (TBB && !FBB && !Cond.empty()) {
720       // Block conditionally branches somewhere, otherwise falls through.
721       MachineFunction::const_iterator MBBI = MBB->getIterator();
722       ++MBBI;
723       if (MBBI == MF->end()) {
724         report("MBB conditionally falls through out of function!", MBB);
725       } else if (MBB->succ_size() == 1) {
726         // A conditional branch with only one successor is weird, but allowed.
727         if (&*MBBI != TBB)
728           report("MBB exits via conditional branch/fall-through but only has "
729                  "one CFG successor!", MBB);
730         else if (TBB != *MBB->succ_begin())
731           report("MBB exits via conditional branch/fall-through but the CFG "
732                  "successor don't match the actual successor!", MBB);
733       } else if (MBB->succ_size() != 2) {
734         report("MBB exits via conditional branch/fall-through but doesn't have "
735                "exactly two CFG successors!", MBB);
736       } else if (!matchPair(MBB->succ_begin(), TBB, &*MBBI)) {
737         report("MBB exits via conditional branch/fall-through but the CFG "
738                "successors don't match the actual successors!", MBB);
739       }
740       if (MBB->empty()) {
741         report("MBB exits via conditional branch/fall-through but doesn't "
742                "contain any instructions!", MBB);
743       } else if (MBB->back().isBarrier()) {
744         report("MBB exits via conditional branch/fall-through but ends with a "
745                "barrier instruction!", MBB);
746       } else if (!MBB->back().isTerminator()) {
747         report("MBB exits via conditional branch/fall-through but the branch "
748                "isn't a terminator instruction!", MBB);
749       }
750     } else if (TBB && FBB) {
751       // Block conditionally branches somewhere, otherwise branches
752       // somewhere else.
753       if (MBB->succ_size() == 1) {
754         // A conditional branch with only one successor is weird, but allowed.
755         if (FBB != TBB)
756           report("MBB exits via conditional branch/branch through but only has "
757                  "one CFG successor!", MBB);
758         else if (TBB != *MBB->succ_begin())
759           report("MBB exits via conditional branch/branch through but the CFG "
760                  "successor don't match the actual successor!", MBB);
761       } else if (MBB->succ_size() != 2) {
762         report("MBB exits via conditional branch/branch but doesn't have "
763                "exactly two CFG successors!", MBB);
764       } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
765         report("MBB exits via conditional branch/branch but the CFG "
766                "successors don't match the actual successors!", MBB);
767       }
768       if (MBB->empty()) {
769         report("MBB exits via conditional branch/branch but doesn't "
770                "contain any instructions!", MBB);
771       } else if (!MBB->back().isBarrier()) {
772         report("MBB exits via conditional branch/branch but doesn't end with a "
773                "barrier instruction!", MBB);
774       } else if (!MBB->back().isTerminator()) {
775         report("MBB exits via conditional branch/branch but the branch "
776                "isn't a terminator instruction!", MBB);
777       }
778       if (Cond.empty()) {
779         report("MBB exits via conditinal branch/branch but there's no "
780                "condition!", MBB);
781       }
782     } else {
783       report("AnalyzeBranch returned invalid data!", MBB);
784     }
785   }
786 
787   regsLive.clear();
788   if (MRI->tracksLiveness()) {
789     for (const auto &LI : MBB->liveins()) {
790       if (!TargetRegisterInfo::isPhysicalRegister(LI.PhysReg)) {
791         report("MBB live-in list contains non-physical register", MBB);
792         continue;
793       }
794       for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true);
795            SubRegs.isValid(); ++SubRegs)
796         regsLive.insert(*SubRegs);
797     }
798   }
799 
800   const MachineFrameInfo &MFI = MF->getFrameInfo();
801   BitVector PR = MFI.getPristineRegs(*MF);
802   for (unsigned I : PR.set_bits()) {
803     for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
804          SubRegs.isValid(); ++SubRegs)
805       regsLive.insert(*SubRegs);
806   }
807 
808   regsKilled.clear();
809   regsDefined.clear();
810 
811   if (Indexes)
812     lastIndex = Indexes->getMBBStartIdx(MBB);
813 }
814 
815 // This function gets called for all bundle headers, including normal
816 // stand-alone unbundled instructions.
817 void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
818   if (Indexes && Indexes->hasIndex(*MI)) {
819     SlotIndex idx = Indexes->getInstructionIndex(*MI);
820     if (!(idx > lastIndex)) {
821       report("Instruction index out of order", MI);
822       errs() << "Last instruction was at " << lastIndex << '\n';
823     }
824     lastIndex = idx;
825   }
826 
827   // Ensure non-terminators don't follow terminators.
828   // Ignore predicated terminators formed by if conversion.
829   // FIXME: If conversion shouldn't need to violate this rule.
830   if (MI->isTerminator() && !TII->isPredicated(*MI)) {
831     if (!FirstTerminator)
832       FirstTerminator = MI;
833   } else if (FirstTerminator) {
834     report("Non-terminator instruction after the first terminator", MI);
835     errs() << "First terminator was:\t" << *FirstTerminator;
836   }
837 }
838 
839 // The operands on an INLINEASM instruction must follow a template.
840 // Verify that the flag operands make sense.
841 void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
842   // The first two operands on INLINEASM are the asm string and global flags.
843   if (MI->getNumOperands() < 2) {
844     report("Too few operands on inline asm", MI);
845     return;
846   }
847   if (!MI->getOperand(0).isSymbol())
848     report("Asm string must be an external symbol", MI);
849   if (!MI->getOperand(1).isImm())
850     report("Asm flags must be an immediate", MI);
851   // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
852   // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16,
853   // and Extra_IsConvergent = 32.
854   if (!isUInt<6>(MI->getOperand(1).getImm()))
855     report("Unknown asm flags", &MI->getOperand(1), 1);
856 
857   static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed");
858 
859   unsigned OpNo = InlineAsm::MIOp_FirstOperand;
860   unsigned NumOps;
861   for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
862     const MachineOperand &MO = MI->getOperand(OpNo);
863     // There may be implicit ops after the fixed operands.
864     if (!MO.isImm())
865       break;
866     NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
867   }
868 
869   if (OpNo > MI->getNumOperands())
870     report("Missing operands in last group", MI);
871 
872   // An optional MDNode follows the groups.
873   if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
874     ++OpNo;
875 
876   // All trailing operands must be implicit registers.
877   for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
878     const MachineOperand &MO = MI->getOperand(OpNo);
879     if (!MO.isReg() || !MO.isImplicit())
880       report("Expected implicit register after groups", &MO, OpNo);
881   }
882 }
883 
884 void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
885   const MCInstrDesc &MCID = MI->getDesc();
886   if (MI->getNumOperands() < MCID.getNumOperands()) {
887     report("Too few operands", MI);
888     errs() << MCID.getNumOperands() << " operands expected, but "
889            << MI->getNumOperands() << " given.\n";
890   }
891 
892   if (MI->isPHI() && MF->getProperties().hasProperty(
893                          MachineFunctionProperties::Property::NoPHIs))
894     report("Found PHI instruction with NoPHIs property set", MI);
895 
896   // Check the tied operands.
897   if (MI->isInlineAsm())
898     verifyInlineAsm(MI);
899 
900   // Check the MachineMemOperands for basic consistency.
901   for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
902                                   E = MI->memoperands_end();
903        I != E; ++I) {
904     if ((*I)->isLoad() && !MI->mayLoad())
905       report("Missing mayLoad flag", MI);
906     if ((*I)->isStore() && !MI->mayStore())
907       report("Missing mayStore flag", MI);
908   }
909 
910   // Debug values must not have a slot index.
911   // Other instructions must have one, unless they are inside a bundle.
912   if (LiveInts) {
913     bool mapped = !LiveInts->isNotInMIMap(*MI);
914     if (MI->isDebugInstr()) {
915       if (mapped)
916         report("Debug instruction has a slot index", MI);
917     } else if (MI->isInsideBundle()) {
918       if (mapped)
919         report("Instruction inside bundle has a slot index", MI);
920     } else {
921       if (!mapped)
922         report("Missing slot index", MI);
923     }
924   }
925 
926   if (isPreISelGenericOpcode(MCID.getOpcode())) {
927     if (isFunctionSelected)
928       report("Unexpected generic instruction in a Selected function", MI);
929 
930     // Check types.
931     SmallVector<LLT, 4> Types;
932     for (unsigned I = 0; I < MCID.getNumOperands(); ++I) {
933       if (!MCID.OpInfo[I].isGenericType())
934         continue;
935       // Generic instructions specify type equality constraints between some of
936       // their operands. Make sure these are consistent.
937       size_t TypeIdx = MCID.OpInfo[I].getGenericTypeIndex();
938       Types.resize(std::max(TypeIdx + 1, Types.size()));
939 
940       const MachineOperand *MO = &MI->getOperand(I);
941       LLT OpTy = MRI->getType(MO->getReg());
942       // Don't report a type mismatch if there is no actual mismatch, only a
943       // type missing, to reduce noise:
944       if (OpTy.isValid()) {
945         // Only the first valid type for a type index will be printed: don't
946         // overwrite it later so it's always clear which type was expected:
947         if (!Types[TypeIdx].isValid())
948           Types[TypeIdx] = OpTy;
949         else if (Types[TypeIdx] != OpTy)
950           report("Type mismatch in generic instruction", MO, I, OpTy);
951       } else {
952         // Generic instructions must have types attached to their operands.
953         report("Generic instruction is missing a virtual register type", MO, I);
954       }
955     }
956 
957     // Generic opcodes must not have physical register operands.
958     for (unsigned I = 0; I < MI->getNumOperands(); ++I) {
959       const MachineOperand *MO = &MI->getOperand(I);
960       if (MO->isReg() && TargetRegisterInfo::isPhysicalRegister(MO->getReg()))
961         report("Generic instruction cannot have physical register", MO, I);
962     }
963   }
964 
965   StringRef ErrorInfo;
966   if (!TII->verifyInstruction(*MI, ErrorInfo))
967     report(ErrorInfo.data(), MI);
968 
969   // Verify properties of various specific instruction types
970   switch(MI->getOpcode()) {
971   default:
972     break;
973   case TargetOpcode::G_LOAD:
974   case TargetOpcode::G_STORE:
975     // Generic loads and stores must have a single MachineMemOperand
976     // describing that access.
977     if (!MI->hasOneMemOperand())
978       report("Generic instruction accessing memory must have one mem operand",
979              MI);
980     break;
981   case TargetOpcode::G_PHI: {
982     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
983     if (!DstTy.isValid() ||
984         !std::all_of(MI->operands_begin() + 1, MI->operands_end(),
985                      [this, &DstTy](const MachineOperand &MO) {
986                        if (!MO.isReg())
987                          return true;
988                        LLT Ty = MRI->getType(MO.getReg());
989                        if (!Ty.isValid() || (Ty != DstTy))
990                          return false;
991                        return true;
992                      }))
993       report("Generic Instruction G_PHI has operands with incompatible/missing "
994              "types",
995              MI);
996     break;
997   }
998   case TargetOpcode::G_SEXT:
999   case TargetOpcode::G_ZEXT:
1000   case TargetOpcode::G_ANYEXT:
1001   case TargetOpcode::G_TRUNC:
1002   case TargetOpcode::G_FPEXT:
1003   case TargetOpcode::G_FPTRUNC: {
1004     // Number of operands and presense of types is already checked (and
1005     // reported in case of any issues), so no need to report them again. As
1006     // we're trying to report as many issues as possible at once, however, the
1007     // instructions aren't guaranteed to have the right number of operands or
1008     // types attached to them at this point
1009     assert(MCID.getNumOperands() == 2 && "Expected 2 operands G_*{EXT,TRUNC}");
1010     if (MI->getNumOperands() < MCID.getNumOperands())
1011       break;
1012     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1013     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1014     if (!DstTy.isValid() || !SrcTy.isValid())
1015       break;
1016 
1017     LLT DstElTy = DstTy.isVector() ? DstTy.getElementType() : DstTy;
1018     LLT SrcElTy = SrcTy.isVector() ? SrcTy.getElementType() : SrcTy;
1019     if (DstElTy.isPointer() || SrcElTy.isPointer())
1020       report("Generic extend/truncate can not operate on pointers", MI);
1021 
1022     if (DstTy.isVector() != SrcTy.isVector()) {
1023       report("Generic extend/truncate must be all-vector or all-scalar", MI);
1024       // Generally we try to report as many issues as possible at once, but in
1025       // this case it's not clear what should we be comparing the size of the
1026       // scalar with: the size of the whole vector or its lane. Instead of
1027       // making an arbitrary choice and emitting not so helpful message, let's
1028       // avoid the extra noise and stop here.
1029       break;
1030     }
1031     if (DstTy.isVector() && DstTy.getNumElements() != SrcTy.getNumElements())
1032       report("Generic vector extend/truncate must preserve number of lanes",
1033              MI);
1034     unsigned DstSize = DstElTy.getSizeInBits();
1035     unsigned SrcSize = SrcElTy.getSizeInBits();
1036     switch (MI->getOpcode()) {
1037     default:
1038       if (DstSize <= SrcSize)
1039         report("Generic extend has destination type no larger than source", MI);
1040       break;
1041     case TargetOpcode::G_TRUNC:
1042     case TargetOpcode::G_FPTRUNC:
1043       if (DstSize >= SrcSize)
1044         report("Generic truncate has destination type no smaller than source",
1045                MI);
1046       break;
1047     }
1048     break;
1049   }
1050   case TargetOpcode::COPY: {
1051     if (foundErrors)
1052       break;
1053     const MachineOperand &DstOp = MI->getOperand(0);
1054     const MachineOperand &SrcOp = MI->getOperand(1);
1055     LLT DstTy = MRI->getType(DstOp.getReg());
1056     LLT SrcTy = MRI->getType(SrcOp.getReg());
1057     if (SrcTy.isValid() && DstTy.isValid()) {
1058       // If both types are valid, check that the types are the same.
1059       if (SrcTy != DstTy) {
1060         report("Copy Instruction is illegal with mismatching types", MI);
1061         errs() << "Def = " << DstTy << ", Src = " << SrcTy << "\n";
1062       }
1063     }
1064     if (SrcTy.isValid() || DstTy.isValid()) {
1065       // If one of them have valid types, let's just check they have the same
1066       // size.
1067       unsigned SrcSize = TRI->getRegSizeInBits(SrcOp.getReg(), *MRI);
1068       unsigned DstSize = TRI->getRegSizeInBits(DstOp.getReg(), *MRI);
1069       assert(SrcSize && "Expecting size here");
1070       assert(DstSize && "Expecting size here");
1071       if (SrcSize != DstSize)
1072         if (!DstOp.getSubReg() && !SrcOp.getSubReg()) {
1073           report("Copy Instruction is illegal with mismatching sizes", MI);
1074           errs() << "Def Size = " << DstSize << ", Src Size = " << SrcSize
1075                  << "\n";
1076         }
1077     }
1078     break;
1079   }
1080   case TargetOpcode::STATEPOINT:
1081     if (!MI->getOperand(StatepointOpers::IDPos).isImm() ||
1082         !MI->getOperand(StatepointOpers::NBytesPos).isImm() ||
1083         !MI->getOperand(StatepointOpers::NCallArgsPos).isImm())
1084       report("meta operands to STATEPOINT not constant!", MI);
1085     break;
1086 
1087     auto VerifyStackMapConstant = [&](unsigned Offset) {
1088       if (!MI->getOperand(Offset).isImm() ||
1089           MI->getOperand(Offset).getImm() != StackMaps::ConstantOp ||
1090           !MI->getOperand(Offset + 1).isImm())
1091         report("stack map constant to STATEPOINT not well formed!", MI);
1092     };
1093     const unsigned VarStart = StatepointOpers(MI).getVarIdx();
1094     VerifyStackMapConstant(VarStart + StatepointOpers::CCOffset);
1095     VerifyStackMapConstant(VarStart + StatepointOpers::FlagsOffset);
1096     VerifyStackMapConstant(VarStart + StatepointOpers::NumDeoptOperandsOffset);
1097 
1098     // TODO: verify we have properly encoded deopt arguments
1099   };
1100 }
1101 
1102 void
1103 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
1104   const MachineInstr *MI = MO->getParent();
1105   const MCInstrDesc &MCID = MI->getDesc();
1106   unsigned NumDefs = MCID.getNumDefs();
1107   if (MCID.getOpcode() == TargetOpcode::PATCHPOINT)
1108     NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0;
1109 
1110   // The first MCID.NumDefs operands must be explicit register defines
1111   if (MONum < NumDefs) {
1112     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1113     if (!MO->isReg())
1114       report("Explicit definition must be a register", MO, MONum);
1115     else if (!MO->isDef() && !MCOI.isOptionalDef())
1116       report("Explicit definition marked as use", MO, MONum);
1117     else if (MO->isImplicit())
1118       report("Explicit definition marked as implicit", MO, MONum);
1119   } else if (MONum < MCID.getNumOperands()) {
1120     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1121     // Don't check if it's the last operand in a variadic instruction. See,
1122     // e.g., LDM_RET in the arm back end.
1123     if (MO->isReg() &&
1124         !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
1125       if (MO->isDef() && !MCOI.isOptionalDef())
1126         report("Explicit operand marked as def", MO, MONum);
1127       if (MO->isImplicit())
1128         report("Explicit operand marked as implicit", MO, MONum);
1129     }
1130 
1131     int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
1132     if (TiedTo != -1) {
1133       if (!MO->isReg())
1134         report("Tied use must be a register", MO, MONum);
1135       else if (!MO->isTied())
1136         report("Operand should be tied", MO, MONum);
1137       else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
1138         report("Tied def doesn't match MCInstrDesc", MO, MONum);
1139       else if (TargetRegisterInfo::isPhysicalRegister(MO->getReg())) {
1140         const MachineOperand &MOTied = MI->getOperand(TiedTo);
1141         if (!MOTied.isReg())
1142           report("Tied counterpart must be a register", &MOTied, TiedTo);
1143         else if (TargetRegisterInfo::isPhysicalRegister(MOTied.getReg()) &&
1144                  MO->getReg() != MOTied.getReg())
1145           report("Tied physical registers must match.", &MOTied, TiedTo);
1146       }
1147     } else if (MO->isReg() && MO->isTied())
1148       report("Explicit operand should not be tied", MO, MONum);
1149   } else {
1150     // ARM adds %reg0 operands to indicate predicates. We'll allow that.
1151     if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
1152       report("Extra explicit operand on non-variadic instruction", MO, MONum);
1153   }
1154 
1155   switch (MO->getType()) {
1156   case MachineOperand::MO_Register: {
1157     const unsigned Reg = MO->getReg();
1158     if (!Reg)
1159       return;
1160     if (MRI->tracksLiveness() && !MI->isDebugValue())
1161       checkLiveness(MO, MONum);
1162 
1163     // Verify the consistency of tied operands.
1164     if (MO->isTied()) {
1165       unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
1166       const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
1167       if (!OtherMO.isReg())
1168         report("Must be tied to a register", MO, MONum);
1169       if (!OtherMO.isTied())
1170         report("Missing tie flags on tied operand", MO, MONum);
1171       if (MI->findTiedOperandIdx(OtherIdx) != MONum)
1172         report("Inconsistent tie links", MO, MONum);
1173       if (MONum < MCID.getNumDefs()) {
1174         if (OtherIdx < MCID.getNumOperands()) {
1175           if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
1176             report("Explicit def tied to explicit use without tie constraint",
1177                    MO, MONum);
1178         } else {
1179           if (!OtherMO.isImplicit())
1180             report("Explicit def should be tied to implicit use", MO, MONum);
1181         }
1182       }
1183     }
1184 
1185     // Verify two-address constraints after leaving SSA form.
1186     unsigned DefIdx;
1187     if (!MRI->isSSA() && MO->isUse() &&
1188         MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
1189         Reg != MI->getOperand(DefIdx).getReg())
1190       report("Two-address instruction operands must be identical", MO, MONum);
1191 
1192     // Check register classes.
1193     unsigned SubIdx = MO->getSubReg();
1194 
1195     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1196       if (SubIdx) {
1197         report("Illegal subregister index for physical register", MO, MONum);
1198         return;
1199       }
1200       if (MONum < MCID.getNumOperands()) {
1201         if (const TargetRegisterClass *DRC =
1202               TII->getRegClass(MCID, MONum, TRI, *MF)) {
1203           if (!DRC->contains(Reg)) {
1204             report("Illegal physical register for instruction", MO, MONum);
1205             errs() << printReg(Reg, TRI) << " is not a "
1206                    << TRI->getRegClassName(DRC) << " register.\n";
1207           }
1208         }
1209       }
1210       if (MO->isRenamable()) {
1211         if (MRI->isReserved(Reg)) {
1212           report("isRenamable set on reserved register", MO, MONum);
1213           return;
1214         }
1215       }
1216       if (MI->isDebugValue() && MO->isUse() && !MO->isDebug()) {
1217         report("Use-reg is not IsDebug in a DBG_VALUE", MO, MONum);
1218         return;
1219       }
1220     } else {
1221       // Virtual register.
1222       const TargetRegisterClass *RC = MRI->getRegClassOrNull(Reg);
1223       if (!RC) {
1224         // This is a generic virtual register.
1225 
1226         // If we're post-Select, we can't have gvregs anymore.
1227         if (isFunctionSelected) {
1228           report("Generic virtual register invalid in a Selected function",
1229                  MO, MONum);
1230           return;
1231         }
1232 
1233         // The gvreg must have a type and it must not have a SubIdx.
1234         LLT Ty = MRI->getType(Reg);
1235         if (!Ty.isValid()) {
1236           report("Generic virtual register must have a valid type", MO,
1237                  MONum);
1238           return;
1239         }
1240 
1241         const RegisterBank *RegBank = MRI->getRegBankOrNull(Reg);
1242 
1243         // If we're post-RegBankSelect, the gvreg must have a bank.
1244         if (!RegBank && isFunctionRegBankSelected) {
1245           report("Generic virtual register must have a bank in a "
1246                  "RegBankSelected function",
1247                  MO, MONum);
1248           return;
1249         }
1250 
1251         // Make sure the register fits into its register bank if any.
1252         if (RegBank && Ty.isValid() &&
1253             RegBank->getSize() < Ty.getSizeInBits()) {
1254           report("Register bank is too small for virtual register", MO,
1255                  MONum);
1256           errs() << "Register bank " << RegBank->getName() << " too small("
1257                  << RegBank->getSize() << ") to fit " << Ty.getSizeInBits()
1258                  << "-bits\n";
1259           return;
1260         }
1261         if (SubIdx)  {
1262           report("Generic virtual register does not subregister index", MO,
1263                  MONum);
1264           return;
1265         }
1266 
1267         // If this is a target specific instruction and this operand
1268         // has register class constraint, the virtual register must
1269         // comply to it.
1270         if (!isPreISelGenericOpcode(MCID.getOpcode()) &&
1271             MONum < MCID.getNumOperands() &&
1272             TII->getRegClass(MCID, MONum, TRI, *MF)) {
1273           report("Virtual register does not match instruction constraint", MO,
1274                  MONum);
1275           errs() << "Expect register class "
1276                  << TRI->getRegClassName(
1277                         TII->getRegClass(MCID, MONum, TRI, *MF))
1278                  << " but got nothing\n";
1279           return;
1280         }
1281 
1282         break;
1283       }
1284       if (SubIdx) {
1285         const TargetRegisterClass *SRC =
1286           TRI->getSubClassWithSubReg(RC, SubIdx);
1287         if (!SRC) {
1288           report("Invalid subregister index for virtual register", MO, MONum);
1289           errs() << "Register class " << TRI->getRegClassName(RC)
1290               << " does not support subreg index " << SubIdx << "\n";
1291           return;
1292         }
1293         if (RC != SRC) {
1294           report("Invalid register class for subregister index", MO, MONum);
1295           errs() << "Register class " << TRI->getRegClassName(RC)
1296               << " does not fully support subreg index " << SubIdx << "\n";
1297           return;
1298         }
1299       }
1300       if (MONum < MCID.getNumOperands()) {
1301         if (const TargetRegisterClass *DRC =
1302               TII->getRegClass(MCID, MONum, TRI, *MF)) {
1303           if (SubIdx) {
1304             const TargetRegisterClass *SuperRC =
1305                 TRI->getLargestLegalSuperClass(RC, *MF);
1306             if (!SuperRC) {
1307               report("No largest legal super class exists.", MO, MONum);
1308               return;
1309             }
1310             DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
1311             if (!DRC) {
1312               report("No matching super-reg register class.", MO, MONum);
1313               return;
1314             }
1315           }
1316           if (!RC->hasSuperClassEq(DRC)) {
1317             report("Illegal virtual register for instruction", MO, MONum);
1318             errs() << "Expected a " << TRI->getRegClassName(DRC)
1319                 << " register, but got a " << TRI->getRegClassName(RC)
1320                 << " register\n";
1321           }
1322         }
1323       }
1324     }
1325     break;
1326   }
1327 
1328   case MachineOperand::MO_RegisterMask:
1329     regMasks.push_back(MO->getRegMask());
1330     break;
1331 
1332   case MachineOperand::MO_MachineBasicBlock:
1333     if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
1334       report("PHI operand is not in the CFG", MO, MONum);
1335     break;
1336 
1337   case MachineOperand::MO_FrameIndex:
1338     if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
1339         LiveInts && !LiveInts->isNotInMIMap(*MI)) {
1340       int FI = MO->getIndex();
1341       LiveInterval &LI = LiveStks->getInterval(FI);
1342       SlotIndex Idx = LiveInts->getInstructionIndex(*MI);
1343 
1344       bool stores = MI->mayStore();
1345       bool loads = MI->mayLoad();
1346       // For a memory-to-memory move, we need to check if the frame
1347       // index is used for storing or loading, by inspecting the
1348       // memory operands.
1349       if (stores && loads) {
1350         for (auto *MMO : MI->memoperands()) {
1351           const PseudoSourceValue *PSV = MMO->getPseudoValue();
1352           if (PSV == nullptr) continue;
1353           const FixedStackPseudoSourceValue *Value =
1354             dyn_cast<FixedStackPseudoSourceValue>(PSV);
1355           if (Value == nullptr) continue;
1356           if (Value->getFrameIndex() != FI) continue;
1357 
1358           if (MMO->isStore())
1359             loads = false;
1360           else
1361             stores = false;
1362           break;
1363         }
1364         if (loads == stores)
1365           report("Missing fixed stack memoperand.", MI);
1366       }
1367       if (loads && !LI.liveAt(Idx.getRegSlot(true))) {
1368         report("Instruction loads from dead spill slot", MO, MONum);
1369         errs() << "Live stack: " << LI << '\n';
1370       }
1371       if (stores && !LI.liveAt(Idx.getRegSlot())) {
1372         report("Instruction stores to dead spill slot", MO, MONum);
1373         errs() << "Live stack: " << LI << '\n';
1374       }
1375     }
1376     break;
1377 
1378   default:
1379     break;
1380   }
1381 }
1382 
1383 void MachineVerifier::checkLivenessAtUse(const MachineOperand *MO,
1384     unsigned MONum, SlotIndex UseIdx, const LiveRange &LR, unsigned VRegOrUnit,
1385     LaneBitmask LaneMask) {
1386   LiveQueryResult LRQ = LR.Query(UseIdx);
1387   // Check if we have a segment at the use, note however that we only need one
1388   // live subregister range, the others may be dead.
1389   if (!LRQ.valueIn() && LaneMask.none()) {
1390     report("No live segment at use", MO, MONum);
1391     report_context_liverange(LR);
1392     report_context_vreg_regunit(VRegOrUnit);
1393     report_context(UseIdx);
1394   }
1395   if (MO->isKill() && !LRQ.isKill()) {
1396     report("Live range continues after kill flag", MO, MONum);
1397     report_context_liverange(LR);
1398     report_context_vreg_regunit(VRegOrUnit);
1399     if (LaneMask.any())
1400       report_context_lanemask(LaneMask);
1401     report_context(UseIdx);
1402   }
1403 }
1404 
1405 void MachineVerifier::checkLivenessAtDef(const MachineOperand *MO,
1406     unsigned MONum, SlotIndex DefIdx, const LiveRange &LR, unsigned VRegOrUnit,
1407     bool SubRangeCheck, LaneBitmask LaneMask) {
1408   if (const VNInfo *VNI = LR.getVNInfoAt(DefIdx)) {
1409     assert(VNI && "NULL valno is not allowed");
1410     if (VNI->def != DefIdx) {
1411       report("Inconsistent valno->def", MO, MONum);
1412       report_context_liverange(LR);
1413       report_context_vreg_regunit(VRegOrUnit);
1414       if (LaneMask.any())
1415         report_context_lanemask(LaneMask);
1416       report_context(*VNI);
1417       report_context(DefIdx);
1418     }
1419   } else {
1420     report("No live segment at def", MO, MONum);
1421     report_context_liverange(LR);
1422     report_context_vreg_regunit(VRegOrUnit);
1423     if (LaneMask.any())
1424       report_context_lanemask(LaneMask);
1425     report_context(DefIdx);
1426   }
1427   // Check that, if the dead def flag is present, LiveInts agree.
1428   if (MO->isDead()) {
1429     LiveQueryResult LRQ = LR.Query(DefIdx);
1430     if (!LRQ.isDeadDef()) {
1431       assert(TargetRegisterInfo::isVirtualRegister(VRegOrUnit) &&
1432              "Expecting a virtual register.");
1433       // A dead subreg def only tells us that the specific subreg is dead. There
1434       // could be other non-dead defs of other subregs, or we could have other
1435       // parts of the register being live through the instruction. So unless we
1436       // are checking liveness for a subrange it is ok for the live range to
1437       // continue, given that we have a dead def of a subregister.
1438       if (SubRangeCheck || MO->getSubReg() == 0) {
1439         report("Live range continues after dead def flag", MO, MONum);
1440         report_context_liverange(LR);
1441         report_context_vreg_regunit(VRegOrUnit);
1442         if (LaneMask.any())
1443           report_context_lanemask(LaneMask);
1444       }
1445     }
1446   }
1447 }
1448 
1449 void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
1450   const MachineInstr *MI = MO->getParent();
1451   const unsigned Reg = MO->getReg();
1452 
1453   // Both use and def operands can read a register.
1454   if (MO->readsReg()) {
1455     if (MO->isKill())
1456       addRegWithSubRegs(regsKilled, Reg);
1457 
1458     // Check that LiveVars knows this kill.
1459     if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
1460         MO->isKill()) {
1461       LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1462       if (!is_contained(VI.Kills, MI))
1463         report("Kill missing from LiveVariables", MO, MONum);
1464     }
1465 
1466     // Check LiveInts liveness and kill.
1467     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
1468       SlotIndex UseIdx = LiveInts->getInstructionIndex(*MI);
1469       // Check the cached regunit intervals.
1470       if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
1471         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
1472           if (MRI->isReservedRegUnit(*Units))
1473             continue;
1474           if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units))
1475             checkLivenessAtUse(MO, MONum, UseIdx, *LR, *Units);
1476         }
1477       }
1478 
1479       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1480         if (LiveInts->hasInterval(Reg)) {
1481           // This is a virtual register interval.
1482           const LiveInterval &LI = LiveInts->getInterval(Reg);
1483           checkLivenessAtUse(MO, MONum, UseIdx, LI, Reg);
1484 
1485           if (LI.hasSubRanges() && !MO->isDef()) {
1486             unsigned SubRegIdx = MO->getSubReg();
1487             LaneBitmask MOMask = SubRegIdx != 0
1488                                ? TRI->getSubRegIndexLaneMask(SubRegIdx)
1489                                : MRI->getMaxLaneMaskForVReg(Reg);
1490             LaneBitmask LiveInMask;
1491             for (const LiveInterval::SubRange &SR : LI.subranges()) {
1492               if ((MOMask & SR.LaneMask).none())
1493                 continue;
1494               checkLivenessAtUse(MO, MONum, UseIdx, SR, Reg, SR.LaneMask);
1495               LiveQueryResult LRQ = SR.Query(UseIdx);
1496               if (LRQ.valueIn())
1497                 LiveInMask |= SR.LaneMask;
1498             }
1499             // At least parts of the register has to be live at the use.
1500             if ((LiveInMask & MOMask).none()) {
1501               report("No live subrange at use", MO, MONum);
1502               report_context(LI);
1503               report_context(UseIdx);
1504             }
1505           }
1506         } else {
1507           report("Virtual register has no live interval", MO, MONum);
1508         }
1509       }
1510     }
1511 
1512     // Use of a dead register.
1513     if (!regsLive.count(Reg)) {
1514       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1515         // Reserved registers may be used even when 'dead'.
1516         bool Bad = !isReserved(Reg);
1517         // We are fine if just any subregister has a defined value.
1518         if (Bad) {
1519           for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid();
1520                ++SubRegs) {
1521             if (regsLive.count(*SubRegs)) {
1522               Bad = false;
1523               break;
1524             }
1525           }
1526         }
1527         // If there is an additional implicit-use of a super register we stop
1528         // here. By definition we are fine if the super register is not
1529         // (completely) dead, if the complete super register is dead we will
1530         // get a report for its operand.
1531         if (Bad) {
1532           for (const MachineOperand &MOP : MI->uses()) {
1533             if (!MOP.isReg() || !MOP.isImplicit())
1534               continue;
1535 
1536             if (!TargetRegisterInfo::isPhysicalRegister(MOP.getReg()))
1537               continue;
1538 
1539             for (MCSubRegIterator SubRegs(MOP.getReg(), TRI); SubRegs.isValid();
1540                  ++SubRegs) {
1541               if (*SubRegs == Reg) {
1542                 Bad = false;
1543                 break;
1544               }
1545             }
1546           }
1547         }
1548         if (Bad)
1549           report("Using an undefined physical register", MO, MONum);
1550       } else if (MRI->def_empty(Reg)) {
1551         report("Reading virtual register without a def", MO, MONum);
1552       } else {
1553         BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1554         // We don't know which virtual registers are live in, so only complain
1555         // if vreg was killed in this MBB. Otherwise keep track of vregs that
1556         // must be live in. PHI instructions are handled separately.
1557         if (MInfo.regsKilled.count(Reg))
1558           report("Using a killed virtual register", MO, MONum);
1559         else if (!MI->isPHI())
1560           MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
1561       }
1562     }
1563   }
1564 
1565   if (MO->isDef()) {
1566     // Register defined.
1567     // TODO: verify that earlyclobber ops are not used.
1568     if (MO->isDead())
1569       addRegWithSubRegs(regsDead, Reg);
1570     else
1571       addRegWithSubRegs(regsDefined, Reg);
1572 
1573     // Verify SSA form.
1574     if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
1575         std::next(MRI->def_begin(Reg)) != MRI->def_end())
1576       report("Multiple virtual register defs in SSA form", MO, MONum);
1577 
1578     // Check LiveInts for a live segment, but only for virtual registers.
1579     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
1580       SlotIndex DefIdx = LiveInts->getInstructionIndex(*MI);
1581       DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
1582 
1583       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1584         if (LiveInts->hasInterval(Reg)) {
1585           const LiveInterval &LI = LiveInts->getInterval(Reg);
1586           checkLivenessAtDef(MO, MONum, DefIdx, LI, Reg);
1587 
1588           if (LI.hasSubRanges()) {
1589             unsigned SubRegIdx = MO->getSubReg();
1590             LaneBitmask MOMask = SubRegIdx != 0
1591               ? TRI->getSubRegIndexLaneMask(SubRegIdx)
1592               : MRI->getMaxLaneMaskForVReg(Reg);
1593             for (const LiveInterval::SubRange &SR : LI.subranges()) {
1594               if ((SR.LaneMask & MOMask).none())
1595                 continue;
1596               checkLivenessAtDef(MO, MONum, DefIdx, SR, Reg, true, SR.LaneMask);
1597             }
1598           }
1599         } else {
1600           report("Virtual register has no Live interval", MO, MONum);
1601         }
1602       }
1603     }
1604   }
1605 }
1606 
1607 void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {}
1608 
1609 // This function gets called after visiting all instructions in a bundle. The
1610 // argument points to the bundle header.
1611 // Normal stand-alone instructions are also considered 'bundles', and this
1612 // function is called for all of them.
1613 void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
1614   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1615   set_union(MInfo.regsKilled, regsKilled);
1616   set_subtract(regsLive, regsKilled); regsKilled.clear();
1617   // Kill any masked registers.
1618   while (!regMasks.empty()) {
1619     const uint32_t *Mask = regMasks.pop_back_val();
1620     for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
1621       if (TargetRegisterInfo::isPhysicalRegister(*I) &&
1622           MachineOperand::clobbersPhysReg(Mask, *I))
1623         regsDead.push_back(*I);
1624   }
1625   set_subtract(regsLive, regsDead);   regsDead.clear();
1626   set_union(regsLive, regsDefined);   regsDefined.clear();
1627 }
1628 
1629 void
1630 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
1631   MBBInfoMap[MBB].regsLiveOut = regsLive;
1632   regsLive.clear();
1633 
1634   if (Indexes) {
1635     SlotIndex stop = Indexes->getMBBEndIdx(MBB);
1636     if (!(stop > lastIndex)) {
1637       report("Block ends before last instruction index", MBB);
1638       errs() << "Block ends at " << stop
1639           << " last instruction was at " << lastIndex << '\n';
1640     }
1641     lastIndex = stop;
1642   }
1643 }
1644 
1645 // Calculate the largest possible vregsPassed sets. These are the registers that
1646 // can pass through an MBB live, but may not be live every time. It is assumed
1647 // that all vregsPassed sets are empty before the call.
1648 void MachineVerifier::calcRegsPassed() {
1649   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
1650   // have any vregsPassed.
1651   SmallPtrSet<const MachineBasicBlock*, 8> todo;
1652   for (const auto &MBB : *MF) {
1653     BBInfo &MInfo = MBBInfoMap[&MBB];
1654     if (!MInfo.reachable)
1655       continue;
1656     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
1657            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
1658       BBInfo &SInfo = MBBInfoMap[*SuI];
1659       if (SInfo.addPassed(MInfo.regsLiveOut))
1660         todo.insert(*SuI);
1661     }
1662   }
1663 
1664   // Iteratively push vregsPassed to successors. This will converge to the same
1665   // final state regardless of DenseSet iteration order.
1666   while (!todo.empty()) {
1667     const MachineBasicBlock *MBB = *todo.begin();
1668     todo.erase(MBB);
1669     BBInfo &MInfo = MBBInfoMap[MBB];
1670     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
1671            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
1672       if (*SuI == MBB)
1673         continue;
1674       BBInfo &SInfo = MBBInfoMap[*SuI];
1675       if (SInfo.addPassed(MInfo.vregsPassed))
1676         todo.insert(*SuI);
1677     }
1678   }
1679 }
1680 
1681 // Calculate the set of virtual registers that must be passed through each basic
1682 // block in order to satisfy the requirements of successor blocks. This is very
1683 // similar to calcRegsPassed, only backwards.
1684 void MachineVerifier::calcRegsRequired() {
1685   // First push live-in regs to predecessors' vregsRequired.
1686   SmallPtrSet<const MachineBasicBlock*, 8> todo;
1687   for (const auto &MBB : *MF) {
1688     BBInfo &MInfo = MBBInfoMap[&MBB];
1689     for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
1690            PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
1691       BBInfo &PInfo = MBBInfoMap[*PrI];
1692       if (PInfo.addRequired(MInfo.vregsLiveIn))
1693         todo.insert(*PrI);
1694     }
1695   }
1696 
1697   // Iteratively push vregsRequired to predecessors. This will converge to the
1698   // same final state regardless of DenseSet iteration order.
1699   while (!todo.empty()) {
1700     const MachineBasicBlock *MBB = *todo.begin();
1701     todo.erase(MBB);
1702     BBInfo &MInfo = MBBInfoMap[MBB];
1703     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1704            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1705       if (*PrI == MBB)
1706         continue;
1707       BBInfo &SInfo = MBBInfoMap[*PrI];
1708       if (SInfo.addRequired(MInfo.vregsRequired))
1709         todo.insert(*PrI);
1710     }
1711   }
1712 }
1713 
1714 // Check PHI instructions at the beginning of MBB. It is assumed that
1715 // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
1716 void MachineVerifier::checkPHIOps(const MachineBasicBlock &MBB) {
1717   BBInfo &MInfo = MBBInfoMap[&MBB];
1718 
1719   SmallPtrSet<const MachineBasicBlock*, 8> seen;
1720   for (const MachineInstr &Phi : MBB) {
1721     if (!Phi.isPHI())
1722       break;
1723     seen.clear();
1724 
1725     const MachineOperand &MODef = Phi.getOperand(0);
1726     if (!MODef.isReg() || !MODef.isDef()) {
1727       report("Expected first PHI operand to be a register def", &MODef, 0);
1728       continue;
1729     }
1730     if (MODef.isTied() || MODef.isImplicit() || MODef.isInternalRead() ||
1731         MODef.isEarlyClobber() || MODef.isDebug())
1732       report("Unexpected flag on PHI operand", &MODef, 0);
1733     unsigned DefReg = MODef.getReg();
1734     if (!TargetRegisterInfo::isVirtualRegister(DefReg))
1735       report("Expected first PHI operand to be a virtual register", &MODef, 0);
1736 
1737     for (unsigned I = 1, E = Phi.getNumOperands(); I != E; I += 2) {
1738       const MachineOperand &MO0 = Phi.getOperand(I);
1739       if (!MO0.isReg()) {
1740         report("Expected PHI operand to be a register", &MO0, I);
1741         continue;
1742       }
1743       if (MO0.isImplicit() || MO0.isInternalRead() || MO0.isEarlyClobber() ||
1744           MO0.isDebug() || MO0.isTied())
1745         report("Unexpected flag on PHI operand", &MO0, I);
1746 
1747       const MachineOperand &MO1 = Phi.getOperand(I + 1);
1748       if (!MO1.isMBB()) {
1749         report("Expected PHI operand to be a basic block", &MO1, I + 1);
1750         continue;
1751       }
1752 
1753       const MachineBasicBlock &Pre = *MO1.getMBB();
1754       if (!Pre.isSuccessor(&MBB)) {
1755         report("PHI input is not a predecessor block", &MO1, I + 1);
1756         continue;
1757       }
1758 
1759       if (MInfo.reachable) {
1760         seen.insert(&Pre);
1761         BBInfo &PrInfo = MBBInfoMap[&Pre];
1762         if (!MO0.isUndef() && PrInfo.reachable &&
1763             !PrInfo.isLiveOut(MO0.getReg()))
1764           report("PHI operand is not live-out from predecessor", &MO0, I);
1765       }
1766     }
1767 
1768     // Did we see all predecessors?
1769     if (MInfo.reachable) {
1770       for (MachineBasicBlock *Pred : MBB.predecessors()) {
1771         if (!seen.count(Pred)) {
1772           report("Missing PHI operand", &Phi);
1773           errs() << printMBBReference(*Pred)
1774                  << " is a predecessor according to the CFG.\n";
1775         }
1776       }
1777     }
1778   }
1779 }
1780 
1781 void MachineVerifier::visitMachineFunctionAfter() {
1782   calcRegsPassed();
1783 
1784   for (const MachineBasicBlock &MBB : *MF)
1785     checkPHIOps(MBB);
1786 
1787   // Now check liveness info if available
1788   calcRegsRequired();
1789 
1790   // Check for killed virtual registers that should be live out.
1791   for (const auto &MBB : *MF) {
1792     BBInfo &MInfo = MBBInfoMap[&MBB];
1793     for (RegSet::iterator
1794          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1795          ++I)
1796       if (MInfo.regsKilled.count(*I)) {
1797         report("Virtual register killed in block, but needed live out.", &MBB);
1798         errs() << "Virtual register " << printReg(*I)
1799                << " is used after the block.\n";
1800       }
1801   }
1802 
1803   if (!MF->empty()) {
1804     BBInfo &MInfo = MBBInfoMap[&MF->front()];
1805     for (RegSet::iterator
1806          I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1807          ++I) {
1808       report("Virtual register defs don't dominate all uses.", MF);
1809       report_context_vreg(*I);
1810     }
1811   }
1812 
1813   if (LiveVars)
1814     verifyLiveVariables();
1815   if (LiveInts)
1816     verifyLiveIntervals();
1817 }
1818 
1819 void MachineVerifier::verifyLiveVariables() {
1820   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
1821   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1822     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1823     LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1824     for (const auto &MBB : *MF) {
1825       BBInfo &MInfo = MBBInfoMap[&MBB];
1826 
1827       // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1828       if (MInfo.vregsRequired.count(Reg)) {
1829         if (!VI.AliveBlocks.test(MBB.getNumber())) {
1830           report("LiveVariables: Block missing from AliveBlocks", &MBB);
1831           errs() << "Virtual register " << printReg(Reg)
1832                  << " must be live through the block.\n";
1833         }
1834       } else {
1835         if (VI.AliveBlocks.test(MBB.getNumber())) {
1836           report("LiveVariables: Block should not be in AliveBlocks", &MBB);
1837           errs() << "Virtual register " << printReg(Reg)
1838                  << " is not needed live through the block.\n";
1839         }
1840       }
1841     }
1842   }
1843 }
1844 
1845 void MachineVerifier::verifyLiveIntervals() {
1846   assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
1847   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1848     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1849 
1850     // Spilling and splitting may leave unused registers around. Skip them.
1851     if (MRI->reg_nodbg_empty(Reg))
1852       continue;
1853 
1854     if (!LiveInts->hasInterval(Reg)) {
1855       report("Missing live interval for virtual register", MF);
1856       errs() << printReg(Reg, TRI) << " still has defs or uses\n";
1857       continue;
1858     }
1859 
1860     const LiveInterval &LI = LiveInts->getInterval(Reg);
1861     assert(Reg == LI.reg && "Invalid reg to interval mapping");
1862     verifyLiveInterval(LI);
1863   }
1864 
1865   // Verify all the cached regunit intervals.
1866   for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
1867     if (const LiveRange *LR = LiveInts->getCachedRegUnit(i))
1868       verifyLiveRange(*LR, i);
1869 }
1870 
1871 void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR,
1872                                            const VNInfo *VNI, unsigned Reg,
1873                                            LaneBitmask LaneMask) {
1874   if (VNI->isUnused())
1875     return;
1876 
1877   const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def);
1878 
1879   if (!DefVNI) {
1880     report("Value not live at VNInfo def and not marked unused", MF);
1881     report_context(LR, Reg, LaneMask);
1882     report_context(*VNI);
1883     return;
1884   }
1885 
1886   if (DefVNI != VNI) {
1887     report("Live segment at def has different VNInfo", MF);
1888     report_context(LR, Reg, LaneMask);
1889     report_context(*VNI);
1890     return;
1891   }
1892 
1893   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1894   if (!MBB) {
1895     report("Invalid VNInfo definition index", MF);
1896     report_context(LR, Reg, LaneMask);
1897     report_context(*VNI);
1898     return;
1899   }
1900 
1901   if (VNI->isPHIDef()) {
1902     if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1903       report("PHIDef VNInfo is not defined at MBB start", MBB);
1904       report_context(LR, Reg, LaneMask);
1905       report_context(*VNI);
1906     }
1907     return;
1908   }
1909 
1910   // Non-PHI def.
1911   const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1912   if (!MI) {
1913     report("No instruction at VNInfo def index", MBB);
1914     report_context(LR, Reg, LaneMask);
1915     report_context(*VNI);
1916     return;
1917   }
1918 
1919   if (Reg != 0) {
1920     bool hasDef = false;
1921     bool isEarlyClobber = false;
1922     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
1923       if (!MOI->isReg() || !MOI->isDef())
1924         continue;
1925       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1926         if (MOI->getReg() != Reg)
1927           continue;
1928       } else {
1929         if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1930             !TRI->hasRegUnit(MOI->getReg(), Reg))
1931           continue;
1932       }
1933       if (LaneMask.any() &&
1934           (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
1935         continue;
1936       hasDef = true;
1937       if (MOI->isEarlyClobber())
1938         isEarlyClobber = true;
1939     }
1940 
1941     if (!hasDef) {
1942       report("Defining instruction does not modify register", MI);
1943       report_context(LR, Reg, LaneMask);
1944       report_context(*VNI);
1945     }
1946 
1947     // Early clobber defs begin at USE slots, but other defs must begin at
1948     // DEF slots.
1949     if (isEarlyClobber) {
1950       if (!VNI->def.isEarlyClobber()) {
1951         report("Early clobber def must be at an early-clobber slot", MBB);
1952         report_context(LR, Reg, LaneMask);
1953         report_context(*VNI);
1954       }
1955     } else if (!VNI->def.isRegister()) {
1956       report("Non-PHI, non-early clobber def must be at a register slot", MBB);
1957       report_context(LR, Reg, LaneMask);
1958       report_context(*VNI);
1959     }
1960   }
1961 }
1962 
1963 void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
1964                                              const LiveRange::const_iterator I,
1965                                              unsigned Reg, LaneBitmask LaneMask)
1966 {
1967   const LiveRange::Segment &S = *I;
1968   const VNInfo *VNI = S.valno;
1969   assert(VNI && "Live segment has no valno");
1970 
1971   if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) {
1972     report("Foreign valno in live segment", MF);
1973     report_context(LR, Reg, LaneMask);
1974     report_context(S);
1975     report_context(*VNI);
1976   }
1977 
1978   if (VNI->isUnused()) {
1979     report("Live segment valno is marked unused", MF);
1980     report_context(LR, Reg, LaneMask);
1981     report_context(S);
1982   }
1983 
1984   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start);
1985   if (!MBB) {
1986     report("Bad start of live segment, no basic block", MF);
1987     report_context(LR, Reg, LaneMask);
1988     report_context(S);
1989     return;
1990   }
1991   SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1992   if (S.start != MBBStartIdx && S.start != VNI->def) {
1993     report("Live segment must begin at MBB entry or valno def", MBB);
1994     report_context(LR, Reg, LaneMask);
1995     report_context(S);
1996   }
1997 
1998   const MachineBasicBlock *EndMBB =
1999     LiveInts->getMBBFromIndex(S.end.getPrevSlot());
2000   if (!EndMBB) {
2001     report("Bad end of live segment, no basic block", MF);
2002     report_context(LR, Reg, LaneMask);
2003     report_context(S);
2004     return;
2005   }
2006 
2007   // No more checks for live-out segments.
2008   if (S.end == LiveInts->getMBBEndIdx(EndMBB))
2009     return;
2010 
2011   // RegUnit intervals are allowed dead phis.
2012   if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() &&
2013       S.start == VNI->def && S.end == VNI->def.getDeadSlot())
2014     return;
2015 
2016   // The live segment is ending inside EndMBB
2017   const MachineInstr *MI =
2018     LiveInts->getInstructionFromIndex(S.end.getPrevSlot());
2019   if (!MI) {
2020     report("Live segment doesn't end at a valid instruction", EndMBB);
2021     report_context(LR, Reg, LaneMask);
2022     report_context(S);
2023     return;
2024   }
2025 
2026   // The block slot must refer to a basic block boundary.
2027   if (S.end.isBlock()) {
2028     report("Live segment ends at B slot of an instruction", EndMBB);
2029     report_context(LR, Reg, LaneMask);
2030     report_context(S);
2031   }
2032 
2033   if (S.end.isDead()) {
2034     // Segment ends on the dead slot.
2035     // That means there must be a dead def.
2036     if (!SlotIndex::isSameInstr(S.start, S.end)) {
2037       report("Live segment ending at dead slot spans instructions", EndMBB);
2038       report_context(LR, Reg, LaneMask);
2039       report_context(S);
2040     }
2041   }
2042 
2043   // A live segment can only end at an early-clobber slot if it is being
2044   // redefined by an early-clobber def.
2045   if (S.end.isEarlyClobber()) {
2046     if (I+1 == LR.end() || (I+1)->start != S.end) {
2047       report("Live segment ending at early clobber slot must be "
2048              "redefined by an EC def in the same instruction", EndMBB);
2049       report_context(LR, Reg, LaneMask);
2050       report_context(S);
2051     }
2052   }
2053 
2054   // The following checks only apply to virtual registers. Physreg liveness
2055   // is too weird to check.
2056   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2057     // A live segment can end with either a redefinition, a kill flag on a
2058     // use, or a dead flag on a def.
2059     bool hasRead = false;
2060     bool hasSubRegDef = false;
2061     bool hasDeadDef = false;
2062     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
2063       if (!MOI->isReg() || MOI->getReg() != Reg)
2064         continue;
2065       unsigned Sub = MOI->getSubReg();
2066       LaneBitmask SLM = Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
2067                                  : LaneBitmask::getAll();
2068       if (MOI->isDef()) {
2069         if (Sub != 0) {
2070           hasSubRegDef = true;
2071           // An operand %0:sub0 reads %0:sub1..n. Invert the lane
2072           // mask for subregister defs. Read-undef defs will be handled by
2073           // readsReg below.
2074           SLM = ~SLM;
2075         }
2076         if (MOI->isDead())
2077           hasDeadDef = true;
2078       }
2079       if (LaneMask.any() && (LaneMask & SLM).none())
2080         continue;
2081       if (MOI->readsReg())
2082         hasRead = true;
2083     }
2084     if (S.end.isDead()) {
2085       // Make sure that the corresponding machine operand for a "dead" live
2086       // range has the dead flag. We cannot perform this check for subregister
2087       // liveranges as partially dead values are allowed.
2088       if (LaneMask.none() && !hasDeadDef) {
2089         report("Instruction ending live segment on dead slot has no dead flag",
2090                MI);
2091         report_context(LR, Reg, LaneMask);
2092         report_context(S);
2093       }
2094     } else {
2095       if (!hasRead) {
2096         // When tracking subregister liveness, the main range must start new
2097         // values on partial register writes, even if there is no read.
2098         if (!MRI->shouldTrackSubRegLiveness(Reg) || LaneMask.any() ||
2099             !hasSubRegDef) {
2100           report("Instruction ending live segment doesn't read the register",
2101                  MI);
2102           report_context(LR, Reg, LaneMask);
2103           report_context(S);
2104         }
2105       }
2106     }
2107   }
2108 
2109   // Now check all the basic blocks in this live segment.
2110   MachineFunction::const_iterator MFI = MBB->getIterator();
2111   // Is this live segment the beginning of a non-PHIDef VN?
2112   if (S.start == VNI->def && !VNI->isPHIDef()) {
2113     // Not live-in to any blocks.
2114     if (MBB == EndMBB)
2115       return;
2116     // Skip this block.
2117     ++MFI;
2118   }
2119 
2120   SmallVector<SlotIndex, 4> Undefs;
2121   if (LaneMask.any()) {
2122     LiveInterval &OwnerLI = LiveInts->getInterval(Reg);
2123     OwnerLI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
2124   }
2125 
2126   while (true) {
2127     assert(LiveInts->isLiveInToMBB(LR, &*MFI));
2128     // We don't know how to track physregs into a landing pad.
2129     if (!TargetRegisterInfo::isVirtualRegister(Reg) &&
2130         MFI->isEHPad()) {
2131       if (&*MFI == EndMBB)
2132         break;
2133       ++MFI;
2134       continue;
2135     }
2136 
2137     // Is VNI a PHI-def in the current block?
2138     bool IsPHI = VNI->isPHIDef() &&
2139       VNI->def == LiveInts->getMBBStartIdx(&*MFI);
2140 
2141     // Check that VNI is live-out of all predecessors.
2142     for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
2143          PE = MFI->pred_end(); PI != PE; ++PI) {
2144       SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
2145       const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
2146 
2147       // All predecessors must have a live-out value. However for a phi
2148       // instruction with subregister intervals
2149       // only one of the subregisters (not necessarily the current one) needs to
2150       // be defined.
2151       if (!PVNI && (LaneMask.none() || !IsPHI)) {
2152         if (LiveRangeCalc::isJointlyDominated(*PI, Undefs, *Indexes))
2153           continue;
2154         report("Register not marked live out of predecessor", *PI);
2155         report_context(LR, Reg, LaneMask);
2156         report_context(*VNI);
2157         errs() << " live into " << printMBBReference(*MFI) << '@'
2158                << LiveInts->getMBBStartIdx(&*MFI) << ", not live before "
2159                << PEnd << '\n';
2160         continue;
2161       }
2162 
2163       // Only PHI-defs can take different predecessor values.
2164       if (!IsPHI && PVNI != VNI) {
2165         report("Different value live out of predecessor", *PI);
2166         report_context(LR, Reg, LaneMask);
2167         errs() << "Valno #" << PVNI->id << " live out of "
2168                << printMBBReference(*(*PI)) << '@' << PEnd << "\nValno #"
2169                << VNI->id << " live into " << printMBBReference(*MFI) << '@'
2170                << LiveInts->getMBBStartIdx(&*MFI) << '\n';
2171       }
2172     }
2173     if (&*MFI == EndMBB)
2174       break;
2175     ++MFI;
2176   }
2177 }
2178 
2179 void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg,
2180                                       LaneBitmask LaneMask) {
2181   for (const VNInfo *VNI : LR.valnos)
2182     verifyLiveRangeValue(LR, VNI, Reg, LaneMask);
2183 
2184   for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I)
2185     verifyLiveRangeSegment(LR, I, Reg, LaneMask);
2186 }
2187 
2188 void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
2189   unsigned Reg = LI.reg;
2190   assert(TargetRegisterInfo::isVirtualRegister(Reg));
2191   verifyLiveRange(LI, Reg);
2192 
2193   LaneBitmask Mask;
2194   LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
2195   for (const LiveInterval::SubRange &SR : LI.subranges()) {
2196     if ((Mask & SR.LaneMask).any()) {
2197       report("Lane masks of sub ranges overlap in live interval", MF);
2198       report_context(LI);
2199     }
2200     if ((SR.LaneMask & ~MaxMask).any()) {
2201       report("Subrange lanemask is invalid", MF);
2202       report_context(LI);
2203     }
2204     if (SR.empty()) {
2205       report("Subrange must not be empty", MF);
2206       report_context(SR, LI.reg, SR.LaneMask);
2207     }
2208     Mask |= SR.LaneMask;
2209     verifyLiveRange(SR, LI.reg, SR.LaneMask);
2210     if (!LI.covers(SR)) {
2211       report("A Subrange is not covered by the main range", MF);
2212       report_context(LI);
2213     }
2214   }
2215 
2216   // Check the LI only has one connected component.
2217   ConnectedVNInfoEqClasses ConEQ(*LiveInts);
2218   unsigned NumComp = ConEQ.Classify(LI);
2219   if (NumComp > 1) {
2220     report("Multiple connected components in live interval", MF);
2221     report_context(LI);
2222     for (unsigned comp = 0; comp != NumComp; ++comp) {
2223       errs() << comp << ": valnos";
2224       for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
2225            E = LI.vni_end(); I!=E; ++I)
2226         if (comp == ConEQ.getEqClass(*I))
2227           errs() << ' ' << (*I)->id;
2228       errs() << '\n';
2229     }
2230   }
2231 }
2232 
2233 namespace {
2234 
2235   // FrameSetup and FrameDestroy can have zero adjustment, so using a single
2236   // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
2237   // value is zero.
2238   // We use a bool plus an integer to capture the stack state.
2239   struct StackStateOfBB {
2240     StackStateOfBB() = default;
2241     StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
2242       EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
2243       ExitIsSetup(ExitSetup) {}
2244 
2245     // Can be negative, which means we are setting up a frame.
2246     int EntryValue = 0;
2247     int ExitValue = 0;
2248     bool EntryIsSetup = false;
2249     bool ExitIsSetup = false;
2250   };
2251 
2252 } // end anonymous namespace
2253 
2254 /// Make sure on every path through the CFG, a FrameSetup <n> is always followed
2255 /// by a FrameDestroy <n>, stack adjustments are identical on all
2256 /// CFG edges to a merge point, and frame is destroyed at end of a return block.
2257 void MachineVerifier::verifyStackFrame() {
2258   unsigned FrameSetupOpcode   = TII->getCallFrameSetupOpcode();
2259   unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
2260   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
2261     return;
2262 
2263   SmallVector<StackStateOfBB, 8> SPState;
2264   SPState.resize(MF->getNumBlockIDs());
2265   df_iterator_default_set<const MachineBasicBlock*> Reachable;
2266 
2267   // Visit the MBBs in DFS order.
2268   for (df_ext_iterator<const MachineFunction *,
2269                        df_iterator_default_set<const MachineBasicBlock *>>
2270        DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
2271        DFI != DFE; ++DFI) {
2272     const MachineBasicBlock *MBB = *DFI;
2273 
2274     StackStateOfBB BBState;
2275     // Check the exit state of the DFS stack predecessor.
2276     if (DFI.getPathLength() >= 2) {
2277       const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
2278       assert(Reachable.count(StackPred) &&
2279              "DFS stack predecessor is already visited.\n");
2280       BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
2281       BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
2282       BBState.ExitValue = BBState.EntryValue;
2283       BBState.ExitIsSetup = BBState.EntryIsSetup;
2284     }
2285 
2286     // Update stack state by checking contents of MBB.
2287     for (const auto &I : *MBB) {
2288       if (I.getOpcode() == FrameSetupOpcode) {
2289         if (BBState.ExitIsSetup)
2290           report("FrameSetup is after another FrameSetup", &I);
2291         BBState.ExitValue -= TII->getFrameTotalSize(I);
2292         BBState.ExitIsSetup = true;
2293       }
2294 
2295       if (I.getOpcode() == FrameDestroyOpcode) {
2296         int Size = TII->getFrameTotalSize(I);
2297         if (!BBState.ExitIsSetup)
2298           report("FrameDestroy is not after a FrameSetup", &I);
2299         int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
2300                                                BBState.ExitValue;
2301         if (BBState.ExitIsSetup && AbsSPAdj != Size) {
2302           report("FrameDestroy <n> is after FrameSetup <m>", &I);
2303           errs() << "FrameDestroy <" << Size << "> is after FrameSetup <"
2304               << AbsSPAdj << ">.\n";
2305         }
2306         BBState.ExitValue += Size;
2307         BBState.ExitIsSetup = false;
2308       }
2309     }
2310     SPState[MBB->getNumber()] = BBState;
2311 
2312     // Make sure the exit state of any predecessor is consistent with the entry
2313     // state.
2314     for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
2315          E = MBB->pred_end(); I != E; ++I) {
2316       if (Reachable.count(*I) &&
2317           (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue ||
2318            SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
2319         report("The exit stack state of a predecessor is inconsistent.", MBB);
2320         errs() << "Predecessor " << printMBBReference(*(*I))
2321                << " has exit state (" << SPState[(*I)->getNumber()].ExitValue
2322                << ", " << SPState[(*I)->getNumber()].ExitIsSetup << "), while "
2323                << printMBBReference(*MBB) << " has entry state ("
2324                << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
2325       }
2326     }
2327 
2328     // Make sure the entry state of any successor is consistent with the exit
2329     // state.
2330     for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
2331          E = MBB->succ_end(); I != E; ++I) {
2332       if (Reachable.count(*I) &&
2333           (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue ||
2334            SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
2335         report("The entry stack state of a successor is inconsistent.", MBB);
2336         errs() << "Successor " << printMBBReference(*(*I))
2337                << " has entry state (" << SPState[(*I)->getNumber()].EntryValue
2338                << ", " << SPState[(*I)->getNumber()].EntryIsSetup << "), while "
2339                << printMBBReference(*MBB) << " has exit state ("
2340                << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
2341       }
2342     }
2343 
2344     // Make sure a basic block with return ends with zero stack adjustment.
2345     if (!MBB->empty() && MBB->back().isReturn()) {
2346       if (BBState.ExitIsSetup)
2347         report("A return block ends with a FrameSetup.", MBB);
2348       if (BBState.ExitValue)
2349         report("A return block ends with a nonzero stack adjustment.", MBB);
2350     }
2351   }
2352 }
2353