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