xref: /llvm-project/llvm/lib/CodeGen/MachineVerifier.cpp (revision ec893da99080366fed2e4f13a7f0d4d92cf20e9f)
1 //===- MachineVerifier.cpp - Machine Code Verifier ------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Pass to verify generated machine code. The following is checked:
10 //
11 // Operand counts: All explicit operands must be present.
12 //
13 // Register classes: All physical and virtual register operands must be
14 // compatible with the register class required by the instruction descriptor.
15 //
16 // Register live intervals: Registers must be defined only once, and must be
17 // defined before use.
18 //
19 // The machine code verifier is enabled with the command-line option
20 // -verify-machineinstrs.
21 //===----------------------------------------------------------------------===//
22 
23 #include "llvm/ADT/BitVector.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/DenseSet.h"
26 #include "llvm/ADT/DepthFirstIterator.h"
27 #include "llvm/ADT/PostOrderIterator.h"
28 #include "llvm/ADT/STLExtras.h"
29 #include "llvm/ADT/SetOperations.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/ADT/StringRef.h"
33 #include "llvm/ADT/Twine.h"
34 #include "llvm/Analysis/EHPersonalities.h"
35 #include "llvm/CodeGen/CodeGenCommonISel.h"
36 #include "llvm/CodeGen/LiveInterval.h"
37 #include "llvm/CodeGen/LiveIntervals.h"
38 #include "llvm/CodeGen/LiveRangeCalc.h"
39 #include "llvm/CodeGen/LiveStacks.h"
40 #include "llvm/CodeGen/LiveVariables.h"
41 #include "llvm/CodeGen/MachineBasicBlock.h"
42 #include "llvm/CodeGen/MachineFrameInfo.h"
43 #include "llvm/CodeGen/MachineFunction.h"
44 #include "llvm/CodeGen/MachineFunctionPass.h"
45 #include "llvm/CodeGen/MachineInstr.h"
46 #include "llvm/CodeGen/MachineInstrBundle.h"
47 #include "llvm/CodeGen/MachineMemOperand.h"
48 #include "llvm/CodeGen/MachineOperand.h"
49 #include "llvm/CodeGen/MachineRegisterInfo.h"
50 #include "llvm/CodeGen/PseudoSourceValue.h"
51 #include "llvm/CodeGen/RegisterBank.h"
52 #include "llvm/CodeGen/RegisterBankInfo.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/Constants.h"
61 #include "llvm/IR/Function.h"
62 #include "llvm/IR/InlineAsm.h"
63 #include "llvm/IR/Instructions.h"
64 #include "llvm/InitializePasses.h"
65 #include "llvm/MC/LaneBitmask.h"
66 #include "llvm/MC/MCAsmInfo.h"
67 #include "llvm/MC/MCDwarf.h"
68 #include "llvm/MC/MCInstrDesc.h"
69 #include "llvm/MC/MCRegisterInfo.h"
70 #include "llvm/MC/MCTargetOptions.h"
71 #include "llvm/Pass.h"
72 #include "llvm/Support/Casting.h"
73 #include "llvm/Support/ErrorHandling.h"
74 #include "llvm/Support/LowLevelTypeImpl.h"
75 #include "llvm/Support/MathExtras.h"
76 #include "llvm/Support/ModRef.h"
77 #include "llvm/Support/raw_ostream.h"
78 #include "llvm/Target/TargetMachine.h"
79 #include <algorithm>
80 #include <cassert>
81 #include <cstddef>
82 #include <cstdint>
83 #include <iterator>
84 #include <string>
85 #include <utility>
86 
87 using namespace llvm;
88 
89 namespace {
90 
91   struct MachineVerifier {
92     MachineVerifier(Pass *pass, const char *b) : PASS(pass), Banner(b) {}
93 
94     unsigned verify(const MachineFunction &MF);
95 
96     Pass *const PASS;
97     const char *Banner;
98     const MachineFunction *MF;
99     const TargetMachine *TM;
100     const TargetInstrInfo *TII;
101     const TargetRegisterInfo *TRI;
102     const MachineRegisterInfo *MRI;
103     const RegisterBankInfo *RBI;
104 
105     unsigned foundErrors;
106 
107     // Avoid querying the MachineFunctionProperties for each operand.
108     bool isFunctionRegBankSelected;
109     bool isFunctionSelected;
110     bool isFunctionTracksDebugUserValues;
111 
112     using RegVector = SmallVector<Register, 16>;
113     using RegMaskVector = SmallVector<const uint32_t *, 4>;
114     using RegSet = DenseSet<Register>;
115     using RegMap = DenseMap<Register, const MachineInstr *>;
116     using BlockSet = SmallPtrSet<const MachineBasicBlock *, 8>;
117 
118     const MachineInstr *FirstNonPHI;
119     const MachineInstr *FirstTerminator;
120     BlockSet FunctionBlocks;
121 
122     BitVector regsReserved;
123     RegSet regsLive;
124     RegVector regsDefined, regsDead, regsKilled;
125     RegMaskVector regMasks;
126 
127     SlotIndex lastIndex;
128 
129     // Add Reg and any sub-registers to RV
130     void addRegWithSubRegs(RegVector &RV, Register Reg) {
131       RV.push_back(Reg);
132       if (Reg.isPhysical())
133         append_range(RV, TRI->subregs(Reg.asMCReg()));
134     }
135 
136     struct BBInfo {
137       // Is this MBB reachable from the MF entry point?
138       bool reachable = false;
139 
140       // Vregs that must be live in because they are used without being
141       // defined. Map value is the user. vregsLiveIn doesn't include regs
142       // that only are used by PHI nodes.
143       RegMap vregsLiveIn;
144 
145       // Regs killed in MBB. They may be defined again, and will then be in both
146       // regsKilled and regsLiveOut.
147       RegSet regsKilled;
148 
149       // Regs defined in MBB and live out. Note that vregs passing through may
150       // be live out without being mentioned here.
151       RegSet regsLiveOut;
152 
153       // Vregs that pass through MBB untouched. This set is disjoint from
154       // regsKilled and regsLiveOut.
155       RegSet vregsPassed;
156 
157       // Vregs that must pass through MBB because they are needed by a successor
158       // block. This set is disjoint from regsLiveOut.
159       RegSet vregsRequired;
160 
161       // Set versions of block's predecessor and successor lists.
162       BlockSet Preds, Succs;
163 
164       BBInfo() = default;
165 
166       // Add register to vregsRequired if it belongs there. Return true if
167       // anything changed.
168       bool addRequired(Register Reg) {
169         if (!Reg.isVirtual())
170           return false;
171         if (regsLiveOut.count(Reg))
172           return false;
173         return vregsRequired.insert(Reg).second;
174       }
175 
176       // Same for a full set.
177       bool addRequired(const RegSet &RS) {
178         bool Changed = false;
179         for (Register Reg : RS)
180           Changed |= addRequired(Reg);
181         return Changed;
182       }
183 
184       // Same for a full map.
185       bool addRequired(const RegMap &RM) {
186         bool Changed = false;
187         for (const auto &I : RM)
188           Changed |= addRequired(I.first);
189         return Changed;
190       }
191 
192       // Live-out registers are either in regsLiveOut or vregsPassed.
193       bool isLiveOut(Register Reg) const {
194         return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
195       }
196     };
197 
198     // Extra register info per MBB.
199     DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
200 
201     bool isReserved(Register Reg) {
202       return Reg.id() < regsReserved.size() && regsReserved.test(Reg.id());
203     }
204 
205     bool isAllocatable(Register Reg) const {
206       return Reg.id() < TRI->getNumRegs() && TRI->isInAllocatableClass(Reg) &&
207              !regsReserved.test(Reg.id());
208     }
209 
210     // Analysis information if available
211     LiveVariables *LiveVars;
212     LiveIntervals *LiveInts;
213     LiveStacks *LiveStks;
214     SlotIndexes *Indexes;
215 
216     void visitMachineFunctionBefore();
217     void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
218     void visitMachineBundleBefore(const MachineInstr *MI);
219 
220     /// Verify that all of \p MI's virtual register operands are scalars.
221     /// \returns True if all virtual register operands are scalar. False
222     /// otherwise.
223     bool verifyAllRegOpsScalar(const MachineInstr &MI,
224                                const MachineRegisterInfo &MRI);
225     bool verifyVectorElementMatch(LLT Ty0, LLT Ty1, const MachineInstr *MI);
226     void verifyPreISelGenericInstruction(const MachineInstr *MI);
227     void visitMachineInstrBefore(const MachineInstr *MI);
228     void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
229     void visitMachineBundleAfter(const MachineInstr *MI);
230     void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
231     void visitMachineFunctionAfter();
232 
233     void report(const char *msg, const MachineFunction *MF);
234     void report(const char *msg, const MachineBasicBlock *MBB);
235     void report(const char *msg, const MachineInstr *MI);
236     void report(const char *msg, const MachineOperand *MO, unsigned MONum,
237                 LLT MOVRegType = LLT{});
238     void report(const Twine &Msg, const MachineInstr *MI);
239 
240     void report_context(const LiveInterval &LI) const;
241     void report_context(const LiveRange &LR, Register VRegUnit,
242                         LaneBitmask LaneMask) const;
243     void report_context(const LiveRange::Segment &S) const;
244     void report_context(const VNInfo &VNI) const;
245     void report_context(SlotIndex Pos) const;
246     void report_context(MCPhysReg PhysReg) const;
247     void report_context_liverange(const LiveRange &LR) const;
248     void report_context_lanemask(LaneBitmask LaneMask) const;
249     void report_context_vreg(Register VReg) const;
250     void report_context_vreg_regunit(Register VRegOrUnit) const;
251 
252     void verifyInlineAsm(const MachineInstr *MI);
253 
254     void checkLiveness(const MachineOperand *MO, unsigned MONum);
255     void checkLivenessAtUse(const MachineOperand *MO, unsigned MONum,
256                             SlotIndex UseIdx, const LiveRange &LR,
257                             Register VRegOrUnit,
258                             LaneBitmask LaneMask = LaneBitmask::getNone());
259     void checkLivenessAtDef(const MachineOperand *MO, unsigned MONum,
260                             SlotIndex DefIdx, const LiveRange &LR,
261                             Register VRegOrUnit, bool SubRangeCheck = false,
262                             LaneBitmask LaneMask = LaneBitmask::getNone());
263 
264     void markReachable(const MachineBasicBlock *MBB);
265     void calcRegsPassed();
266     void checkPHIOps(const MachineBasicBlock &MBB);
267 
268     void calcRegsRequired();
269     void verifyLiveVariables();
270     void verifyLiveIntervals();
271     void verifyLiveInterval(const LiveInterval&);
272     void verifyLiveRangeValue(const LiveRange &, const VNInfo *, Register,
273                               LaneBitmask);
274     void verifyLiveRangeSegment(const LiveRange &,
275                                 const LiveRange::const_iterator I, Register,
276                                 LaneBitmask);
277     void verifyLiveRange(const LiveRange &, Register,
278                          LaneBitmask LaneMask = LaneBitmask::getNone());
279 
280     void verifyStackFrame();
281 
282     void verifySlotIndexes() const;
283     void verifyProperties(const MachineFunction &MF);
284   };
285 
286   struct MachineVerifierPass : public MachineFunctionPass {
287     static char ID; // Pass ID, replacement for typeid
288 
289     const std::string Banner;
290 
291     MachineVerifierPass(std::string banner = std::string())
292       : MachineFunctionPass(ID), Banner(std::move(banner)) {
293         initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
294       }
295 
296     void getAnalysisUsage(AnalysisUsage &AU) const override {
297       AU.addUsedIfAvailable<LiveStacks>();
298       AU.addUsedIfAvailable<LiveVariables>();
299       AU.setPreservesAll();
300       MachineFunctionPass::getAnalysisUsage(AU);
301     }
302 
303     bool runOnMachineFunction(MachineFunction &MF) override {
304       // Skip functions that have known verification problems.
305       // FIXME: Remove this mechanism when all problematic passes have been
306       // fixed.
307       if (MF.getProperties().hasProperty(
308               MachineFunctionProperties::Property::FailsVerification))
309         return false;
310 
311       unsigned FoundErrors = MachineVerifier(this, Banner.c_str()).verify(MF);
312       if (FoundErrors)
313         report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
314       return false;
315     }
316   };
317 
318 } // end anonymous namespace
319 
320 char MachineVerifierPass::ID = 0;
321 
322 INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
323                 "Verify generated machine code", false, false)
324 
325 FunctionPass *llvm::createMachineVerifierPass(const std::string &Banner) {
326   return new MachineVerifierPass(Banner);
327 }
328 
329 void llvm::verifyMachineFunction(MachineFunctionAnalysisManager *,
330                                  const std::string &Banner,
331                                  const MachineFunction &MF) {
332   // TODO: Use MFAM after porting below analyses.
333   // LiveVariables *LiveVars;
334   // LiveIntervals *LiveInts;
335   // LiveStacks *LiveStks;
336   // SlotIndexes *Indexes;
337   unsigned FoundErrors = MachineVerifier(nullptr, Banner.c_str()).verify(MF);
338   if (FoundErrors)
339     report_fatal_error("Found " + Twine(FoundErrors) + " machine code errors.");
340 }
341 
342 bool MachineFunction::verify(Pass *p, const char *Banner, bool AbortOnErrors)
343     const {
344   MachineFunction &MF = const_cast<MachineFunction&>(*this);
345   unsigned FoundErrors = MachineVerifier(p, Banner).verify(MF);
346   if (AbortOnErrors && FoundErrors)
347     report_fatal_error("Found "+Twine(FoundErrors)+" machine code errors.");
348   return FoundErrors == 0;
349 }
350 
351 void MachineVerifier::verifySlotIndexes() const {
352   if (Indexes == nullptr)
353     return;
354 
355   // Ensure the IdxMBB list is sorted by slot indexes.
356   SlotIndex Last;
357   for (SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(),
358        E = Indexes->MBBIndexEnd(); I != E; ++I) {
359     assert(!Last.isValid() || I->first > Last);
360     Last = I->first;
361   }
362 }
363 
364 void MachineVerifier::verifyProperties(const MachineFunction &MF) {
365   // If a pass has introduced virtual registers without clearing the
366   // NoVRegs property (or set it without allocating the vregs)
367   // then report an error.
368   if (MF.getProperties().hasProperty(
369           MachineFunctionProperties::Property::NoVRegs) &&
370       MRI->getNumVirtRegs())
371     report("Function has NoVRegs property but there are VReg operands", &MF);
372 }
373 
374 unsigned MachineVerifier::verify(const MachineFunction &MF) {
375   foundErrors = 0;
376 
377   this->MF = &MF;
378   TM = &MF.getTarget();
379   TII = MF.getSubtarget().getInstrInfo();
380   TRI = MF.getSubtarget().getRegisterInfo();
381   RBI = MF.getSubtarget().getRegBankInfo();
382   MRI = &MF.getRegInfo();
383 
384   const bool isFunctionFailedISel = MF.getProperties().hasProperty(
385       MachineFunctionProperties::Property::FailedISel);
386 
387   // If we're mid-GlobalISel and we already triggered the fallback path then
388   // it's expected that the MIR is somewhat broken but that's ok since we'll
389   // reset it and clear the FailedISel attribute in ResetMachineFunctions.
390   if (isFunctionFailedISel)
391     return foundErrors;
392 
393   isFunctionRegBankSelected = MF.getProperties().hasProperty(
394       MachineFunctionProperties::Property::RegBankSelected);
395   isFunctionSelected = MF.getProperties().hasProperty(
396       MachineFunctionProperties::Property::Selected);
397   isFunctionTracksDebugUserValues = MF.getProperties().hasProperty(
398       MachineFunctionProperties::Property::TracksDebugUserValues);
399 
400   LiveVars = nullptr;
401   LiveInts = nullptr;
402   LiveStks = nullptr;
403   Indexes = nullptr;
404   if (PASS) {
405     LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
406     // We don't want to verify LiveVariables if LiveIntervals is available.
407     if (!LiveInts)
408       LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
409     LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
410     Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
411   }
412 
413   verifySlotIndexes();
414 
415   verifyProperties(MF);
416 
417   visitMachineFunctionBefore();
418   for (const MachineBasicBlock &MBB : MF) {
419     visitMachineBasicBlockBefore(&MBB);
420     // Keep track of the current bundle header.
421     const MachineInstr *CurBundle = nullptr;
422     // Do we expect the next instruction to be part of the same bundle?
423     bool InBundle = false;
424 
425     for (const MachineInstr &MI : MBB.instrs()) {
426       if (MI.getParent() != &MBB) {
427         report("Bad instruction parent pointer", &MBB);
428         errs() << "Instruction: " << MI;
429         continue;
430       }
431 
432       // Check for consistent bundle flags.
433       if (InBundle && !MI.isBundledWithPred())
434         report("Missing BundledPred flag, "
435                "BundledSucc was set on predecessor",
436                &MI);
437       if (!InBundle && MI.isBundledWithPred())
438         report("BundledPred flag is set, "
439                "but BundledSucc not set on predecessor",
440                &MI);
441 
442       // Is this a bundle header?
443       if (!MI.isInsideBundle()) {
444         if (CurBundle)
445           visitMachineBundleAfter(CurBundle);
446         CurBundle = &MI;
447         visitMachineBundleBefore(CurBundle);
448       } else if (!CurBundle)
449         report("No bundle header", &MI);
450       visitMachineInstrBefore(&MI);
451       for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
452         const MachineOperand &Op = MI.getOperand(I);
453         if (Op.getParent() != &MI) {
454           // Make sure to use correct addOperand / removeOperand / ChangeTo
455           // functions when replacing operands of a MachineInstr.
456           report("Instruction has operand with wrong parent set", &MI);
457         }
458 
459         visitMachineOperand(&Op, I);
460       }
461 
462       // Was this the last bundled instruction?
463       InBundle = MI.isBundledWithSucc();
464     }
465     if (CurBundle)
466       visitMachineBundleAfter(CurBundle);
467     if (InBundle)
468       report("BundledSucc flag set on last instruction in block", &MBB.back());
469     visitMachineBasicBlockAfter(&MBB);
470   }
471   visitMachineFunctionAfter();
472 
473   // Clean up.
474   regsLive.clear();
475   regsDefined.clear();
476   regsDead.clear();
477   regsKilled.clear();
478   regMasks.clear();
479   MBBInfoMap.clear();
480 
481   return foundErrors;
482 }
483 
484 void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
485   assert(MF);
486   errs() << '\n';
487   if (!foundErrors++) {
488     if (Banner)
489       errs() << "# " << Banner << '\n';
490     if (LiveInts != nullptr)
491       LiveInts->print(errs());
492     else
493       MF->print(errs(), Indexes);
494   }
495   errs() << "*** Bad machine code: " << msg << " ***\n"
496       << "- function:    " << MF->getName() << "\n";
497 }
498 
499 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
500   assert(MBB);
501   report(msg, MBB->getParent());
502   errs() << "- basic block: " << printMBBReference(*MBB) << ' '
503          << MBB->getName() << " (" << (const void *)MBB << ')';
504   if (Indexes)
505     errs() << " [" << Indexes->getMBBStartIdx(MBB)
506         << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
507   errs() << '\n';
508 }
509 
510 void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
511   assert(MI);
512   report(msg, MI->getParent());
513   errs() << "- instruction: ";
514   if (Indexes && Indexes->hasIndex(*MI))
515     errs() << Indexes->getInstructionIndex(*MI) << '\t';
516   MI->print(errs(), /*IsStandalone=*/true);
517 }
518 
519 void MachineVerifier::report(const char *msg, const MachineOperand *MO,
520                              unsigned MONum, LLT MOVRegType) {
521   assert(MO);
522   report(msg, MO->getParent());
523   errs() << "- operand " << MONum << ":   ";
524   MO->print(errs(), MOVRegType, TRI);
525   errs() << "\n";
526 }
527 
528 void MachineVerifier::report(const Twine &Msg, const MachineInstr *MI) {
529   report(Msg.str().c_str(), MI);
530 }
531 
532 void MachineVerifier::report_context(SlotIndex Pos) const {
533   errs() << "- at:          " << Pos << '\n';
534 }
535 
536 void MachineVerifier::report_context(const LiveInterval &LI) const {
537   errs() << "- interval:    " << LI << '\n';
538 }
539 
540 void MachineVerifier::report_context(const LiveRange &LR, Register VRegUnit,
541                                      LaneBitmask LaneMask) const {
542   report_context_liverange(LR);
543   report_context_vreg_regunit(VRegUnit);
544   if (LaneMask.any())
545     report_context_lanemask(LaneMask);
546 }
547 
548 void MachineVerifier::report_context(const LiveRange::Segment &S) const {
549   errs() << "- segment:     " << S << '\n';
550 }
551 
552 void MachineVerifier::report_context(const VNInfo &VNI) const {
553   errs() << "- ValNo:       " << VNI.id << " (def " << VNI.def << ")\n";
554 }
555 
556 void MachineVerifier::report_context_liverange(const LiveRange &LR) const {
557   errs() << "- liverange:   " << LR << '\n';
558 }
559 
560 void MachineVerifier::report_context(MCPhysReg PReg) const {
561   errs() << "- p. register: " << printReg(PReg, TRI) << '\n';
562 }
563 
564 void MachineVerifier::report_context_vreg(Register VReg) const {
565   errs() << "- v. register: " << printReg(VReg, TRI) << '\n';
566 }
567 
568 void MachineVerifier::report_context_vreg_regunit(Register VRegOrUnit) const {
569   if (Register::isVirtualRegister(VRegOrUnit)) {
570     report_context_vreg(VRegOrUnit);
571   } else {
572     errs() << "- regunit:     " << printRegUnit(VRegOrUnit, TRI) << '\n';
573   }
574 }
575 
576 void MachineVerifier::report_context_lanemask(LaneBitmask LaneMask) const {
577   errs() << "- lanemask:    " << PrintLaneMask(LaneMask) << '\n';
578 }
579 
580 void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
581   BBInfo &MInfo = MBBInfoMap[MBB];
582   if (!MInfo.reachable) {
583     MInfo.reachable = true;
584     for (const MachineBasicBlock *Succ : MBB->successors())
585       markReachable(Succ);
586   }
587 }
588 
589 void MachineVerifier::visitMachineFunctionBefore() {
590   lastIndex = SlotIndex();
591   regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs()
592                                            : TRI->getReservedRegs(*MF);
593 
594   if (!MF->empty())
595     markReachable(&MF->front());
596 
597   // Build a set of the basic blocks in the function.
598   FunctionBlocks.clear();
599   for (const auto &MBB : *MF) {
600     FunctionBlocks.insert(&MBB);
601     BBInfo &MInfo = MBBInfoMap[&MBB];
602 
603     MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end());
604     if (MInfo.Preds.size() != MBB.pred_size())
605       report("MBB has duplicate entries in its predecessor list.", &MBB);
606 
607     MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end());
608     if (MInfo.Succs.size() != MBB.succ_size())
609       report("MBB has duplicate entries in its successor list.", &MBB);
610   }
611 
612   // Check that the register use lists are sane.
613   MRI->verifyUseLists();
614 
615   if (!MF->empty())
616     verifyStackFrame();
617 }
618 
619 void
620 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
621   FirstTerminator = nullptr;
622   FirstNonPHI = nullptr;
623 
624   if (!MF->getProperties().hasProperty(
625       MachineFunctionProperties::Property::NoPHIs) && MRI->tracksLiveness()) {
626     // If this block has allocatable physical registers live-in, check that
627     // it is an entry block or landing pad.
628     for (const auto &LI : MBB->liveins()) {
629       if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() &&
630           MBB->getIterator() != MBB->getParent()->begin()) {
631         report("MBB has allocatable live-in, but isn't entry or landing-pad.", MBB);
632         report_context(LI.PhysReg);
633       }
634     }
635   }
636 
637   if (MBB->isIRBlockAddressTaken()) {
638     if (!MBB->getAddressTakenIRBlock()->hasAddressTaken())
639       report("ir-block-address-taken is associated with basic block not used by "
640              "a blockaddress.",
641              MBB);
642   }
643 
644   // Count the number of landing pad successors.
645   SmallPtrSet<const MachineBasicBlock*, 4> LandingPadSuccs;
646   for (const auto *succ : MBB->successors()) {
647     if (succ->isEHPad())
648       LandingPadSuccs.insert(succ);
649     if (!FunctionBlocks.count(succ))
650       report("MBB has successor that isn't part of the function.", MBB);
651     if (!MBBInfoMap[succ].Preds.count(MBB)) {
652       report("Inconsistent CFG", MBB);
653       errs() << "MBB is not in the predecessor list of the successor "
654              << printMBBReference(*succ) << ".\n";
655     }
656   }
657 
658   // Check the predecessor list.
659   for (const MachineBasicBlock *Pred : MBB->predecessors()) {
660     if (!FunctionBlocks.count(Pred))
661       report("MBB has predecessor that isn't part of the function.", MBB);
662     if (!MBBInfoMap[Pred].Succs.count(MBB)) {
663       report("Inconsistent CFG", MBB);
664       errs() << "MBB is not in the successor list of the predecessor "
665              << printMBBReference(*Pred) << ".\n";
666     }
667   }
668 
669   const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
670   const BasicBlock *BB = MBB->getBasicBlock();
671   const Function &F = MF->getFunction();
672   if (LandingPadSuccs.size() > 1 &&
673       !(AsmInfo &&
674         AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
675         BB && isa<SwitchInst>(BB->getTerminator())) &&
676       !isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
677     report("MBB has more than one landing pad successor", MBB);
678 
679   // Call analyzeBranch. If it succeeds, there several more conditions to check.
680   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
681   SmallVector<MachineOperand, 4> Cond;
682   if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB,
683                           Cond)) {
684     // Ok, analyzeBranch thinks it knows what's going on with this block. Let's
685     // check whether its answers match up with reality.
686     if (!TBB && !FBB) {
687       // Block falls through to its successor.
688       if (!MBB->empty() && MBB->back().isBarrier() &&
689           !TII->isPredicated(MBB->back())) {
690         report("MBB exits via unconditional fall-through but ends with a "
691                "barrier instruction!", MBB);
692       }
693       if (!Cond.empty()) {
694         report("MBB exits via unconditional fall-through but has a condition!",
695                MBB);
696       }
697     } else if (TBB && !FBB && Cond.empty()) {
698       // Block unconditionally branches somewhere.
699       if (MBB->empty()) {
700         report("MBB exits via unconditional branch but doesn't contain "
701                "any instructions!", MBB);
702       } else if (!MBB->back().isBarrier()) {
703         report("MBB exits via unconditional branch but doesn't end with a "
704                "barrier instruction!", MBB);
705       } else if (!MBB->back().isTerminator()) {
706         report("MBB exits via unconditional branch but the branch isn't a "
707                "terminator instruction!", MBB);
708       }
709     } else if (TBB && !FBB && !Cond.empty()) {
710       // Block conditionally branches somewhere, otherwise falls through.
711       if (MBB->empty()) {
712         report("MBB exits via conditional branch/fall-through but doesn't "
713                "contain any instructions!", MBB);
714       } else if (MBB->back().isBarrier()) {
715         report("MBB exits via conditional branch/fall-through but ends with a "
716                "barrier instruction!", MBB);
717       } else if (!MBB->back().isTerminator()) {
718         report("MBB exits via conditional branch/fall-through but the branch "
719                "isn't a terminator instruction!", MBB);
720       }
721     } else if (TBB && FBB) {
722       // Block conditionally branches somewhere, otherwise branches
723       // somewhere else.
724       if (MBB->empty()) {
725         report("MBB exits via conditional branch/branch but doesn't "
726                "contain any instructions!", MBB);
727       } else if (!MBB->back().isBarrier()) {
728         report("MBB exits via conditional branch/branch but doesn't end with a "
729                "barrier instruction!", MBB);
730       } else if (!MBB->back().isTerminator()) {
731         report("MBB exits via conditional branch/branch but the branch "
732                "isn't a terminator instruction!", MBB);
733       }
734       if (Cond.empty()) {
735         report("MBB exits via conditional branch/branch but there's no "
736                "condition!", MBB);
737       }
738     } else {
739       report("analyzeBranch returned invalid data!", MBB);
740     }
741 
742     // Now check that the successors match up with the answers reported by
743     // analyzeBranch.
744     if (TBB && !MBB->isSuccessor(TBB))
745       report("MBB exits via jump or conditional branch, but its target isn't a "
746              "CFG successor!",
747              MBB);
748     if (FBB && !MBB->isSuccessor(FBB))
749       report("MBB exits via conditional branch, but its target isn't a CFG "
750              "successor!",
751              MBB);
752 
753     // There might be a fallthrough to the next block if there's either no
754     // unconditional true branch, or if there's a condition, and one of the
755     // branches is missing.
756     bool Fallthrough = !TBB || (!Cond.empty() && !FBB);
757 
758     // A conditional fallthrough must be an actual CFG successor, not
759     // unreachable. (Conversely, an unconditional fallthrough might not really
760     // be a successor, because the block might end in unreachable.)
761     if (!Cond.empty() && !FBB) {
762       MachineFunction::const_iterator MBBI = std::next(MBB->getIterator());
763       if (MBBI == MF->end()) {
764         report("MBB conditionally falls through out of function!", MBB);
765       } else if (!MBB->isSuccessor(&*MBBI))
766         report("MBB exits via conditional branch/fall-through but the CFG "
767                "successors don't match the actual successors!",
768                MBB);
769     }
770 
771     // Verify that there aren't any extra un-accounted-for successors.
772     for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
773       // If this successor is one of the branch targets, it's okay.
774       if (SuccMBB == TBB || SuccMBB == FBB)
775         continue;
776       // If we might have a fallthrough, and the successor is the fallthrough
777       // block, that's also ok.
778       if (Fallthrough && SuccMBB == MBB->getNextNode())
779         continue;
780       // Also accept successors which are for exception-handling or might be
781       // inlineasm_br targets.
782       if (SuccMBB->isEHPad() || SuccMBB->isInlineAsmBrIndirectTarget())
783         continue;
784       report("MBB has unexpected successors which are not branch targets, "
785              "fallthrough, EHPads, or inlineasm_br targets.",
786              MBB);
787     }
788   }
789 
790   regsLive.clear();
791   if (MRI->tracksLiveness()) {
792     for (const auto &LI : MBB->liveins()) {
793       if (!Register::isPhysicalRegister(LI.PhysReg)) {
794         report("MBB live-in list contains non-physical register", MBB);
795         continue;
796       }
797       for (const MCPhysReg &SubReg : TRI->subregs_inclusive(LI.PhysReg))
798         regsLive.insert(SubReg);
799     }
800   }
801 
802   const MachineFrameInfo &MFI = MF->getFrameInfo();
803   BitVector PR = MFI.getPristineRegs(*MF);
804   for (unsigned I : PR.set_bits()) {
805     for (const MCPhysReg &SubReg : TRI->subregs_inclusive(I))
806       regsLive.insert(SubReg);
807   }
808 
809   regsKilled.clear();
810   regsDefined.clear();
811 
812   if (Indexes)
813     lastIndex = Indexes->getMBBStartIdx(MBB);
814 }
815 
816 // This function gets called for all bundle headers, including normal
817 // stand-alone unbundled instructions.
818 void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
819   if (Indexes && Indexes->hasIndex(*MI)) {
820     SlotIndex idx = Indexes->getInstructionIndex(*MI);
821     if (!(idx > lastIndex)) {
822       report("Instruction index out of order", MI);
823       errs() << "Last instruction was at " << lastIndex << '\n';
824     }
825     lastIndex = idx;
826   }
827 
828   // Ensure non-terminators don't follow terminators.
829   if (MI->isTerminator()) {
830     if (!FirstTerminator)
831       FirstTerminator = MI;
832   } else if (FirstTerminator) {
833     report("Non-terminator instruction after the first terminator", MI);
834     errs() << "First terminator was:\t" << *FirstTerminator;
835   }
836 }
837 
838 // The operands on an INLINEASM instruction must follow a template.
839 // Verify that the flag operands make sense.
840 void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
841   // The first two operands on INLINEASM are the asm string and global flags.
842   if (MI->getNumOperands() < 2) {
843     report("Too few operands on inline asm", MI);
844     return;
845   }
846   if (!MI->getOperand(0).isSymbol())
847     report("Asm string must be an external symbol", MI);
848   if (!MI->getOperand(1).isImm())
849     report("Asm flags must be an immediate", MI);
850   // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
851   // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16,
852   // and Extra_IsConvergent = 32.
853   if (!isUInt<6>(MI->getOperand(1).getImm()))
854     report("Unknown asm flags", &MI->getOperand(1), 1);
855 
856   static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed");
857 
858   unsigned OpNo = InlineAsm::MIOp_FirstOperand;
859   unsigned NumOps;
860   for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
861     const MachineOperand &MO = MI->getOperand(OpNo);
862     // There may be implicit ops after the fixed operands.
863     if (!MO.isImm())
864       break;
865     NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
866   }
867 
868   if (OpNo > MI->getNumOperands())
869     report("Missing operands in last group", MI);
870 
871   // An optional MDNode follows the groups.
872   if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
873     ++OpNo;
874 
875   // All trailing operands must be implicit registers.
876   for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
877     const MachineOperand &MO = MI->getOperand(OpNo);
878     if (!MO.isReg() || !MO.isImplicit())
879       report("Expected implicit register after groups", &MO, OpNo);
880   }
881 
882   if (MI->getOpcode() == TargetOpcode::INLINEASM_BR) {
883     const MachineBasicBlock *MBB = MI->getParent();
884 
885     for (unsigned i = InlineAsm::MIOp_FirstOperand, e = MI->getNumOperands();
886          i != e; ++i) {
887       const MachineOperand &MO = MI->getOperand(i);
888 
889       if (!MO.isMBB())
890         continue;
891 
892       // Check the successor & predecessor lists look ok, assume they are
893       // not. Find the indirect target without going through the successors.
894       const MachineBasicBlock *IndirectTargetMBB = MO.getMBB();
895       if (!IndirectTargetMBB) {
896         report("INLINEASM_BR indirect target does not exist", &MO, i);
897         break;
898       }
899 
900       if (!MBB->isSuccessor(IndirectTargetMBB))
901         report("INLINEASM_BR indirect target missing from successor list", &MO,
902                i);
903 
904       if (!IndirectTargetMBB->isPredecessor(MBB))
905         report("INLINEASM_BR indirect target predecessor list missing parent",
906                &MO, i);
907     }
908   }
909 }
910 
911 bool MachineVerifier::verifyAllRegOpsScalar(const MachineInstr &MI,
912                                             const MachineRegisterInfo &MRI) {
913   if (none_of(MI.explicit_operands(), [&MRI](const MachineOperand &Op) {
914         if (!Op.isReg())
915           return false;
916         const auto Reg = Op.getReg();
917         if (Reg.isPhysical())
918           return false;
919         return !MRI.getType(Reg).isScalar();
920       }))
921     return true;
922   report("All register operands must have scalar types", &MI);
923   return false;
924 }
925 
926 /// Check that types are consistent when two operands need to have the same
927 /// number of vector elements.
928 /// \return true if the types are valid.
929 bool MachineVerifier::verifyVectorElementMatch(LLT Ty0, LLT Ty1,
930                                                const MachineInstr *MI) {
931   if (Ty0.isVector() != Ty1.isVector()) {
932     report("operand types must be all-vector or all-scalar", MI);
933     // Generally we try to report as many issues as possible at once, but in
934     // this case it's not clear what should we be comparing the size of the
935     // scalar with: the size of the whole vector or its lane. Instead of
936     // making an arbitrary choice and emitting not so helpful message, let's
937     // avoid the extra noise and stop here.
938     return false;
939   }
940 
941   if (Ty0.isVector() && Ty0.getNumElements() != Ty1.getNumElements()) {
942     report("operand types must preserve number of vector elements", MI);
943     return false;
944   }
945 
946   return true;
947 }
948 
949 void MachineVerifier::verifyPreISelGenericInstruction(const MachineInstr *MI) {
950   if (isFunctionSelected)
951     report("Unexpected generic instruction in a Selected function", MI);
952 
953   const MCInstrDesc &MCID = MI->getDesc();
954   unsigned NumOps = MI->getNumOperands();
955 
956   // Branches must reference a basic block if they are not indirect
957   if (MI->isBranch() && !MI->isIndirectBranch()) {
958     bool HasMBB = false;
959     for (const MachineOperand &Op : MI->operands()) {
960       if (Op.isMBB()) {
961         HasMBB = true;
962         break;
963       }
964     }
965 
966     if (!HasMBB) {
967       report("Branch instruction is missing a basic block operand or "
968              "isIndirectBranch property",
969              MI);
970     }
971   }
972 
973   // Check types.
974   SmallVector<LLT, 4> Types;
975   for (unsigned I = 0, E = std::min(MCID.getNumOperands(), NumOps);
976        I != E; ++I) {
977     if (!MCID.OpInfo[I].isGenericType())
978       continue;
979     // Generic instructions specify type equality constraints between some of
980     // their operands. Make sure these are consistent.
981     size_t TypeIdx = MCID.OpInfo[I].getGenericTypeIndex();
982     Types.resize(std::max(TypeIdx + 1, Types.size()));
983 
984     const MachineOperand *MO = &MI->getOperand(I);
985     if (!MO->isReg()) {
986       report("generic instruction must use register operands", MI);
987       continue;
988     }
989 
990     LLT OpTy = MRI->getType(MO->getReg());
991     // Don't report a type mismatch if there is no actual mismatch, only a
992     // type missing, to reduce noise:
993     if (OpTy.isValid()) {
994       // Only the first valid type for a type index will be printed: don't
995       // overwrite it later so it's always clear which type was expected:
996       if (!Types[TypeIdx].isValid())
997         Types[TypeIdx] = OpTy;
998       else if (Types[TypeIdx] != OpTy)
999         report("Type mismatch in generic instruction", MO, I, OpTy);
1000     } else {
1001       // Generic instructions must have types attached to their operands.
1002       report("Generic instruction is missing a virtual register type", MO, I);
1003     }
1004   }
1005 
1006   // Generic opcodes must not have physical register operands.
1007   for (unsigned I = 0; I < MI->getNumOperands(); ++I) {
1008     const MachineOperand *MO = &MI->getOperand(I);
1009     if (MO->isReg() && Register::isPhysicalRegister(MO->getReg()))
1010       report("Generic instruction cannot have physical register", MO, I);
1011   }
1012 
1013   // Avoid out of bounds in checks below. This was already reported earlier.
1014   if (MI->getNumOperands() < MCID.getNumOperands())
1015     return;
1016 
1017   StringRef ErrorInfo;
1018   if (!TII->verifyInstruction(*MI, ErrorInfo))
1019     report(ErrorInfo.data(), MI);
1020 
1021   // Verify properties of various specific instruction types
1022   unsigned Opc = MI->getOpcode();
1023   switch (Opc) {
1024   case TargetOpcode::G_ASSERT_SEXT:
1025   case TargetOpcode::G_ASSERT_ZEXT: {
1026     std::string OpcName =
1027         Opc == TargetOpcode::G_ASSERT_ZEXT ? "G_ASSERT_ZEXT" : "G_ASSERT_SEXT";
1028     if (!MI->getOperand(2).isImm()) {
1029       report(Twine(OpcName, " expects an immediate operand #2"), MI);
1030       break;
1031     }
1032 
1033     Register Dst = MI->getOperand(0).getReg();
1034     Register Src = MI->getOperand(1).getReg();
1035     LLT SrcTy = MRI->getType(Src);
1036     int64_t Imm = MI->getOperand(2).getImm();
1037     if (Imm <= 0) {
1038       report(Twine(OpcName, " size must be >= 1"), MI);
1039       break;
1040     }
1041 
1042     if (Imm >= SrcTy.getScalarSizeInBits()) {
1043       report(Twine(OpcName, " size must be less than source bit width"), MI);
1044       break;
1045     }
1046 
1047     const RegisterBank *SrcRB = RBI->getRegBank(Src, *MRI, *TRI);
1048     const RegisterBank *DstRB = RBI->getRegBank(Dst, *MRI, *TRI);
1049 
1050     // Allow only the source bank to be set.
1051     if ((SrcRB && DstRB && SrcRB != DstRB) || (DstRB && !SrcRB)) {
1052       report(Twine(OpcName, " cannot change register bank"), MI);
1053       break;
1054     }
1055 
1056     // Don't allow a class change. Do allow member class->regbank.
1057     const TargetRegisterClass *DstRC = MRI->getRegClassOrNull(Dst);
1058     if (DstRC && DstRC != MRI->getRegClassOrNull(Src)) {
1059       report(
1060           Twine(OpcName, " source and destination register classes must match"),
1061           MI);
1062       break;
1063     }
1064 
1065     break;
1066   }
1067 
1068   case TargetOpcode::G_CONSTANT:
1069   case TargetOpcode::G_FCONSTANT: {
1070     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1071     if (DstTy.isVector())
1072       report("Instruction cannot use a vector result type", MI);
1073 
1074     if (MI->getOpcode() == TargetOpcode::G_CONSTANT) {
1075       if (!MI->getOperand(1).isCImm()) {
1076         report("G_CONSTANT operand must be cimm", MI);
1077         break;
1078       }
1079 
1080       const ConstantInt *CI = MI->getOperand(1).getCImm();
1081       if (CI->getBitWidth() != DstTy.getSizeInBits())
1082         report("inconsistent constant size", MI);
1083     } else {
1084       if (!MI->getOperand(1).isFPImm()) {
1085         report("G_FCONSTANT operand must be fpimm", MI);
1086         break;
1087       }
1088       const ConstantFP *CF = MI->getOperand(1).getFPImm();
1089 
1090       if (APFloat::getSizeInBits(CF->getValueAPF().getSemantics()) !=
1091           DstTy.getSizeInBits()) {
1092         report("inconsistent constant size", MI);
1093       }
1094     }
1095 
1096     break;
1097   }
1098   case TargetOpcode::G_LOAD:
1099   case TargetOpcode::G_STORE:
1100   case TargetOpcode::G_ZEXTLOAD:
1101   case TargetOpcode::G_SEXTLOAD: {
1102     LLT ValTy = MRI->getType(MI->getOperand(0).getReg());
1103     LLT PtrTy = MRI->getType(MI->getOperand(1).getReg());
1104     if (!PtrTy.isPointer())
1105       report("Generic memory instruction must access a pointer", MI);
1106 
1107     // Generic loads and stores must have a single MachineMemOperand
1108     // describing that access.
1109     if (!MI->hasOneMemOperand()) {
1110       report("Generic instruction accessing memory must have one mem operand",
1111              MI);
1112     } else {
1113       const MachineMemOperand &MMO = **MI->memoperands_begin();
1114       if (MI->getOpcode() == TargetOpcode::G_ZEXTLOAD ||
1115           MI->getOpcode() == TargetOpcode::G_SEXTLOAD) {
1116         if (MMO.getSizeInBits() >= ValTy.getSizeInBits())
1117           report("Generic extload must have a narrower memory type", MI);
1118       } else if (MI->getOpcode() == TargetOpcode::G_LOAD) {
1119         if (MMO.getSize() > ValTy.getSizeInBytes())
1120           report("load memory size cannot exceed result size", MI);
1121       } else if (MI->getOpcode() == TargetOpcode::G_STORE) {
1122         if (ValTy.getSizeInBytes() < MMO.getSize())
1123           report("store memory size cannot exceed value size", MI);
1124       }
1125 
1126       const AtomicOrdering Order = MMO.getSuccessOrdering();
1127       if (Opc == TargetOpcode::G_STORE) {
1128         if (Order == AtomicOrdering::Acquire ||
1129             Order == AtomicOrdering::AcquireRelease)
1130           report("atomic store cannot use acquire ordering", MI);
1131 
1132       } else {
1133         if (Order == AtomicOrdering::Release ||
1134             Order == AtomicOrdering::AcquireRelease)
1135           report("atomic load cannot use release ordering", MI);
1136       }
1137     }
1138 
1139     break;
1140   }
1141   case TargetOpcode::G_PHI: {
1142     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1143     if (!DstTy.isValid() || !all_of(drop_begin(MI->operands()),
1144                                     [this, &DstTy](const MachineOperand &MO) {
1145                                       if (!MO.isReg())
1146                                         return true;
1147                                       LLT Ty = MRI->getType(MO.getReg());
1148                                       if (!Ty.isValid() || (Ty != DstTy))
1149                                         return false;
1150                                       return true;
1151                                     }))
1152       report("Generic Instruction G_PHI has operands with incompatible/missing "
1153              "types",
1154              MI);
1155     break;
1156   }
1157   case TargetOpcode::G_BITCAST: {
1158     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1159     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1160     if (!DstTy.isValid() || !SrcTy.isValid())
1161       break;
1162 
1163     if (SrcTy.isPointer() != DstTy.isPointer())
1164       report("bitcast cannot convert between pointers and other types", MI);
1165 
1166     if (SrcTy.getSizeInBits() != DstTy.getSizeInBits())
1167       report("bitcast sizes must match", MI);
1168 
1169     if (SrcTy == DstTy)
1170       report("bitcast must change the type", MI);
1171 
1172     break;
1173   }
1174   case TargetOpcode::G_INTTOPTR:
1175   case TargetOpcode::G_PTRTOINT:
1176   case TargetOpcode::G_ADDRSPACE_CAST: {
1177     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1178     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1179     if (!DstTy.isValid() || !SrcTy.isValid())
1180       break;
1181 
1182     verifyVectorElementMatch(DstTy, SrcTy, MI);
1183 
1184     DstTy = DstTy.getScalarType();
1185     SrcTy = SrcTy.getScalarType();
1186 
1187     if (MI->getOpcode() == TargetOpcode::G_INTTOPTR) {
1188       if (!DstTy.isPointer())
1189         report("inttoptr result type must be a pointer", MI);
1190       if (SrcTy.isPointer())
1191         report("inttoptr source type must not be a pointer", MI);
1192     } else if (MI->getOpcode() == TargetOpcode::G_PTRTOINT) {
1193       if (!SrcTy.isPointer())
1194         report("ptrtoint source type must be a pointer", MI);
1195       if (DstTy.isPointer())
1196         report("ptrtoint result type must not be a pointer", MI);
1197     } else {
1198       assert(MI->getOpcode() == TargetOpcode::G_ADDRSPACE_CAST);
1199       if (!SrcTy.isPointer() || !DstTy.isPointer())
1200         report("addrspacecast types must be pointers", MI);
1201       else {
1202         if (SrcTy.getAddressSpace() == DstTy.getAddressSpace())
1203           report("addrspacecast must convert different address spaces", MI);
1204       }
1205     }
1206 
1207     break;
1208   }
1209   case TargetOpcode::G_PTR_ADD: {
1210     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1211     LLT PtrTy = MRI->getType(MI->getOperand(1).getReg());
1212     LLT OffsetTy = MRI->getType(MI->getOperand(2).getReg());
1213     if (!DstTy.isValid() || !PtrTy.isValid() || !OffsetTy.isValid())
1214       break;
1215 
1216     if (!PtrTy.getScalarType().isPointer())
1217       report("gep first operand must be a pointer", MI);
1218 
1219     if (OffsetTy.getScalarType().isPointer())
1220       report("gep offset operand must not be a pointer", MI);
1221 
1222     // TODO: Is the offset allowed to be a scalar with a vector?
1223     break;
1224   }
1225   case TargetOpcode::G_PTRMASK: {
1226     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1227     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1228     LLT MaskTy = MRI->getType(MI->getOperand(2).getReg());
1229     if (!DstTy.isValid() || !SrcTy.isValid() || !MaskTy.isValid())
1230       break;
1231 
1232     if (!DstTy.getScalarType().isPointer())
1233       report("ptrmask result type must be a pointer", MI);
1234 
1235     if (!MaskTy.getScalarType().isScalar())
1236       report("ptrmask mask type must be an integer", MI);
1237 
1238     verifyVectorElementMatch(DstTy, MaskTy, MI);
1239     break;
1240   }
1241   case TargetOpcode::G_SEXT:
1242   case TargetOpcode::G_ZEXT:
1243   case TargetOpcode::G_ANYEXT:
1244   case TargetOpcode::G_TRUNC:
1245   case TargetOpcode::G_FPEXT:
1246   case TargetOpcode::G_FPTRUNC: {
1247     // Number of operands and presense of types is already checked (and
1248     // reported in case of any issues), so no need to report them again. As
1249     // we're trying to report as many issues as possible at once, however, the
1250     // instructions aren't guaranteed to have the right number of operands or
1251     // types attached to them at this point
1252     assert(MCID.getNumOperands() == 2 && "Expected 2 operands G_*{EXT,TRUNC}");
1253     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1254     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1255     if (!DstTy.isValid() || !SrcTy.isValid())
1256       break;
1257 
1258     LLT DstElTy = DstTy.getScalarType();
1259     LLT SrcElTy = SrcTy.getScalarType();
1260     if (DstElTy.isPointer() || SrcElTy.isPointer())
1261       report("Generic extend/truncate can not operate on pointers", MI);
1262 
1263     verifyVectorElementMatch(DstTy, SrcTy, MI);
1264 
1265     unsigned DstSize = DstElTy.getSizeInBits();
1266     unsigned SrcSize = SrcElTy.getSizeInBits();
1267     switch (MI->getOpcode()) {
1268     default:
1269       if (DstSize <= SrcSize)
1270         report("Generic extend has destination type no larger than source", MI);
1271       break;
1272     case TargetOpcode::G_TRUNC:
1273     case TargetOpcode::G_FPTRUNC:
1274       if (DstSize >= SrcSize)
1275         report("Generic truncate has destination type no smaller than source",
1276                MI);
1277       break;
1278     }
1279     break;
1280   }
1281   case TargetOpcode::G_SELECT: {
1282     LLT SelTy = MRI->getType(MI->getOperand(0).getReg());
1283     LLT CondTy = MRI->getType(MI->getOperand(1).getReg());
1284     if (!SelTy.isValid() || !CondTy.isValid())
1285       break;
1286 
1287     // Scalar condition select on a vector is valid.
1288     if (CondTy.isVector())
1289       verifyVectorElementMatch(SelTy, CondTy, MI);
1290     break;
1291   }
1292   case TargetOpcode::G_MERGE_VALUES: {
1293     // G_MERGE_VALUES should only be used to merge scalars into a larger scalar,
1294     // e.g. s2N = MERGE sN, sN
1295     // Merging multiple scalars into a vector is not allowed, should use
1296     // G_BUILD_VECTOR for that.
1297     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1298     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1299     if (DstTy.isVector() || SrcTy.isVector())
1300       report("G_MERGE_VALUES cannot operate on vectors", MI);
1301 
1302     const unsigned NumOps = MI->getNumOperands();
1303     if (DstTy.getSizeInBits() != SrcTy.getSizeInBits() * (NumOps - 1))
1304       report("G_MERGE_VALUES result size is inconsistent", MI);
1305 
1306     for (unsigned I = 2; I != NumOps; ++I) {
1307       if (MRI->getType(MI->getOperand(I).getReg()) != SrcTy)
1308         report("G_MERGE_VALUES source types do not match", MI);
1309     }
1310 
1311     break;
1312   }
1313   case TargetOpcode::G_UNMERGE_VALUES: {
1314     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1315     LLT SrcTy = MRI->getType(MI->getOperand(MI->getNumOperands()-1).getReg());
1316     // For now G_UNMERGE can split vectors.
1317     for (unsigned i = 0; i < MI->getNumOperands()-1; ++i) {
1318       if (MRI->getType(MI->getOperand(i).getReg()) != DstTy)
1319         report("G_UNMERGE_VALUES destination types do not match", MI);
1320     }
1321     if (SrcTy.getSizeInBits() !=
1322         (DstTy.getSizeInBits() * (MI->getNumOperands() - 1))) {
1323       report("G_UNMERGE_VALUES source operand does not cover dest operands",
1324              MI);
1325     }
1326     break;
1327   }
1328   case TargetOpcode::G_BUILD_VECTOR: {
1329     // Source types must be scalars, dest type a vector. Total size of scalars
1330     // must match the dest vector size.
1331     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1332     LLT SrcEltTy = MRI->getType(MI->getOperand(1).getReg());
1333     if (!DstTy.isVector() || SrcEltTy.isVector()) {
1334       report("G_BUILD_VECTOR must produce a vector from scalar operands", MI);
1335       break;
1336     }
1337 
1338     if (DstTy.getElementType() != SrcEltTy)
1339       report("G_BUILD_VECTOR result element type must match source type", MI);
1340 
1341     if (DstTy.getNumElements() != MI->getNumOperands() - 1)
1342       report("G_BUILD_VECTOR must have an operand for each elemement", MI);
1343 
1344     for (const MachineOperand &MO : llvm::drop_begin(MI->operands(), 2))
1345       if (MRI->getType(MI->getOperand(1).getReg()) != MRI->getType(MO.getReg()))
1346         report("G_BUILD_VECTOR source operand types are not homogeneous", MI);
1347 
1348     break;
1349   }
1350   case TargetOpcode::G_BUILD_VECTOR_TRUNC: {
1351     // Source types must be scalars, dest type a vector. Scalar types must be
1352     // larger than the dest vector elt type, as this is a truncating operation.
1353     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1354     LLT SrcEltTy = MRI->getType(MI->getOperand(1).getReg());
1355     if (!DstTy.isVector() || SrcEltTy.isVector())
1356       report("G_BUILD_VECTOR_TRUNC must produce a vector from scalar operands",
1357              MI);
1358     for (const MachineOperand &MO : llvm::drop_begin(MI->operands(), 2))
1359       if (MRI->getType(MI->getOperand(1).getReg()) != MRI->getType(MO.getReg()))
1360         report("G_BUILD_VECTOR_TRUNC source operand types are not homogeneous",
1361                MI);
1362     if (SrcEltTy.getSizeInBits() <= DstTy.getElementType().getSizeInBits())
1363       report("G_BUILD_VECTOR_TRUNC source operand types are not larger than "
1364              "dest elt type",
1365              MI);
1366     break;
1367   }
1368   case TargetOpcode::G_CONCAT_VECTORS: {
1369     // Source types should be vectors, and total size should match the dest
1370     // vector size.
1371     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1372     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1373     if (!DstTy.isVector() || !SrcTy.isVector())
1374       report("G_CONCAT_VECTOR requires vector source and destination operands",
1375              MI);
1376 
1377     if (MI->getNumOperands() < 3)
1378       report("G_CONCAT_VECTOR requires at least 2 source operands", MI);
1379 
1380     for (const MachineOperand &MO : llvm::drop_begin(MI->operands(), 2))
1381       if (MRI->getType(MI->getOperand(1).getReg()) != MRI->getType(MO.getReg()))
1382         report("G_CONCAT_VECTOR source operand types are not homogeneous", MI);
1383     if (DstTy.getNumElements() !=
1384         SrcTy.getNumElements() * (MI->getNumOperands() - 1))
1385       report("G_CONCAT_VECTOR num dest and source elements should match", MI);
1386     break;
1387   }
1388   case TargetOpcode::G_ICMP:
1389   case TargetOpcode::G_FCMP: {
1390     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1391     LLT SrcTy = MRI->getType(MI->getOperand(2).getReg());
1392 
1393     if ((DstTy.isVector() != SrcTy.isVector()) ||
1394         (DstTy.isVector() && DstTy.getNumElements() != SrcTy.getNumElements()))
1395       report("Generic vector icmp/fcmp must preserve number of lanes", MI);
1396 
1397     break;
1398   }
1399   case TargetOpcode::G_EXTRACT: {
1400     const MachineOperand &SrcOp = MI->getOperand(1);
1401     if (!SrcOp.isReg()) {
1402       report("extract source must be a register", MI);
1403       break;
1404     }
1405 
1406     const MachineOperand &OffsetOp = MI->getOperand(2);
1407     if (!OffsetOp.isImm()) {
1408       report("extract offset must be a constant", MI);
1409       break;
1410     }
1411 
1412     unsigned DstSize = MRI->getType(MI->getOperand(0).getReg()).getSizeInBits();
1413     unsigned SrcSize = MRI->getType(SrcOp.getReg()).getSizeInBits();
1414     if (SrcSize == DstSize)
1415       report("extract source must be larger than result", MI);
1416 
1417     if (DstSize + OffsetOp.getImm() > SrcSize)
1418       report("extract reads past end of register", MI);
1419     break;
1420   }
1421   case TargetOpcode::G_INSERT: {
1422     const MachineOperand &SrcOp = MI->getOperand(2);
1423     if (!SrcOp.isReg()) {
1424       report("insert source must be a register", MI);
1425       break;
1426     }
1427 
1428     const MachineOperand &OffsetOp = MI->getOperand(3);
1429     if (!OffsetOp.isImm()) {
1430       report("insert offset must be a constant", MI);
1431       break;
1432     }
1433 
1434     unsigned DstSize = MRI->getType(MI->getOperand(0).getReg()).getSizeInBits();
1435     unsigned SrcSize = MRI->getType(SrcOp.getReg()).getSizeInBits();
1436 
1437     if (DstSize <= SrcSize)
1438       report("inserted size must be smaller than total register", MI);
1439 
1440     if (SrcSize + OffsetOp.getImm() > DstSize)
1441       report("insert writes past end of register", MI);
1442 
1443     break;
1444   }
1445   case TargetOpcode::G_JUMP_TABLE: {
1446     if (!MI->getOperand(1).isJTI())
1447       report("G_JUMP_TABLE source operand must be a jump table index", MI);
1448     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1449     if (!DstTy.isPointer())
1450       report("G_JUMP_TABLE dest operand must have a pointer type", MI);
1451     break;
1452   }
1453   case TargetOpcode::G_BRJT: {
1454     if (!MRI->getType(MI->getOperand(0).getReg()).isPointer())
1455       report("G_BRJT src operand 0 must be a pointer type", MI);
1456 
1457     if (!MI->getOperand(1).isJTI())
1458       report("G_BRJT src operand 1 must be a jump table index", MI);
1459 
1460     const auto &IdxOp = MI->getOperand(2);
1461     if (!IdxOp.isReg() || MRI->getType(IdxOp.getReg()).isPointer())
1462       report("G_BRJT src operand 2 must be a scalar reg type", MI);
1463     break;
1464   }
1465   case TargetOpcode::G_INTRINSIC:
1466   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS: {
1467     // TODO: Should verify number of def and use operands, but the current
1468     // interface requires passing in IR types for mangling.
1469     const MachineOperand &IntrIDOp = MI->getOperand(MI->getNumExplicitDefs());
1470     if (!IntrIDOp.isIntrinsicID()) {
1471       report("G_INTRINSIC first src operand must be an intrinsic ID", MI);
1472       break;
1473     }
1474 
1475     bool NoSideEffects = MI->getOpcode() == TargetOpcode::G_INTRINSIC;
1476     unsigned IntrID = IntrIDOp.getIntrinsicID();
1477     if (IntrID != 0 && IntrID < Intrinsic::num_intrinsics) {
1478       AttributeList Attrs = Intrinsic::getAttributes(
1479           MF->getFunction().getContext(), static_cast<Intrinsic::ID>(IntrID));
1480       bool DeclHasSideEffects = !Attrs.getMemoryEffects().doesNotAccessMemory();
1481       if (NoSideEffects && DeclHasSideEffects) {
1482         report("G_INTRINSIC used with intrinsic that accesses memory", MI);
1483         break;
1484       }
1485       if (!NoSideEffects && !DeclHasSideEffects) {
1486         report("G_INTRINSIC_W_SIDE_EFFECTS used with readnone intrinsic", MI);
1487         break;
1488       }
1489     }
1490 
1491     break;
1492   }
1493   case TargetOpcode::G_SEXT_INREG: {
1494     if (!MI->getOperand(2).isImm()) {
1495       report("G_SEXT_INREG expects an immediate operand #2", MI);
1496       break;
1497     }
1498 
1499     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1500     int64_t Imm = MI->getOperand(2).getImm();
1501     if (Imm <= 0)
1502       report("G_SEXT_INREG size must be >= 1", MI);
1503     if (Imm >= SrcTy.getScalarSizeInBits())
1504       report("G_SEXT_INREG size must be less than source bit width", MI);
1505     break;
1506   }
1507   case TargetOpcode::G_SHUFFLE_VECTOR: {
1508     const MachineOperand &MaskOp = MI->getOperand(3);
1509     if (!MaskOp.isShuffleMask()) {
1510       report("Incorrect mask operand type for G_SHUFFLE_VECTOR", MI);
1511       break;
1512     }
1513 
1514     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1515     LLT Src0Ty = MRI->getType(MI->getOperand(1).getReg());
1516     LLT Src1Ty = MRI->getType(MI->getOperand(2).getReg());
1517 
1518     if (Src0Ty != Src1Ty)
1519       report("Source operands must be the same type", MI);
1520 
1521     if (Src0Ty.getScalarType() != DstTy.getScalarType())
1522       report("G_SHUFFLE_VECTOR cannot change element type", MI);
1523 
1524     // Don't check that all operands are vector because scalars are used in
1525     // place of 1 element vectors.
1526     int SrcNumElts = Src0Ty.isVector() ? Src0Ty.getNumElements() : 1;
1527     int DstNumElts = DstTy.isVector() ? DstTy.getNumElements() : 1;
1528 
1529     ArrayRef<int> MaskIdxes = MaskOp.getShuffleMask();
1530 
1531     if (static_cast<int>(MaskIdxes.size()) != DstNumElts)
1532       report("Wrong result type for shufflemask", MI);
1533 
1534     for (int Idx : MaskIdxes) {
1535       if (Idx < 0)
1536         continue;
1537 
1538       if (Idx >= 2 * SrcNumElts)
1539         report("Out of bounds shuffle index", MI);
1540     }
1541 
1542     break;
1543   }
1544   case TargetOpcode::G_DYN_STACKALLOC: {
1545     const MachineOperand &DstOp = MI->getOperand(0);
1546     const MachineOperand &AllocOp = MI->getOperand(1);
1547     const MachineOperand &AlignOp = MI->getOperand(2);
1548 
1549     if (!DstOp.isReg() || !MRI->getType(DstOp.getReg()).isPointer()) {
1550       report("dst operand 0 must be a pointer type", MI);
1551       break;
1552     }
1553 
1554     if (!AllocOp.isReg() || !MRI->getType(AllocOp.getReg()).isScalar()) {
1555       report("src operand 1 must be a scalar reg type", MI);
1556       break;
1557     }
1558 
1559     if (!AlignOp.isImm()) {
1560       report("src operand 2 must be an immediate type", MI);
1561       break;
1562     }
1563     break;
1564   }
1565   case TargetOpcode::G_MEMCPY_INLINE:
1566   case TargetOpcode::G_MEMCPY:
1567   case TargetOpcode::G_MEMMOVE: {
1568     ArrayRef<MachineMemOperand *> MMOs = MI->memoperands();
1569     if (MMOs.size() != 2) {
1570       report("memcpy/memmove must have 2 memory operands", MI);
1571       break;
1572     }
1573 
1574     if ((!MMOs[0]->isStore() || MMOs[0]->isLoad()) ||
1575         (MMOs[1]->isStore() || !MMOs[1]->isLoad())) {
1576       report("wrong memory operand types", MI);
1577       break;
1578     }
1579 
1580     if (MMOs[0]->getSize() != MMOs[1]->getSize())
1581       report("inconsistent memory operand sizes", MI);
1582 
1583     LLT DstPtrTy = MRI->getType(MI->getOperand(0).getReg());
1584     LLT SrcPtrTy = MRI->getType(MI->getOperand(1).getReg());
1585 
1586     if (!DstPtrTy.isPointer() || !SrcPtrTy.isPointer()) {
1587       report("memory instruction operand must be a pointer", MI);
1588       break;
1589     }
1590 
1591     if (DstPtrTy.getAddressSpace() != MMOs[0]->getAddrSpace())
1592       report("inconsistent store address space", MI);
1593     if (SrcPtrTy.getAddressSpace() != MMOs[1]->getAddrSpace())
1594       report("inconsistent load address space", MI);
1595 
1596     if (Opc != TargetOpcode::G_MEMCPY_INLINE)
1597       if (!MI->getOperand(3).isImm() || (MI->getOperand(3).getImm() & ~1LL))
1598         report("'tail' flag (operand 3) must be an immediate 0 or 1", MI);
1599 
1600     break;
1601   }
1602   case TargetOpcode::G_BZERO:
1603   case TargetOpcode::G_MEMSET: {
1604     ArrayRef<MachineMemOperand *> MMOs = MI->memoperands();
1605     std::string Name = Opc == TargetOpcode::G_MEMSET ? "memset" : "bzero";
1606     if (MMOs.size() != 1) {
1607       report(Twine(Name, " must have 1 memory operand"), MI);
1608       break;
1609     }
1610 
1611     if ((!MMOs[0]->isStore() || MMOs[0]->isLoad())) {
1612       report(Twine(Name, " memory operand must be a store"), MI);
1613       break;
1614     }
1615 
1616     LLT DstPtrTy = MRI->getType(MI->getOperand(0).getReg());
1617     if (!DstPtrTy.isPointer()) {
1618       report(Twine(Name, " operand must be a pointer"), MI);
1619       break;
1620     }
1621 
1622     if (DstPtrTy.getAddressSpace() != MMOs[0]->getAddrSpace())
1623       report("inconsistent " + Twine(Name, " address space"), MI);
1624 
1625     if (!MI->getOperand(MI->getNumOperands() - 1).isImm() ||
1626         (MI->getOperand(MI->getNumOperands() - 1).getImm() & ~1LL))
1627       report("'tail' flag (last operand) must be an immediate 0 or 1", MI);
1628 
1629     break;
1630   }
1631   case TargetOpcode::G_VECREDUCE_SEQ_FADD:
1632   case TargetOpcode::G_VECREDUCE_SEQ_FMUL: {
1633     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1634     LLT Src1Ty = MRI->getType(MI->getOperand(1).getReg());
1635     LLT Src2Ty = MRI->getType(MI->getOperand(2).getReg());
1636     if (!DstTy.isScalar())
1637       report("Vector reduction requires a scalar destination type", MI);
1638     if (!Src1Ty.isScalar())
1639       report("Sequential FADD/FMUL vector reduction requires a scalar 1st operand", MI);
1640     if (!Src2Ty.isVector())
1641       report("Sequential FADD/FMUL vector reduction must have a vector 2nd operand", MI);
1642     break;
1643   }
1644   case TargetOpcode::G_VECREDUCE_FADD:
1645   case TargetOpcode::G_VECREDUCE_FMUL:
1646   case TargetOpcode::G_VECREDUCE_FMAX:
1647   case TargetOpcode::G_VECREDUCE_FMIN:
1648   case TargetOpcode::G_VECREDUCE_ADD:
1649   case TargetOpcode::G_VECREDUCE_MUL:
1650   case TargetOpcode::G_VECREDUCE_AND:
1651   case TargetOpcode::G_VECREDUCE_OR:
1652   case TargetOpcode::G_VECREDUCE_XOR:
1653   case TargetOpcode::G_VECREDUCE_SMAX:
1654   case TargetOpcode::G_VECREDUCE_SMIN:
1655   case TargetOpcode::G_VECREDUCE_UMAX:
1656   case TargetOpcode::G_VECREDUCE_UMIN: {
1657     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1658     if (!DstTy.isScalar())
1659       report("Vector reduction requires a scalar destination type", MI);
1660     break;
1661   }
1662 
1663   case TargetOpcode::G_SBFX:
1664   case TargetOpcode::G_UBFX: {
1665     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
1666     if (DstTy.isVector()) {
1667       report("Bitfield extraction is not supported on vectors", MI);
1668       break;
1669     }
1670     break;
1671   }
1672   case TargetOpcode::G_SHL:
1673   case TargetOpcode::G_LSHR:
1674   case TargetOpcode::G_ASHR:
1675   case TargetOpcode::G_ROTR:
1676   case TargetOpcode::G_ROTL: {
1677     LLT Src1Ty = MRI->getType(MI->getOperand(1).getReg());
1678     LLT Src2Ty = MRI->getType(MI->getOperand(2).getReg());
1679     if (Src1Ty.isVector() != Src2Ty.isVector()) {
1680       report("Shifts and rotates require operands to be either all scalars or "
1681              "all vectors",
1682              MI);
1683       break;
1684     }
1685     break;
1686   }
1687   case TargetOpcode::G_LLROUND:
1688   case TargetOpcode::G_LROUND: {
1689     verifyAllRegOpsScalar(*MI, *MRI);
1690     break;
1691   }
1692   case TargetOpcode::G_IS_FPCLASS: {
1693     LLT DestTy = MRI->getType(MI->getOperand(0).getReg());
1694     LLT DestEltTy = DestTy.getScalarType();
1695     if (!DestEltTy.isScalar()) {
1696       report("Destination must be a scalar or vector of scalars", MI);
1697       break;
1698     }
1699     LLT SrcTy = MRI->getType(MI->getOperand(1).getReg());
1700     LLT SrcEltTy = SrcTy.getScalarType();
1701     if (!SrcEltTy.isScalar()) {
1702       report("Source must be a scalar or vector of scalars", MI);
1703       break;
1704     }
1705     if (!verifyVectorElementMatch(DestTy, SrcTy, MI))
1706       break;
1707     const MachineOperand &TestMO = MI->getOperand(2);
1708     if (!TestMO.isImm()) {
1709       report("floating-point class set (operand 2) must be an immediate", MI);
1710       break;
1711     }
1712     int64_t Test = TestMO.getImm();
1713     if (Test < 0 || Test > fcAllFlags) {
1714       report("Incorrect floating-point class set (operand 2)", MI);
1715       break;
1716     }
1717     break;
1718   }
1719   case TargetOpcode::G_ASSERT_ALIGN: {
1720     if (MI->getOperand(2).getImm() < 1)
1721       report("alignment immediate must be >= 1", MI);
1722     break;
1723   }
1724   default:
1725     break;
1726   }
1727 }
1728 
1729 void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
1730   const MCInstrDesc &MCID = MI->getDesc();
1731   if (MI->getNumOperands() < MCID.getNumOperands()) {
1732     report("Too few operands", MI);
1733     errs() << MCID.getNumOperands() << " operands expected, but "
1734            << MI->getNumOperands() << " given.\n";
1735   }
1736 
1737   if (MI->isPHI()) {
1738     if (MF->getProperties().hasProperty(
1739             MachineFunctionProperties::Property::NoPHIs))
1740       report("Found PHI instruction with NoPHIs property set", MI);
1741 
1742     if (FirstNonPHI)
1743       report("Found PHI instruction after non-PHI", MI);
1744   } else if (FirstNonPHI == nullptr)
1745     FirstNonPHI = MI;
1746 
1747   // Check the tied operands.
1748   if (MI->isInlineAsm())
1749     verifyInlineAsm(MI);
1750 
1751   // Check that unspillable terminators define a reg and have at most one use.
1752   if (TII->isUnspillableTerminator(MI)) {
1753     if (!MI->getOperand(0).isReg() || !MI->getOperand(0).isDef())
1754       report("Unspillable Terminator does not define a reg", MI);
1755     Register Def = MI->getOperand(0).getReg();
1756     if (Def.isVirtual() &&
1757         !MF->getProperties().hasProperty(
1758             MachineFunctionProperties::Property::NoPHIs) &&
1759         std::distance(MRI->use_nodbg_begin(Def), MRI->use_nodbg_end()) > 1)
1760       report("Unspillable Terminator expected to have at most one use!", MI);
1761   }
1762 
1763   // A fully-formed DBG_VALUE must have a location. Ignore partially formed
1764   // DBG_VALUEs: these are convenient to use in tests, but should never get
1765   // generated.
1766   if (MI->isDebugValue() && MI->getNumOperands() == 4)
1767     if (!MI->getDebugLoc())
1768       report("Missing DebugLoc for debug instruction", MI);
1769 
1770   // Meta instructions should never be the subject of debug value tracking,
1771   // they don't create a value in the output program at all.
1772   if (MI->isMetaInstruction() && MI->peekDebugInstrNum())
1773     report("Metadata instruction should not have a value tracking number", MI);
1774 
1775   // Check the MachineMemOperands for basic consistency.
1776   for (MachineMemOperand *Op : MI->memoperands()) {
1777     if (Op->isLoad() && !MI->mayLoad())
1778       report("Missing mayLoad flag", MI);
1779     if (Op->isStore() && !MI->mayStore())
1780       report("Missing mayStore flag", MI);
1781   }
1782 
1783   // Debug values must not have a slot index.
1784   // Other instructions must have one, unless they are inside a bundle.
1785   if (LiveInts) {
1786     bool mapped = !LiveInts->isNotInMIMap(*MI);
1787     if (MI->isDebugOrPseudoInstr()) {
1788       if (mapped)
1789         report("Debug instruction has a slot index", MI);
1790     } else if (MI->isInsideBundle()) {
1791       if (mapped)
1792         report("Instruction inside bundle has a slot index", MI);
1793     } else {
1794       if (!mapped)
1795         report("Missing slot index", MI);
1796     }
1797   }
1798 
1799   unsigned Opc = MCID.getOpcode();
1800   if (isPreISelGenericOpcode(Opc) || isPreISelGenericOptimizationHint(Opc)) {
1801     verifyPreISelGenericInstruction(MI);
1802     return;
1803   }
1804 
1805   StringRef ErrorInfo;
1806   if (!TII->verifyInstruction(*MI, ErrorInfo))
1807     report(ErrorInfo.data(), MI);
1808 
1809   // Verify properties of various specific instruction types
1810   switch (MI->getOpcode()) {
1811   case TargetOpcode::COPY: {
1812     const MachineOperand &DstOp = MI->getOperand(0);
1813     const MachineOperand &SrcOp = MI->getOperand(1);
1814     const Register SrcReg = SrcOp.getReg();
1815     const Register DstReg = DstOp.getReg();
1816 
1817     LLT DstTy = MRI->getType(DstReg);
1818     LLT SrcTy = MRI->getType(SrcReg);
1819     if (SrcTy.isValid() && DstTy.isValid()) {
1820       // If both types are valid, check that the types are the same.
1821       if (SrcTy != DstTy) {
1822         report("Copy Instruction is illegal with mismatching types", MI);
1823         errs() << "Def = " << DstTy << ", Src = " << SrcTy << "\n";
1824       }
1825 
1826       break;
1827     }
1828 
1829     if (!SrcTy.isValid() && !DstTy.isValid())
1830       break;
1831 
1832     // If we have only one valid type, this is likely a copy between a virtual
1833     // and physical register.
1834     unsigned SrcSize = 0;
1835     unsigned DstSize = 0;
1836     if (SrcReg.isPhysical() && DstTy.isValid()) {
1837       const TargetRegisterClass *SrcRC =
1838           TRI->getMinimalPhysRegClassLLT(SrcReg, DstTy);
1839       if (SrcRC)
1840         SrcSize = TRI->getRegSizeInBits(*SrcRC);
1841     }
1842 
1843     if (SrcSize == 0)
1844       SrcSize = TRI->getRegSizeInBits(SrcReg, *MRI);
1845 
1846     if (DstReg.isPhysical() && SrcTy.isValid()) {
1847       const TargetRegisterClass *DstRC =
1848           TRI->getMinimalPhysRegClassLLT(DstReg, SrcTy);
1849       if (DstRC)
1850         DstSize = TRI->getRegSizeInBits(*DstRC);
1851     }
1852 
1853     if (DstSize == 0)
1854       DstSize = TRI->getRegSizeInBits(DstReg, *MRI);
1855 
1856     if (SrcSize != 0 && DstSize != 0 && SrcSize != DstSize) {
1857       if (!DstOp.getSubReg() && !SrcOp.getSubReg()) {
1858         report("Copy Instruction is illegal with mismatching sizes", MI);
1859         errs() << "Def Size = " << DstSize << ", Src Size = " << SrcSize
1860                << "\n";
1861       }
1862     }
1863     break;
1864   }
1865   case TargetOpcode::STATEPOINT: {
1866     StatepointOpers SO(MI);
1867     if (!MI->getOperand(SO.getIDPos()).isImm() ||
1868         !MI->getOperand(SO.getNBytesPos()).isImm() ||
1869         !MI->getOperand(SO.getNCallArgsPos()).isImm()) {
1870       report("meta operands to STATEPOINT not constant!", MI);
1871       break;
1872     }
1873 
1874     auto VerifyStackMapConstant = [&](unsigned Offset) {
1875       if (Offset >= MI->getNumOperands()) {
1876         report("stack map constant to STATEPOINT is out of range!", MI);
1877         return;
1878       }
1879       if (!MI->getOperand(Offset - 1).isImm() ||
1880           MI->getOperand(Offset - 1).getImm() != StackMaps::ConstantOp ||
1881           !MI->getOperand(Offset).isImm())
1882         report("stack map constant to STATEPOINT not well formed!", MI);
1883     };
1884     VerifyStackMapConstant(SO.getCCIdx());
1885     VerifyStackMapConstant(SO.getFlagsIdx());
1886     VerifyStackMapConstant(SO.getNumDeoptArgsIdx());
1887     VerifyStackMapConstant(SO.getNumGCPtrIdx());
1888     VerifyStackMapConstant(SO.getNumAllocaIdx());
1889     VerifyStackMapConstant(SO.getNumGcMapEntriesIdx());
1890 
1891     // Verify that all explicit statepoint defs are tied to gc operands as
1892     // they are expected to be a relocation of gc operands.
1893     unsigned FirstGCPtrIdx = SO.getFirstGCPtrIdx();
1894     unsigned LastGCPtrIdx = SO.getNumAllocaIdx() - 2;
1895     for (unsigned Idx = 0; Idx < MI->getNumDefs(); Idx++) {
1896       unsigned UseOpIdx;
1897       if (!MI->isRegTiedToUseOperand(Idx, &UseOpIdx)) {
1898         report("STATEPOINT defs expected to be tied", MI);
1899         break;
1900       }
1901       if (UseOpIdx < FirstGCPtrIdx || UseOpIdx > LastGCPtrIdx) {
1902         report("STATEPOINT def tied to non-gc operand", MI);
1903         break;
1904       }
1905     }
1906 
1907     // TODO: verify we have properly encoded deopt arguments
1908   } break;
1909   case TargetOpcode::INSERT_SUBREG: {
1910     unsigned InsertedSize;
1911     if (unsigned SubIdx = MI->getOperand(2).getSubReg())
1912       InsertedSize = TRI->getSubRegIdxSize(SubIdx);
1913     else
1914       InsertedSize = TRI->getRegSizeInBits(MI->getOperand(2).getReg(), *MRI);
1915     unsigned SubRegSize = TRI->getSubRegIdxSize(MI->getOperand(3).getImm());
1916     if (SubRegSize < InsertedSize) {
1917       report("INSERT_SUBREG expected inserted value to have equal or lesser "
1918              "size than the subreg it was inserted into", MI);
1919       break;
1920     }
1921   } break;
1922   case TargetOpcode::REG_SEQUENCE: {
1923     unsigned NumOps = MI->getNumOperands();
1924     if (!(NumOps & 1)) {
1925       report("Invalid number of operands for REG_SEQUENCE", MI);
1926       break;
1927     }
1928 
1929     for (unsigned I = 1; I != NumOps; I += 2) {
1930       const MachineOperand &RegOp = MI->getOperand(I);
1931       const MachineOperand &SubRegOp = MI->getOperand(I + 1);
1932 
1933       if (!RegOp.isReg())
1934         report("Invalid register operand for REG_SEQUENCE", &RegOp, I);
1935 
1936       if (!SubRegOp.isImm() || SubRegOp.getImm() == 0 ||
1937           SubRegOp.getImm() >= TRI->getNumSubRegIndices()) {
1938         report("Invalid subregister index operand for REG_SEQUENCE",
1939                &SubRegOp, I + 1);
1940       }
1941     }
1942 
1943     Register DstReg = MI->getOperand(0).getReg();
1944     if (DstReg.isPhysical())
1945       report("REG_SEQUENCE does not support physical register results", MI);
1946 
1947     if (MI->getOperand(0).getSubReg())
1948       report("Invalid subreg result for REG_SEQUENCE", MI);
1949 
1950     break;
1951   }
1952   }
1953 }
1954 
1955 void
1956 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
1957   const MachineInstr *MI = MO->getParent();
1958   const MCInstrDesc &MCID = MI->getDesc();
1959   unsigned NumDefs = MCID.getNumDefs();
1960   if (MCID.getOpcode() == TargetOpcode::PATCHPOINT)
1961     NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0;
1962 
1963   // The first MCID.NumDefs operands must be explicit register defines
1964   if (MONum < NumDefs) {
1965     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1966     if (!MO->isReg())
1967       report("Explicit definition must be a register", MO, MONum);
1968     else if (!MO->isDef() && !MCOI.isOptionalDef())
1969       report("Explicit definition marked as use", MO, MONum);
1970     else if (MO->isImplicit())
1971       report("Explicit definition marked as implicit", MO, MONum);
1972   } else if (MONum < MCID.getNumOperands()) {
1973     const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1974     // Don't check if it's the last operand in a variadic instruction. See,
1975     // e.g., LDM_RET in the arm back end. Check non-variadic operands only.
1976     bool IsOptional = MI->isVariadic() && MONum == MCID.getNumOperands() - 1;
1977     if (!IsOptional) {
1978       if (MO->isReg()) {
1979         if (MO->isDef() && !MCOI.isOptionalDef() && !MCID.variadicOpsAreDefs())
1980           report("Explicit operand marked as def", MO, MONum);
1981         if (MO->isImplicit())
1982           report("Explicit operand marked as implicit", MO, MONum);
1983       }
1984 
1985       // Check that an instruction has register operands only as expected.
1986       if (MCOI.OperandType == MCOI::OPERAND_REGISTER &&
1987           !MO->isReg() && !MO->isFI())
1988         report("Expected a register operand.", MO, MONum);
1989       if (MO->isReg()) {
1990         if (MCOI.OperandType == MCOI::OPERAND_IMMEDIATE ||
1991             (MCOI.OperandType == MCOI::OPERAND_PCREL &&
1992              !TII->isPCRelRegisterOperandLegal(*MO)))
1993           report("Expected a non-register operand.", MO, MONum);
1994       }
1995     }
1996 
1997     int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
1998     if (TiedTo != -1) {
1999       if (!MO->isReg())
2000         report("Tied use must be a register", MO, MONum);
2001       else if (!MO->isTied())
2002         report("Operand should be tied", MO, MONum);
2003       else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
2004         report("Tied def doesn't match MCInstrDesc", MO, MONum);
2005       else if (Register::isPhysicalRegister(MO->getReg())) {
2006         const MachineOperand &MOTied = MI->getOperand(TiedTo);
2007         if (!MOTied.isReg())
2008           report("Tied counterpart must be a register", &MOTied, TiedTo);
2009         else if (Register::isPhysicalRegister(MOTied.getReg()) &&
2010                  MO->getReg() != MOTied.getReg())
2011           report("Tied physical registers must match.", &MOTied, TiedTo);
2012       }
2013     } else if (MO->isReg() && MO->isTied())
2014       report("Explicit operand should not be tied", MO, MONum);
2015   } else {
2016     // ARM adds %reg0 operands to indicate predicates. We'll allow that.
2017     if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
2018       report("Extra explicit operand on non-variadic instruction", MO, MONum);
2019   }
2020 
2021   switch (MO->getType()) {
2022   case MachineOperand::MO_Register: {
2023     // Verify debug flag on debug instructions. Check this first because reg0
2024     // indicates an undefined debug value.
2025     if (MI->isDebugInstr() && MO->isUse()) {
2026       if (!MO->isDebug())
2027         report("Register operand must be marked debug", MO, MONum);
2028     } else if (MO->isDebug()) {
2029       report("Register operand must not be marked debug", MO, MONum);
2030     }
2031 
2032     const Register Reg = MO->getReg();
2033     if (!Reg)
2034       return;
2035     if (MRI->tracksLiveness() && !MI->isDebugInstr())
2036       checkLiveness(MO, MONum);
2037 
2038     if (MO->isDef() && MO->isUndef() && !MO->getSubReg() &&
2039         MO->getReg().isVirtual()) // TODO: Apply to physregs too
2040       report("Undef virtual register def operands require a subregister", MO, MONum);
2041 
2042     // Verify the consistency of tied operands.
2043     if (MO->isTied()) {
2044       unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
2045       const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
2046       if (!OtherMO.isReg())
2047         report("Must be tied to a register", MO, MONum);
2048       if (!OtherMO.isTied())
2049         report("Missing tie flags on tied operand", MO, MONum);
2050       if (MI->findTiedOperandIdx(OtherIdx) != MONum)
2051         report("Inconsistent tie links", MO, MONum);
2052       if (MONum < MCID.getNumDefs()) {
2053         if (OtherIdx < MCID.getNumOperands()) {
2054           if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
2055             report("Explicit def tied to explicit use without tie constraint",
2056                    MO, MONum);
2057         } else {
2058           if (!OtherMO.isImplicit())
2059             report("Explicit def should be tied to implicit use", MO, MONum);
2060         }
2061       }
2062     }
2063 
2064     // Verify two-address constraints after the twoaddressinstruction pass.
2065     // Both twoaddressinstruction pass and phi-node-elimination pass call
2066     // MRI->leaveSSA() to set MF as NoSSA, we should do the verification after
2067     // twoaddressinstruction pass not after phi-node-elimination pass. So we
2068     // shouldn't use the NoSSA as the condition, we should based on
2069     // TiedOpsRewritten property to verify two-address constraints, this
2070     // property will be set in twoaddressinstruction pass.
2071     unsigned DefIdx;
2072     if (MF->getProperties().hasProperty(
2073             MachineFunctionProperties::Property::TiedOpsRewritten) &&
2074         MO->isUse() && MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
2075         Reg != MI->getOperand(DefIdx).getReg())
2076       report("Two-address instruction operands must be identical", MO, MONum);
2077 
2078     // Check register classes.
2079     unsigned SubIdx = MO->getSubReg();
2080 
2081     if (Register::isPhysicalRegister(Reg)) {
2082       if (SubIdx) {
2083         report("Illegal subregister index for physical register", MO, MONum);
2084         return;
2085       }
2086       if (MONum < MCID.getNumOperands()) {
2087         if (const TargetRegisterClass *DRC =
2088               TII->getRegClass(MCID, MONum, TRI, *MF)) {
2089           if (!DRC->contains(Reg)) {
2090             report("Illegal physical register for instruction", MO, MONum);
2091             errs() << printReg(Reg, TRI) << " is not a "
2092                    << TRI->getRegClassName(DRC) << " register.\n";
2093           }
2094         }
2095       }
2096       if (MO->isRenamable()) {
2097         if (MRI->isReserved(Reg)) {
2098           report("isRenamable set on reserved register", MO, MONum);
2099           return;
2100         }
2101       }
2102     } else {
2103       // Virtual register.
2104       const TargetRegisterClass *RC = MRI->getRegClassOrNull(Reg);
2105       if (!RC) {
2106         // This is a generic virtual register.
2107 
2108         // Do not allow undef uses for generic virtual registers. This ensures
2109         // getVRegDef can never fail and return null on a generic register.
2110         //
2111         // FIXME: This restriction should probably be broadened to all SSA
2112         // MIR. However, DetectDeadLanes/ProcessImplicitDefs technically still
2113         // run on the SSA function just before phi elimination.
2114         if (MO->isUndef())
2115           report("Generic virtual register use cannot be undef", MO, MONum);
2116 
2117         // Debug value instruction is permitted to use undefined vregs.
2118         // This is a performance measure to skip the overhead of immediately
2119         // pruning unused debug operands. The final undef substitution occurs
2120         // when debug values are allocated in LDVImpl::handleDebugValue, so
2121         // these verifications always apply after this pass.
2122         if (isFunctionTracksDebugUserValues || !MO->isUse() ||
2123             !MI->isDebugValue() || !MRI->def_empty(Reg)) {
2124           // If we're post-Select, we can't have gvregs anymore.
2125           if (isFunctionSelected) {
2126             report("Generic virtual register invalid in a Selected function",
2127                    MO, MONum);
2128             return;
2129           }
2130 
2131           // The gvreg must have a type and it must not have a SubIdx.
2132           LLT Ty = MRI->getType(Reg);
2133           if (!Ty.isValid()) {
2134             report("Generic virtual register must have a valid type", MO,
2135                    MONum);
2136             return;
2137           }
2138 
2139           const RegisterBank *RegBank = MRI->getRegBankOrNull(Reg);
2140 
2141           // If we're post-RegBankSelect, the gvreg must have a bank.
2142           if (!RegBank && isFunctionRegBankSelected) {
2143             report("Generic virtual register must have a bank in a "
2144                    "RegBankSelected function",
2145                    MO, MONum);
2146             return;
2147           }
2148 
2149           // Make sure the register fits into its register bank if any.
2150           if (RegBank && Ty.isValid() &&
2151               RegBank->getSize() < Ty.getSizeInBits()) {
2152             report("Register bank is too small for virtual register", MO,
2153                    MONum);
2154             errs() << "Register bank " << RegBank->getName() << " too small("
2155                    << RegBank->getSize() << ") to fit " << Ty.getSizeInBits()
2156                    << "-bits\n";
2157             return;
2158           }
2159         }
2160 
2161         if (SubIdx)  {
2162           report("Generic virtual register does not allow subregister index", MO,
2163                  MONum);
2164           return;
2165         }
2166 
2167         // If this is a target specific instruction and this operand
2168         // has register class constraint, the virtual register must
2169         // comply to it.
2170         if (!isPreISelGenericOpcode(MCID.getOpcode()) &&
2171             MONum < MCID.getNumOperands() &&
2172             TII->getRegClass(MCID, MONum, TRI, *MF)) {
2173           report("Virtual register does not match instruction constraint", MO,
2174                  MONum);
2175           errs() << "Expect register class "
2176                  << TRI->getRegClassName(
2177                         TII->getRegClass(MCID, MONum, TRI, *MF))
2178                  << " but got nothing\n";
2179           return;
2180         }
2181 
2182         break;
2183       }
2184       if (SubIdx) {
2185         const TargetRegisterClass *SRC =
2186           TRI->getSubClassWithSubReg(RC, SubIdx);
2187         if (!SRC) {
2188           report("Invalid subregister index for virtual register", MO, MONum);
2189           errs() << "Register class " << TRI->getRegClassName(RC)
2190               << " does not support subreg index " << SubIdx << "\n";
2191           return;
2192         }
2193         if (RC != SRC) {
2194           report("Invalid register class for subregister index", MO, MONum);
2195           errs() << "Register class " << TRI->getRegClassName(RC)
2196               << " does not fully support subreg index " << SubIdx << "\n";
2197           return;
2198         }
2199       }
2200       if (MONum < MCID.getNumOperands()) {
2201         if (const TargetRegisterClass *DRC =
2202               TII->getRegClass(MCID, MONum, TRI, *MF)) {
2203           if (SubIdx) {
2204             const TargetRegisterClass *SuperRC =
2205                 TRI->getLargestLegalSuperClass(RC, *MF);
2206             if (!SuperRC) {
2207               report("No largest legal super class exists.", MO, MONum);
2208               return;
2209             }
2210             DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
2211             if (!DRC) {
2212               report("No matching super-reg register class.", MO, MONum);
2213               return;
2214             }
2215           }
2216           if (!RC->hasSuperClassEq(DRC)) {
2217             report("Illegal virtual register for instruction", MO, MONum);
2218             errs() << "Expected a " << TRI->getRegClassName(DRC)
2219                 << " register, but got a " << TRI->getRegClassName(RC)
2220                 << " register\n";
2221           }
2222         }
2223       }
2224     }
2225     break;
2226   }
2227 
2228   case MachineOperand::MO_RegisterMask:
2229     regMasks.push_back(MO->getRegMask());
2230     break;
2231 
2232   case MachineOperand::MO_MachineBasicBlock:
2233     if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
2234       report("PHI operand is not in the CFG", MO, MONum);
2235     break;
2236 
2237   case MachineOperand::MO_FrameIndex:
2238     if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
2239         LiveInts && !LiveInts->isNotInMIMap(*MI)) {
2240       int FI = MO->getIndex();
2241       LiveInterval &LI = LiveStks->getInterval(FI);
2242       SlotIndex Idx = LiveInts->getInstructionIndex(*MI);
2243 
2244       bool stores = MI->mayStore();
2245       bool loads = MI->mayLoad();
2246       // For a memory-to-memory move, we need to check if the frame
2247       // index is used for storing or loading, by inspecting the
2248       // memory operands.
2249       if (stores && loads) {
2250         for (auto *MMO : MI->memoperands()) {
2251           const PseudoSourceValue *PSV = MMO->getPseudoValue();
2252           if (PSV == nullptr) continue;
2253           const FixedStackPseudoSourceValue *Value =
2254             dyn_cast<FixedStackPseudoSourceValue>(PSV);
2255           if (Value == nullptr) continue;
2256           if (Value->getFrameIndex() != FI) continue;
2257 
2258           if (MMO->isStore())
2259             loads = false;
2260           else
2261             stores = false;
2262           break;
2263         }
2264         if (loads == stores)
2265           report("Missing fixed stack memoperand.", MI);
2266       }
2267       if (loads && !LI.liveAt(Idx.getRegSlot(true))) {
2268         report("Instruction loads from dead spill slot", MO, MONum);
2269         errs() << "Live stack: " << LI << '\n';
2270       }
2271       if (stores && !LI.liveAt(Idx.getRegSlot())) {
2272         report("Instruction stores to dead spill slot", MO, MONum);
2273         errs() << "Live stack: " << LI << '\n';
2274       }
2275     }
2276     break;
2277 
2278   case MachineOperand::MO_CFIIndex:
2279     if (MO->getCFIIndex() >= MF->getFrameInstructions().size())
2280       report("CFI instruction has invalid index", MO, MONum);
2281     break;
2282 
2283   default:
2284     break;
2285   }
2286 }
2287 
2288 void MachineVerifier::checkLivenessAtUse(const MachineOperand *MO,
2289                                          unsigned MONum, SlotIndex UseIdx,
2290                                          const LiveRange &LR,
2291                                          Register VRegOrUnit,
2292                                          LaneBitmask LaneMask) {
2293   LiveQueryResult LRQ = LR.Query(UseIdx);
2294   // Check if we have a segment at the use, note however that we only need one
2295   // live subregister range, the others may be dead.
2296   if (!LRQ.valueIn() && LaneMask.none()) {
2297     report("No live segment at use", MO, MONum);
2298     report_context_liverange(LR);
2299     report_context_vreg_regunit(VRegOrUnit);
2300     report_context(UseIdx);
2301   }
2302   if (MO->isKill() && !LRQ.isKill()) {
2303     report("Live range continues after kill flag", MO, MONum);
2304     report_context_liverange(LR);
2305     report_context_vreg_regunit(VRegOrUnit);
2306     if (LaneMask.any())
2307       report_context_lanemask(LaneMask);
2308     report_context(UseIdx);
2309   }
2310 }
2311 
2312 void MachineVerifier::checkLivenessAtDef(const MachineOperand *MO,
2313                                          unsigned MONum, SlotIndex DefIdx,
2314                                          const LiveRange &LR,
2315                                          Register VRegOrUnit,
2316                                          bool SubRangeCheck,
2317                                          LaneBitmask LaneMask) {
2318   if (const VNInfo *VNI = LR.getVNInfoAt(DefIdx)) {
2319     // The LR can correspond to the whole reg and its def slot is not obliged
2320     // to be the same as the MO' def slot. E.g. when we check here "normal"
2321     // subreg MO but there is other EC subreg MO in the same instruction so the
2322     // whole reg has EC def slot and differs from the currently checked MO' def
2323     // slot. For example:
2324     // %0 [16e,32r:0) 0@16e  L..3 [16e,32r:0) 0@16e  L..C [16r,32r:0) 0@16r
2325     // Check that there is an early-clobber def of the same superregister
2326     // somewhere is performed in visitMachineFunctionAfter()
2327     if (((SubRangeCheck || MO->getSubReg() == 0) && VNI->def != DefIdx) ||
2328         !SlotIndex::isSameInstr(VNI->def, DefIdx) ||
2329         (VNI->def != DefIdx &&
2330          (!VNI->def.isEarlyClobber() || !DefIdx.isRegister()))) {
2331       report("Inconsistent valno->def", MO, MONum);
2332       report_context_liverange(LR);
2333       report_context_vreg_regunit(VRegOrUnit);
2334       if (LaneMask.any())
2335         report_context_lanemask(LaneMask);
2336       report_context(*VNI);
2337       report_context(DefIdx);
2338     }
2339   } else {
2340     report("No live segment at def", MO, MONum);
2341     report_context_liverange(LR);
2342     report_context_vreg_regunit(VRegOrUnit);
2343     if (LaneMask.any())
2344       report_context_lanemask(LaneMask);
2345     report_context(DefIdx);
2346   }
2347   // Check that, if the dead def flag is present, LiveInts agree.
2348   if (MO->isDead()) {
2349     LiveQueryResult LRQ = LR.Query(DefIdx);
2350     if (!LRQ.isDeadDef()) {
2351       assert(Register::isVirtualRegister(VRegOrUnit) &&
2352              "Expecting a virtual register.");
2353       // A dead subreg def only tells us that the specific subreg is dead. There
2354       // could be other non-dead defs of other subregs, or we could have other
2355       // parts of the register being live through the instruction. So unless we
2356       // are checking liveness for a subrange it is ok for the live range to
2357       // continue, given that we have a dead def of a subregister.
2358       if (SubRangeCheck || MO->getSubReg() == 0) {
2359         report("Live range continues after dead def flag", MO, MONum);
2360         report_context_liverange(LR);
2361         report_context_vreg_regunit(VRegOrUnit);
2362         if (LaneMask.any())
2363           report_context_lanemask(LaneMask);
2364       }
2365     }
2366   }
2367 }
2368 
2369 void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
2370   const MachineInstr *MI = MO->getParent();
2371   const Register Reg = MO->getReg();
2372   const unsigned SubRegIdx = MO->getSubReg();
2373 
2374   const LiveInterval *LI = nullptr;
2375   if (LiveInts && Reg.isVirtual()) {
2376     if (LiveInts->hasInterval(Reg)) {
2377       LI = &LiveInts->getInterval(Reg);
2378       if (SubRegIdx != 0 && (MO->isDef() || !MO->isUndef()) && !LI->empty() &&
2379           !LI->hasSubRanges() && MRI->shouldTrackSubRegLiveness(Reg))
2380         report("Live interval for subreg operand has no subranges", MO, MONum);
2381     } else {
2382       report("Virtual register has no live interval", MO, MONum);
2383     }
2384   }
2385 
2386   // Both use and def operands can read a register.
2387   if (MO->readsReg()) {
2388     if (MO->isKill())
2389       addRegWithSubRegs(regsKilled, Reg);
2390 
2391     // Check that LiveVars knows this kill (unless we are inside a bundle, in
2392     // which case we have already checked that LiveVars knows any kills on the
2393     // bundle header instead).
2394     if (LiveVars && Reg.isVirtual() && MO->isKill() &&
2395         !MI->isBundledWithPred()) {
2396       LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
2397       if (!is_contained(VI.Kills, MI))
2398         report("Kill missing from LiveVariables", MO, MONum);
2399     }
2400 
2401     // Check LiveInts liveness and kill.
2402     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
2403       SlotIndex UseIdx = LiveInts->getInstructionIndex(*MI);
2404       // Check the cached regunit intervals.
2405       if (Reg.isPhysical() && !isReserved(Reg)) {
2406         for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid();
2407              ++Units) {
2408           if (MRI->isReservedRegUnit(*Units))
2409             continue;
2410           if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units))
2411             checkLivenessAtUse(MO, MONum, UseIdx, *LR, *Units);
2412         }
2413       }
2414 
2415       if (Reg.isVirtual()) {
2416         // This is a virtual register interval.
2417         checkLivenessAtUse(MO, MONum, UseIdx, *LI, Reg);
2418 
2419         if (LI->hasSubRanges() && !MO->isDef()) {
2420           LaneBitmask MOMask = SubRegIdx != 0
2421                                    ? TRI->getSubRegIndexLaneMask(SubRegIdx)
2422                                    : MRI->getMaxLaneMaskForVReg(Reg);
2423           LaneBitmask LiveInMask;
2424           for (const LiveInterval::SubRange &SR : LI->subranges()) {
2425             if ((MOMask & SR.LaneMask).none())
2426               continue;
2427             checkLivenessAtUse(MO, MONum, UseIdx, SR, Reg, SR.LaneMask);
2428             LiveQueryResult LRQ = SR.Query(UseIdx);
2429             if (LRQ.valueIn())
2430               LiveInMask |= SR.LaneMask;
2431           }
2432           // At least parts of the register has to be live at the use.
2433           if ((LiveInMask & MOMask).none()) {
2434             report("No live subrange at use", MO, MONum);
2435             report_context(*LI);
2436             report_context(UseIdx);
2437           }
2438         }
2439       }
2440     }
2441 
2442     // Use of a dead register.
2443     if (!regsLive.count(Reg)) {
2444       if (Reg.isPhysical()) {
2445         // Reserved registers may be used even when 'dead'.
2446         bool Bad = !isReserved(Reg);
2447         // We are fine if just any subregister has a defined value.
2448         if (Bad) {
2449 
2450           for (const MCPhysReg &SubReg : TRI->subregs(Reg)) {
2451             if (regsLive.count(SubReg)) {
2452               Bad = false;
2453               break;
2454             }
2455           }
2456         }
2457         // If there is an additional implicit-use of a super register we stop
2458         // here. By definition we are fine if the super register is not
2459         // (completely) dead, if the complete super register is dead we will
2460         // get a report for its operand.
2461         if (Bad) {
2462           for (const MachineOperand &MOP : MI->uses()) {
2463             if (!MOP.isReg() || !MOP.isImplicit())
2464               continue;
2465 
2466             if (!MOP.getReg().isPhysical())
2467               continue;
2468 
2469             if (llvm::is_contained(TRI->subregs(MOP.getReg()), Reg))
2470               Bad = false;
2471           }
2472         }
2473         if (Bad)
2474           report("Using an undefined physical register", MO, MONum);
2475       } else if (MRI->def_empty(Reg)) {
2476         report("Reading virtual register without a def", MO, MONum);
2477       } else {
2478         BBInfo &MInfo = MBBInfoMap[MI->getParent()];
2479         // We don't know which virtual registers are live in, so only complain
2480         // if vreg was killed in this MBB. Otherwise keep track of vregs that
2481         // must be live in. PHI instructions are handled separately.
2482         if (MInfo.regsKilled.count(Reg))
2483           report("Using a killed virtual register", MO, MONum);
2484         else if (!MI->isPHI())
2485           MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
2486       }
2487     }
2488   }
2489 
2490   if (MO->isDef()) {
2491     // Register defined.
2492     // TODO: verify that earlyclobber ops are not used.
2493     if (MO->isDead())
2494       addRegWithSubRegs(regsDead, Reg);
2495     else
2496       addRegWithSubRegs(regsDefined, Reg);
2497 
2498     // Verify SSA form.
2499     if (MRI->isSSA() && Reg.isVirtual() &&
2500         std::next(MRI->def_begin(Reg)) != MRI->def_end())
2501       report("Multiple virtual register defs in SSA form", MO, MONum);
2502 
2503     // Check LiveInts for a live segment, but only for virtual registers.
2504     if (LiveInts && !LiveInts->isNotInMIMap(*MI)) {
2505       SlotIndex DefIdx = LiveInts->getInstructionIndex(*MI);
2506       DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
2507 
2508       if (Reg.isVirtual()) {
2509         checkLivenessAtDef(MO, MONum, DefIdx, *LI, Reg);
2510 
2511         if (LI->hasSubRanges()) {
2512           LaneBitmask MOMask = SubRegIdx != 0
2513                                    ? TRI->getSubRegIndexLaneMask(SubRegIdx)
2514                                    : MRI->getMaxLaneMaskForVReg(Reg);
2515           for (const LiveInterval::SubRange &SR : LI->subranges()) {
2516             if ((SR.LaneMask & MOMask).none())
2517               continue;
2518             checkLivenessAtDef(MO, MONum, DefIdx, SR, Reg, true, SR.LaneMask);
2519           }
2520         }
2521       }
2522     }
2523   }
2524 }
2525 
2526 // This function gets called after visiting all instructions in a bundle. The
2527 // argument points to the bundle header.
2528 // Normal stand-alone instructions are also considered 'bundles', and this
2529 // function is called for all of them.
2530 void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
2531   BBInfo &MInfo = MBBInfoMap[MI->getParent()];
2532   set_union(MInfo.regsKilled, regsKilled);
2533   set_subtract(regsLive, regsKilled); regsKilled.clear();
2534   // Kill any masked registers.
2535   while (!regMasks.empty()) {
2536     const uint32_t *Mask = regMasks.pop_back_val();
2537     for (Register Reg : regsLive)
2538       if (Reg.isPhysical() &&
2539           MachineOperand::clobbersPhysReg(Mask, Reg.asMCReg()))
2540         regsDead.push_back(Reg);
2541   }
2542   set_subtract(regsLive, regsDead);   regsDead.clear();
2543   set_union(regsLive, regsDefined);   regsDefined.clear();
2544 }
2545 
2546 void
2547 MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
2548   MBBInfoMap[MBB].regsLiveOut = regsLive;
2549   regsLive.clear();
2550 
2551   if (Indexes) {
2552     SlotIndex stop = Indexes->getMBBEndIdx(MBB);
2553     if (!(stop > lastIndex)) {
2554       report("Block ends before last instruction index", MBB);
2555       errs() << "Block ends at " << stop
2556           << " last instruction was at " << lastIndex << '\n';
2557     }
2558     lastIndex = stop;
2559   }
2560 }
2561 
2562 namespace {
2563 // This implements a set of registers that serves as a filter: can filter other
2564 // sets by passing through elements not in the filter and blocking those that
2565 // are. Any filter implicitly includes the full set of physical registers upon
2566 // creation, thus filtering them all out. The filter itself as a set only grows,
2567 // and needs to be as efficient as possible.
2568 struct VRegFilter {
2569   // Add elements to the filter itself. \pre Input set \p FromRegSet must have
2570   // no duplicates. Both virtual and physical registers are fine.
2571   template <typename RegSetT> void add(const RegSetT &FromRegSet) {
2572     SmallVector<Register, 0> VRegsBuffer;
2573     filterAndAdd(FromRegSet, VRegsBuffer);
2574   }
2575   // Filter \p FromRegSet through the filter and append passed elements into \p
2576   // ToVRegs. All elements appended are then added to the filter itself.
2577   // \returns true if anything changed.
2578   template <typename RegSetT>
2579   bool filterAndAdd(const RegSetT &FromRegSet,
2580                     SmallVectorImpl<Register> &ToVRegs) {
2581     unsigned SparseUniverse = Sparse.size();
2582     unsigned NewSparseUniverse = SparseUniverse;
2583     unsigned NewDenseSize = Dense.size();
2584     size_t Begin = ToVRegs.size();
2585     for (Register Reg : FromRegSet) {
2586       if (!Reg.isVirtual())
2587         continue;
2588       unsigned Index = Register::virtReg2Index(Reg);
2589       if (Index < SparseUniverseMax) {
2590         if (Index < SparseUniverse && Sparse.test(Index))
2591           continue;
2592         NewSparseUniverse = std::max(NewSparseUniverse, Index + 1);
2593       } else {
2594         if (Dense.count(Reg))
2595           continue;
2596         ++NewDenseSize;
2597       }
2598       ToVRegs.push_back(Reg);
2599     }
2600     size_t End = ToVRegs.size();
2601     if (Begin == End)
2602       return false;
2603     // Reserving space in sets once performs better than doing so continuously
2604     // and pays easily for double look-ups (even in Dense with SparseUniverseMax
2605     // tuned all the way down) and double iteration (the second one is over a
2606     // SmallVector, which is a lot cheaper compared to DenseSet or BitVector).
2607     Sparse.resize(NewSparseUniverse);
2608     Dense.reserve(NewDenseSize);
2609     for (unsigned I = Begin; I < End; ++I) {
2610       Register Reg = ToVRegs[I];
2611       unsigned Index = Register::virtReg2Index(Reg);
2612       if (Index < SparseUniverseMax)
2613         Sparse.set(Index);
2614       else
2615         Dense.insert(Reg);
2616     }
2617     return true;
2618   }
2619 
2620 private:
2621   static constexpr unsigned SparseUniverseMax = 10 * 1024 * 8;
2622   // VRegs indexed within SparseUniverseMax are tracked by Sparse, those beyound
2623   // are tracked by Dense. The only purpose of the threashold and the Dense set
2624   // is to have a reasonably growing memory usage in pathological cases (large
2625   // number of very sparse VRegFilter instances live at the same time). In
2626   // practice even in the worst-by-execution time cases having all elements
2627   // tracked by Sparse (very large SparseUniverseMax scenario) tends to be more
2628   // space efficient than if tracked by Dense. The threashold is set to keep the
2629   // worst-case memory usage within 2x of figures determined empirically for
2630   // "all Dense" scenario in such worst-by-execution-time cases.
2631   BitVector Sparse;
2632   DenseSet<unsigned> Dense;
2633 };
2634 
2635 // Implements both a transfer function and a (binary, in-place) join operator
2636 // for a dataflow over register sets with set union join and filtering transfer
2637 // (out_b = in_b \ filter_b). filter_b is expected to be set-up ahead of time.
2638 // Maintains out_b as its state, allowing for O(n) iteration over it at any
2639 // time, where n is the size of the set (as opposed to O(U) where U is the
2640 // universe). filter_b implicitly contains all physical registers at all times.
2641 class FilteringVRegSet {
2642   VRegFilter Filter;
2643   SmallVector<Register, 0> VRegs;
2644 
2645 public:
2646   // Set-up the filter_b. \pre Input register set \p RS must have no duplicates.
2647   // Both virtual and physical registers are fine.
2648   template <typename RegSetT> void addToFilter(const RegSetT &RS) {
2649     Filter.add(RS);
2650   }
2651   // Passes \p RS through the filter_b (transfer function) and adds what's left
2652   // to itself (out_b).
2653   template <typename RegSetT> bool add(const RegSetT &RS) {
2654     // Double-duty the Filter: to maintain VRegs a set (and the join operation
2655     // a set union) just add everything being added here to the Filter as well.
2656     return Filter.filterAndAdd(RS, VRegs);
2657   }
2658   using const_iterator = decltype(VRegs)::const_iterator;
2659   const_iterator begin() const { return VRegs.begin(); }
2660   const_iterator end() const { return VRegs.end(); }
2661   size_t size() const { return VRegs.size(); }
2662 };
2663 } // namespace
2664 
2665 // Calculate the largest possible vregsPassed sets. These are the registers that
2666 // can pass through an MBB live, but may not be live every time. It is assumed
2667 // that all vregsPassed sets are empty before the call.
2668 void MachineVerifier::calcRegsPassed() {
2669   if (MF->empty())
2670     // ReversePostOrderTraversal doesn't handle empty functions.
2671     return;
2672 
2673   for (const MachineBasicBlock *MB :
2674        ReversePostOrderTraversal<const MachineFunction *>(MF)) {
2675     FilteringVRegSet VRegs;
2676     BBInfo &Info = MBBInfoMap[MB];
2677     assert(Info.reachable);
2678 
2679     VRegs.addToFilter(Info.regsKilled);
2680     VRegs.addToFilter(Info.regsLiveOut);
2681     for (const MachineBasicBlock *Pred : MB->predecessors()) {
2682       const BBInfo &PredInfo = MBBInfoMap[Pred];
2683       if (!PredInfo.reachable)
2684         continue;
2685 
2686       VRegs.add(PredInfo.regsLiveOut);
2687       VRegs.add(PredInfo.vregsPassed);
2688     }
2689     Info.vregsPassed.reserve(VRegs.size());
2690     Info.vregsPassed.insert(VRegs.begin(), VRegs.end());
2691   }
2692 }
2693 
2694 // Calculate the set of virtual registers that must be passed through each basic
2695 // block in order to satisfy the requirements of successor blocks. This is very
2696 // similar to calcRegsPassed, only backwards.
2697 void MachineVerifier::calcRegsRequired() {
2698   // First push live-in regs to predecessors' vregsRequired.
2699   SmallPtrSet<const MachineBasicBlock*, 8> todo;
2700   for (const auto &MBB : *MF) {
2701     BBInfo &MInfo = MBBInfoMap[&MBB];
2702     for (const MachineBasicBlock *Pred : MBB.predecessors()) {
2703       BBInfo &PInfo = MBBInfoMap[Pred];
2704       if (PInfo.addRequired(MInfo.vregsLiveIn))
2705         todo.insert(Pred);
2706     }
2707 
2708     // Handle the PHI node.
2709     for (const MachineInstr &MI : MBB.phis()) {
2710       for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
2711         // Skip those Operands which are undef regs or not regs.
2712         if (!MI.getOperand(i).isReg() || !MI.getOperand(i).readsReg())
2713           continue;
2714 
2715         // Get register and predecessor for one PHI edge.
2716         Register Reg = MI.getOperand(i).getReg();
2717         const MachineBasicBlock *Pred = MI.getOperand(i + 1).getMBB();
2718 
2719         BBInfo &PInfo = MBBInfoMap[Pred];
2720         if (PInfo.addRequired(Reg))
2721           todo.insert(Pred);
2722       }
2723     }
2724   }
2725 
2726   // Iteratively push vregsRequired to predecessors. This will converge to the
2727   // same final state regardless of DenseSet iteration order.
2728   while (!todo.empty()) {
2729     const MachineBasicBlock *MBB = *todo.begin();
2730     todo.erase(MBB);
2731     BBInfo &MInfo = MBBInfoMap[MBB];
2732     for (const MachineBasicBlock *Pred : MBB->predecessors()) {
2733       if (Pred == MBB)
2734         continue;
2735       BBInfo &SInfo = MBBInfoMap[Pred];
2736       if (SInfo.addRequired(MInfo.vregsRequired))
2737         todo.insert(Pred);
2738     }
2739   }
2740 }
2741 
2742 // Check PHI instructions at the beginning of MBB. It is assumed that
2743 // calcRegsPassed has been run so BBInfo::isLiveOut is valid.
2744 void MachineVerifier::checkPHIOps(const MachineBasicBlock &MBB) {
2745   BBInfo &MInfo = MBBInfoMap[&MBB];
2746 
2747   SmallPtrSet<const MachineBasicBlock*, 8> seen;
2748   for (const MachineInstr &Phi : MBB) {
2749     if (!Phi.isPHI())
2750       break;
2751     seen.clear();
2752 
2753     const MachineOperand &MODef = Phi.getOperand(0);
2754     if (!MODef.isReg() || !MODef.isDef()) {
2755       report("Expected first PHI operand to be a register def", &MODef, 0);
2756       continue;
2757     }
2758     if (MODef.isTied() || MODef.isImplicit() || MODef.isInternalRead() ||
2759         MODef.isEarlyClobber() || MODef.isDebug())
2760       report("Unexpected flag on PHI operand", &MODef, 0);
2761     Register DefReg = MODef.getReg();
2762     if (!Register::isVirtualRegister(DefReg))
2763       report("Expected first PHI operand to be a virtual register", &MODef, 0);
2764 
2765     for (unsigned I = 1, E = Phi.getNumOperands(); I != E; I += 2) {
2766       const MachineOperand &MO0 = Phi.getOperand(I);
2767       if (!MO0.isReg()) {
2768         report("Expected PHI operand to be a register", &MO0, I);
2769         continue;
2770       }
2771       if (MO0.isImplicit() || MO0.isInternalRead() || MO0.isEarlyClobber() ||
2772           MO0.isDebug() || MO0.isTied())
2773         report("Unexpected flag on PHI operand", &MO0, I);
2774 
2775       const MachineOperand &MO1 = Phi.getOperand(I + 1);
2776       if (!MO1.isMBB()) {
2777         report("Expected PHI operand to be a basic block", &MO1, I + 1);
2778         continue;
2779       }
2780 
2781       const MachineBasicBlock &Pre = *MO1.getMBB();
2782       if (!Pre.isSuccessor(&MBB)) {
2783         report("PHI input is not a predecessor block", &MO1, I + 1);
2784         continue;
2785       }
2786 
2787       if (MInfo.reachable) {
2788         seen.insert(&Pre);
2789         BBInfo &PrInfo = MBBInfoMap[&Pre];
2790         if (!MO0.isUndef() && PrInfo.reachable &&
2791             !PrInfo.isLiveOut(MO0.getReg()))
2792           report("PHI operand is not live-out from predecessor", &MO0, I);
2793       }
2794     }
2795 
2796     // Did we see all predecessors?
2797     if (MInfo.reachable) {
2798       for (MachineBasicBlock *Pred : MBB.predecessors()) {
2799         if (!seen.count(Pred)) {
2800           report("Missing PHI operand", &Phi);
2801           errs() << printMBBReference(*Pred)
2802                  << " is a predecessor according to the CFG.\n";
2803         }
2804       }
2805     }
2806   }
2807 }
2808 
2809 void MachineVerifier::visitMachineFunctionAfter() {
2810   calcRegsPassed();
2811 
2812   for (const MachineBasicBlock &MBB : *MF)
2813     checkPHIOps(MBB);
2814 
2815   // Now check liveness info if available
2816   calcRegsRequired();
2817 
2818   // Check for killed virtual registers that should be live out.
2819   for (const auto &MBB : *MF) {
2820     BBInfo &MInfo = MBBInfoMap[&MBB];
2821     for (Register VReg : MInfo.vregsRequired)
2822       if (MInfo.regsKilled.count(VReg)) {
2823         report("Virtual register killed in block, but needed live out.", &MBB);
2824         errs() << "Virtual register " << printReg(VReg)
2825                << " is used after the block.\n";
2826       }
2827   }
2828 
2829   if (!MF->empty()) {
2830     BBInfo &MInfo = MBBInfoMap[&MF->front()];
2831     for (Register VReg : MInfo.vregsRequired) {
2832       report("Virtual register defs don't dominate all uses.", MF);
2833       report_context_vreg(VReg);
2834     }
2835   }
2836 
2837   if (LiveVars)
2838     verifyLiveVariables();
2839   if (LiveInts)
2840     verifyLiveIntervals();
2841 
2842   // Check live-in list of each MBB. If a register is live into MBB, check
2843   // that the register is in regsLiveOut of each predecessor block. Since
2844   // this must come from a definition in the predecesssor or its live-in
2845   // list, this will catch a live-through case where the predecessor does not
2846   // have the register in its live-in list.  This currently only checks
2847   // registers that have no aliases, are not allocatable and are not
2848   // reserved, which could mean a condition code register for instance.
2849   if (MRI->tracksLiveness())
2850     for (const auto &MBB : *MF)
2851       for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins()) {
2852         MCPhysReg LiveInReg = P.PhysReg;
2853         bool hasAliases = MCRegAliasIterator(LiveInReg, TRI, false).isValid();
2854         if (hasAliases || isAllocatable(LiveInReg) || isReserved(LiveInReg))
2855           continue;
2856         for (const MachineBasicBlock *Pred : MBB.predecessors()) {
2857           BBInfo &PInfo = MBBInfoMap[Pred];
2858           if (!PInfo.regsLiveOut.count(LiveInReg)) {
2859             report("Live in register not found to be live out from predecessor.",
2860                    &MBB);
2861             errs() << TRI->getName(LiveInReg)
2862                    << " not found to be live out from "
2863                    << printMBBReference(*Pred) << "\n";
2864           }
2865         }
2866       }
2867 
2868   for (auto CSInfo : MF->getCallSitesInfo())
2869     if (!CSInfo.first->isCall())
2870       report("Call site info referencing instruction that is not call", MF);
2871 
2872   // If there's debug-info, check that we don't have any duplicate value
2873   // tracking numbers.
2874   if (MF->getFunction().getSubprogram()) {
2875     DenseSet<unsigned> SeenNumbers;
2876     for (const auto &MBB : *MF) {
2877       for (const auto &MI : MBB) {
2878         if (auto Num = MI.peekDebugInstrNum()) {
2879           auto Result = SeenNumbers.insert((unsigned)Num);
2880           if (!Result.second)
2881             report("Instruction has a duplicated value tracking number", &MI);
2882         }
2883       }
2884     }
2885   }
2886 }
2887 
2888 void MachineVerifier::verifyLiveVariables() {
2889   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
2890   for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) {
2891     Register Reg = Register::index2VirtReg(I);
2892     LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
2893     for (const auto &MBB : *MF) {
2894       BBInfo &MInfo = MBBInfoMap[&MBB];
2895 
2896       // Our vregsRequired should be identical to LiveVariables' AliveBlocks
2897       if (MInfo.vregsRequired.count(Reg)) {
2898         if (!VI.AliveBlocks.test(MBB.getNumber())) {
2899           report("LiveVariables: Block missing from AliveBlocks", &MBB);
2900           errs() << "Virtual register " << printReg(Reg)
2901                  << " must be live through the block.\n";
2902         }
2903       } else {
2904         if (VI.AliveBlocks.test(MBB.getNumber())) {
2905           report("LiveVariables: Block should not be in AliveBlocks", &MBB);
2906           errs() << "Virtual register " << printReg(Reg)
2907                  << " is not needed live through the block.\n";
2908         }
2909       }
2910     }
2911   }
2912 }
2913 
2914 void MachineVerifier::verifyLiveIntervals() {
2915   assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
2916   for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) {
2917     Register Reg = Register::index2VirtReg(I);
2918 
2919     // Spilling and splitting may leave unused registers around. Skip them.
2920     if (MRI->reg_nodbg_empty(Reg))
2921       continue;
2922 
2923     if (!LiveInts->hasInterval(Reg)) {
2924       report("Missing live interval for virtual register", MF);
2925       errs() << printReg(Reg, TRI) << " still has defs or uses\n";
2926       continue;
2927     }
2928 
2929     const LiveInterval &LI = LiveInts->getInterval(Reg);
2930     assert(Reg == LI.reg() && "Invalid reg to interval mapping");
2931     verifyLiveInterval(LI);
2932   }
2933 
2934   // Verify all the cached regunit intervals.
2935   for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
2936     if (const LiveRange *LR = LiveInts->getCachedRegUnit(i))
2937       verifyLiveRange(*LR, i);
2938 }
2939 
2940 void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR,
2941                                            const VNInfo *VNI, Register Reg,
2942                                            LaneBitmask LaneMask) {
2943   if (VNI->isUnused())
2944     return;
2945 
2946   const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def);
2947 
2948   if (!DefVNI) {
2949     report("Value not live at VNInfo def and not marked unused", MF);
2950     report_context(LR, Reg, LaneMask);
2951     report_context(*VNI);
2952     return;
2953   }
2954 
2955   if (DefVNI != VNI) {
2956     report("Live segment at def has different VNInfo", MF);
2957     report_context(LR, Reg, LaneMask);
2958     report_context(*VNI);
2959     return;
2960   }
2961 
2962   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
2963   if (!MBB) {
2964     report("Invalid VNInfo definition index", MF);
2965     report_context(LR, Reg, LaneMask);
2966     report_context(*VNI);
2967     return;
2968   }
2969 
2970   if (VNI->isPHIDef()) {
2971     if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
2972       report("PHIDef VNInfo is not defined at MBB start", MBB);
2973       report_context(LR, Reg, LaneMask);
2974       report_context(*VNI);
2975     }
2976     return;
2977   }
2978 
2979   // Non-PHI def.
2980   const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
2981   if (!MI) {
2982     report("No instruction at VNInfo def index", MBB);
2983     report_context(LR, Reg, LaneMask);
2984     report_context(*VNI);
2985     return;
2986   }
2987 
2988   if (Reg != 0) {
2989     bool hasDef = false;
2990     bool isEarlyClobber = false;
2991     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
2992       if (!MOI->isReg() || !MOI->isDef())
2993         continue;
2994       if (Register::isVirtualRegister(Reg)) {
2995         if (MOI->getReg() != Reg)
2996           continue;
2997       } else {
2998         if (!Register::isPhysicalRegister(MOI->getReg()) ||
2999             !TRI->hasRegUnit(MOI->getReg(), Reg))
3000           continue;
3001       }
3002       if (LaneMask.any() &&
3003           (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
3004         continue;
3005       hasDef = true;
3006       if (MOI->isEarlyClobber())
3007         isEarlyClobber = true;
3008     }
3009 
3010     if (!hasDef) {
3011       report("Defining instruction does not modify register", MI);
3012       report_context(LR, Reg, LaneMask);
3013       report_context(*VNI);
3014     }
3015 
3016     // Early clobber defs begin at USE slots, but other defs must begin at
3017     // DEF slots.
3018     if (isEarlyClobber) {
3019       if (!VNI->def.isEarlyClobber()) {
3020         report("Early clobber def must be at an early-clobber slot", MBB);
3021         report_context(LR, Reg, LaneMask);
3022         report_context(*VNI);
3023       }
3024     } else if (!VNI->def.isRegister()) {
3025       report("Non-PHI, non-early clobber def must be at a register slot", MBB);
3026       report_context(LR, Reg, LaneMask);
3027       report_context(*VNI);
3028     }
3029   }
3030 }
3031 
3032 void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
3033                                              const LiveRange::const_iterator I,
3034                                              Register Reg,
3035                                              LaneBitmask LaneMask) {
3036   const LiveRange::Segment &S = *I;
3037   const VNInfo *VNI = S.valno;
3038   assert(VNI && "Live segment has no valno");
3039 
3040   if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) {
3041     report("Foreign valno in live segment", MF);
3042     report_context(LR, Reg, LaneMask);
3043     report_context(S);
3044     report_context(*VNI);
3045   }
3046 
3047   if (VNI->isUnused()) {
3048     report("Live segment valno is marked unused", MF);
3049     report_context(LR, Reg, LaneMask);
3050     report_context(S);
3051   }
3052 
3053   const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start);
3054   if (!MBB) {
3055     report("Bad start of live segment, no basic block", MF);
3056     report_context(LR, Reg, LaneMask);
3057     report_context(S);
3058     return;
3059   }
3060   SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
3061   if (S.start != MBBStartIdx && S.start != VNI->def) {
3062     report("Live segment must begin at MBB entry or valno def", MBB);
3063     report_context(LR, Reg, LaneMask);
3064     report_context(S);
3065   }
3066 
3067   const MachineBasicBlock *EndMBB =
3068     LiveInts->getMBBFromIndex(S.end.getPrevSlot());
3069   if (!EndMBB) {
3070     report("Bad end of live segment, no basic block", MF);
3071     report_context(LR, Reg, LaneMask);
3072     report_context(S);
3073     return;
3074   }
3075 
3076   // No more checks for live-out segments.
3077   if (S.end == LiveInts->getMBBEndIdx(EndMBB))
3078     return;
3079 
3080   // RegUnit intervals are allowed dead phis.
3081   if (!Register::isVirtualRegister(Reg) && VNI->isPHIDef() &&
3082       S.start == VNI->def && S.end == VNI->def.getDeadSlot())
3083     return;
3084 
3085   // The live segment is ending inside EndMBB
3086   const MachineInstr *MI =
3087     LiveInts->getInstructionFromIndex(S.end.getPrevSlot());
3088   if (!MI) {
3089     report("Live segment doesn't end at a valid instruction", EndMBB);
3090     report_context(LR, Reg, LaneMask);
3091     report_context(S);
3092     return;
3093   }
3094 
3095   // The block slot must refer to a basic block boundary.
3096   if (S.end.isBlock()) {
3097     report("Live segment ends at B slot of an instruction", EndMBB);
3098     report_context(LR, Reg, LaneMask);
3099     report_context(S);
3100   }
3101 
3102   if (S.end.isDead()) {
3103     // Segment ends on the dead slot.
3104     // That means there must be a dead def.
3105     if (!SlotIndex::isSameInstr(S.start, S.end)) {
3106       report("Live segment ending at dead slot spans instructions", EndMBB);
3107       report_context(LR, Reg, LaneMask);
3108       report_context(S);
3109     }
3110   }
3111 
3112   // After tied operands are rewritten, a live segment can only end at an
3113   // early-clobber slot if it is being redefined by an early-clobber def.
3114   // TODO: Before tied operands are rewritten, a live segment can only end at an
3115   // early-clobber slot if the last use is tied to an early-clobber def.
3116   if (MF->getProperties().hasProperty(
3117           MachineFunctionProperties::Property::TiedOpsRewritten) &&
3118       S.end.isEarlyClobber()) {
3119     if (I+1 == LR.end() || (I+1)->start != S.end) {
3120       report("Live segment ending at early clobber slot must be "
3121              "redefined by an EC def in the same instruction", EndMBB);
3122       report_context(LR, Reg, LaneMask);
3123       report_context(S);
3124     }
3125   }
3126 
3127   // The following checks only apply to virtual registers. Physreg liveness
3128   // is too weird to check.
3129   if (Register::isVirtualRegister(Reg)) {
3130     // A live segment can end with either a redefinition, a kill flag on a
3131     // use, or a dead flag on a def.
3132     bool hasRead = false;
3133     bool hasSubRegDef = false;
3134     bool hasDeadDef = false;
3135     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
3136       if (!MOI->isReg() || MOI->getReg() != Reg)
3137         continue;
3138       unsigned Sub = MOI->getSubReg();
3139       LaneBitmask SLM = Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
3140                                  : LaneBitmask::getAll();
3141       if (MOI->isDef()) {
3142         if (Sub != 0) {
3143           hasSubRegDef = true;
3144           // An operand %0:sub0 reads %0:sub1..n. Invert the lane
3145           // mask for subregister defs. Read-undef defs will be handled by
3146           // readsReg below.
3147           SLM = ~SLM;
3148         }
3149         if (MOI->isDead())
3150           hasDeadDef = true;
3151       }
3152       if (LaneMask.any() && (LaneMask & SLM).none())
3153         continue;
3154       if (MOI->readsReg())
3155         hasRead = true;
3156     }
3157     if (S.end.isDead()) {
3158       // Make sure that the corresponding machine operand for a "dead" live
3159       // range has the dead flag. We cannot perform this check for subregister
3160       // liveranges as partially dead values are allowed.
3161       if (LaneMask.none() && !hasDeadDef) {
3162         report("Instruction ending live segment on dead slot has no dead flag",
3163                MI);
3164         report_context(LR, Reg, LaneMask);
3165         report_context(S);
3166       }
3167     } else {
3168       if (!hasRead) {
3169         // When tracking subregister liveness, the main range must start new
3170         // values on partial register writes, even if there is no read.
3171         if (!MRI->shouldTrackSubRegLiveness(Reg) || LaneMask.any() ||
3172             !hasSubRegDef) {
3173           report("Instruction ending live segment doesn't read the register",
3174                  MI);
3175           report_context(LR, Reg, LaneMask);
3176           report_context(S);
3177         }
3178       }
3179     }
3180   }
3181 
3182   // Now check all the basic blocks in this live segment.
3183   MachineFunction::const_iterator MFI = MBB->getIterator();
3184   // Is this live segment the beginning of a non-PHIDef VN?
3185   if (S.start == VNI->def && !VNI->isPHIDef()) {
3186     // Not live-in to any blocks.
3187     if (MBB == EndMBB)
3188       return;
3189     // Skip this block.
3190     ++MFI;
3191   }
3192 
3193   SmallVector<SlotIndex, 4> Undefs;
3194   if (LaneMask.any()) {
3195     LiveInterval &OwnerLI = LiveInts->getInterval(Reg);
3196     OwnerLI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
3197   }
3198 
3199   while (true) {
3200     assert(LiveInts->isLiveInToMBB(LR, &*MFI));
3201     // We don't know how to track physregs into a landing pad.
3202     if (!Register::isVirtualRegister(Reg) && MFI->isEHPad()) {
3203       if (&*MFI == EndMBB)
3204         break;
3205       ++MFI;
3206       continue;
3207     }
3208 
3209     // Is VNI a PHI-def in the current block?
3210     bool IsPHI = VNI->isPHIDef() &&
3211       VNI->def == LiveInts->getMBBStartIdx(&*MFI);
3212 
3213     // Check that VNI is live-out of all predecessors.
3214     for (const MachineBasicBlock *Pred : MFI->predecessors()) {
3215       SlotIndex PEnd = LiveInts->getMBBEndIdx(Pred);
3216       // Predecessor of landing pad live-out on last call.
3217       if (MFI->isEHPad()) {
3218         for (const MachineInstr &MI : llvm::reverse(*Pred)) {
3219           if (MI.isCall()) {
3220             PEnd = Indexes->getInstructionIndex(MI).getBoundaryIndex();
3221             break;
3222           }
3223         }
3224       }
3225       const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
3226 
3227       // All predecessors must have a live-out value. However for a phi
3228       // instruction with subregister intervals
3229       // only one of the subregisters (not necessarily the current one) needs to
3230       // be defined.
3231       if (!PVNI && (LaneMask.none() || !IsPHI)) {
3232         if (LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes))
3233           continue;
3234         report("Register not marked live out of predecessor", Pred);
3235         report_context(LR, Reg, LaneMask);
3236         report_context(*VNI);
3237         errs() << " live into " << printMBBReference(*MFI) << '@'
3238                << LiveInts->getMBBStartIdx(&*MFI) << ", not live before "
3239                << PEnd << '\n';
3240         continue;
3241       }
3242 
3243       // Only PHI-defs can take different predecessor values.
3244       if (!IsPHI && PVNI != VNI) {
3245         report("Different value live out of predecessor", Pred);
3246         report_context(LR, Reg, LaneMask);
3247         errs() << "Valno #" << PVNI->id << " live out of "
3248                << printMBBReference(*Pred) << '@' << PEnd << "\nValno #"
3249                << VNI->id << " live into " << printMBBReference(*MFI) << '@'
3250                << LiveInts->getMBBStartIdx(&*MFI) << '\n';
3251       }
3252     }
3253     if (&*MFI == EndMBB)
3254       break;
3255     ++MFI;
3256   }
3257 }
3258 
3259 void MachineVerifier::verifyLiveRange(const LiveRange &LR, Register Reg,
3260                                       LaneBitmask LaneMask) {
3261   for (const VNInfo *VNI : LR.valnos)
3262     verifyLiveRangeValue(LR, VNI, Reg, LaneMask);
3263 
3264   for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I)
3265     verifyLiveRangeSegment(LR, I, Reg, LaneMask);
3266 }
3267 
3268 void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
3269   Register Reg = LI.reg();
3270   assert(Register::isVirtualRegister(Reg));
3271   verifyLiveRange(LI, Reg);
3272 
3273   LaneBitmask Mask;
3274   LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
3275   for (const LiveInterval::SubRange &SR : LI.subranges()) {
3276     if ((Mask & SR.LaneMask).any()) {
3277       report("Lane masks of sub ranges overlap in live interval", MF);
3278       report_context(LI);
3279     }
3280     if ((SR.LaneMask & ~MaxMask).any()) {
3281       report("Subrange lanemask is invalid", MF);
3282       report_context(LI);
3283     }
3284     if (SR.empty()) {
3285       report("Subrange must not be empty", MF);
3286       report_context(SR, LI.reg(), SR.LaneMask);
3287     }
3288     Mask |= SR.LaneMask;
3289     verifyLiveRange(SR, LI.reg(), SR.LaneMask);
3290     if (!LI.covers(SR)) {
3291       report("A Subrange is not covered by the main range", MF);
3292       report_context(LI);
3293     }
3294   }
3295 
3296   // Check the LI only has one connected component.
3297   ConnectedVNInfoEqClasses ConEQ(*LiveInts);
3298   unsigned NumComp = ConEQ.Classify(LI);
3299   if (NumComp > 1) {
3300     report("Multiple connected components in live interval", MF);
3301     report_context(LI);
3302     for (unsigned comp = 0; comp != NumComp; ++comp) {
3303       errs() << comp << ": valnos";
3304       for (const VNInfo *I : LI.valnos)
3305         if (comp == ConEQ.getEqClass(I))
3306           errs() << ' ' << I->id;
3307       errs() << '\n';
3308     }
3309   }
3310 }
3311 
3312 namespace {
3313 
3314   // FrameSetup and FrameDestroy can have zero adjustment, so using a single
3315   // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
3316   // value is zero.
3317   // We use a bool plus an integer to capture the stack state.
3318   struct StackStateOfBB {
3319     StackStateOfBB() = default;
3320     StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
3321       EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
3322       ExitIsSetup(ExitSetup) {}
3323 
3324     // Can be negative, which means we are setting up a frame.
3325     int EntryValue = 0;
3326     int ExitValue = 0;
3327     bool EntryIsSetup = false;
3328     bool ExitIsSetup = false;
3329   };
3330 
3331 } // end anonymous namespace
3332 
3333 /// Make sure on every path through the CFG, a FrameSetup <n> is always followed
3334 /// by a FrameDestroy <n>, stack adjustments are identical on all
3335 /// CFG edges to a merge point, and frame is destroyed at end of a return block.
3336 void MachineVerifier::verifyStackFrame() {
3337   unsigned FrameSetupOpcode   = TII->getCallFrameSetupOpcode();
3338   unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
3339   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
3340     return;
3341 
3342   SmallVector<StackStateOfBB, 8> SPState;
3343   SPState.resize(MF->getNumBlockIDs());
3344   df_iterator_default_set<const MachineBasicBlock*> Reachable;
3345 
3346   // Visit the MBBs in DFS order.
3347   for (df_ext_iterator<const MachineFunction *,
3348                        df_iterator_default_set<const MachineBasicBlock *>>
3349        DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
3350        DFI != DFE; ++DFI) {
3351     const MachineBasicBlock *MBB = *DFI;
3352 
3353     StackStateOfBB BBState;
3354     // Check the exit state of the DFS stack predecessor.
3355     if (DFI.getPathLength() >= 2) {
3356       const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
3357       assert(Reachable.count(StackPred) &&
3358              "DFS stack predecessor is already visited.\n");
3359       BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
3360       BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
3361       BBState.ExitValue = BBState.EntryValue;
3362       BBState.ExitIsSetup = BBState.EntryIsSetup;
3363     }
3364 
3365     // Update stack state by checking contents of MBB.
3366     for (const auto &I : *MBB) {
3367       if (I.getOpcode() == FrameSetupOpcode) {
3368         if (BBState.ExitIsSetup)
3369           report("FrameSetup is after another FrameSetup", &I);
3370         BBState.ExitValue -= TII->getFrameTotalSize(I);
3371         BBState.ExitIsSetup = true;
3372       }
3373 
3374       if (I.getOpcode() == FrameDestroyOpcode) {
3375         int Size = TII->getFrameTotalSize(I);
3376         if (!BBState.ExitIsSetup)
3377           report("FrameDestroy is not after a FrameSetup", &I);
3378         int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
3379                                                BBState.ExitValue;
3380         if (BBState.ExitIsSetup && AbsSPAdj != Size) {
3381           report("FrameDestroy <n> is after FrameSetup <m>", &I);
3382           errs() << "FrameDestroy <" << Size << "> is after FrameSetup <"
3383               << AbsSPAdj << ">.\n";
3384         }
3385         BBState.ExitValue += Size;
3386         BBState.ExitIsSetup = false;
3387       }
3388     }
3389     SPState[MBB->getNumber()] = BBState;
3390 
3391     // Make sure the exit state of any predecessor is consistent with the entry
3392     // state.
3393     for (const MachineBasicBlock *Pred : MBB->predecessors()) {
3394       if (Reachable.count(Pred) &&
3395           (SPState[Pred->getNumber()].ExitValue != BBState.EntryValue ||
3396            SPState[Pred->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
3397         report("The exit stack state of a predecessor is inconsistent.", MBB);
3398         errs() << "Predecessor " << printMBBReference(*Pred)
3399                << " has exit state (" << SPState[Pred->getNumber()].ExitValue
3400                << ", " << SPState[Pred->getNumber()].ExitIsSetup << "), while "
3401                << printMBBReference(*MBB) << " has entry state ("
3402                << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
3403       }
3404     }
3405 
3406     // Make sure the entry state of any successor is consistent with the exit
3407     // state.
3408     for (const MachineBasicBlock *Succ : MBB->successors()) {
3409       if (Reachable.count(Succ) &&
3410           (SPState[Succ->getNumber()].EntryValue != BBState.ExitValue ||
3411            SPState[Succ->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
3412         report("The entry stack state of a successor is inconsistent.", MBB);
3413         errs() << "Successor " << printMBBReference(*Succ)
3414                << " has entry state (" << SPState[Succ->getNumber()].EntryValue
3415                << ", " << SPState[Succ->getNumber()].EntryIsSetup << "), while "
3416                << printMBBReference(*MBB) << " has exit state ("
3417                << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
3418       }
3419     }
3420 
3421     // Make sure a basic block with return ends with zero stack adjustment.
3422     if (!MBB->empty() && MBB->back().isReturn()) {
3423       if (BBState.ExitIsSetup)
3424         report("A return block ends with a FrameSetup.", MBB);
3425       if (BBState.ExitValue)
3426         report("A return block ends with a nonzero stack adjustment.", MBB);
3427     }
3428   }
3429 }
3430