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  const bool isFunctionFailedISel = MF.getProperties().hasProperty(
364  isFunctionRegBankSelected =
365  !isFunctionFailedISel &&
368  isFunctionSelected = !isFunctionFailedISel &&
371  LiveVars = nullptr;
372  LiveInts = nullptr;
373  LiveStks = nullptr;
374  Indexes = nullptr;
375  if (PASS) {
376  LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
377  // We don't want to verify LiveVariables if LiveIntervals is available.
378  if (!LiveInts)
379  LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
380  LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
381  Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
382  }
383 
384  verifySlotIndexes();
385 
386  verifyProperties(MF);
387 
388  visitMachineFunctionBefore();
389  for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
390  MFI!=MFE; ++MFI) {
391  visitMachineBasicBlockBefore(&*MFI);
392  // Keep track of the current bundle header.
393  const MachineInstr *CurBundle = nullptr;
394  // Do we expect the next instruction to be part of the same bundle?
395  bool InBundle = false;
396 
397  for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
398  MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
399  if (MBBI->getParent() != &*MFI) {
400  report("Bad instruction parent pointer", &*MFI);
401  errs() << "Instruction: " << *MBBI;
402  continue;
403  }
404 
405  // Check for consistent bundle flags.
406  if (InBundle && !MBBI->isBundledWithPred())
407  report("Missing BundledPred flag, "
408  "BundledSucc was set on predecessor",
409  &*MBBI);
410  if (!InBundle && MBBI->isBundledWithPred())
411  report("BundledPred flag is set, "
412  "but BundledSucc not set on predecessor",
413  &*MBBI);
414 
415  // Is this a bundle header?
416  if (!MBBI->isInsideBundle()) {
417  if (CurBundle)
418  visitMachineBundleAfter(CurBundle);
419  CurBundle = &*MBBI;
420  visitMachineBundleBefore(CurBundle);
421  } else if (!CurBundle)
422  report("No bundle header", &*MBBI);
423  visitMachineInstrBefore(&*MBBI);
424  for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I) {
425  const MachineInstr &MI = *MBBI;
426  const MachineOperand &Op = MI.getOperand(I);
427  if (Op.getParent() != &MI) {
428  // Make sure to use correct addOperand / RemoveOperand / ChangeTo
429  // functions when replacing operands of a MachineInstr.
430  report("Instruction has operand with wrong parent set", &MI);
431  }
432 
433  visitMachineOperand(&Op, I);
434  }
435 
436  visitMachineInstrAfter(&*MBBI);
437 
438  // Was this the last bundled instruction?
439  InBundle = MBBI->isBundledWithSucc();
440  }
441  if (CurBundle)
442  visitMachineBundleAfter(CurBundle);
443  if (InBundle)
444  report("BundledSucc flag set on last instruction in block", &MFI->back());
445  visitMachineBasicBlockAfter(&*MFI);
446  }
447  visitMachineFunctionAfter();
448 
449  // Clean up.
450  regsLive.clear();
451  regsDefined.clear();
452  regsDead.clear();
453  regsKilled.clear();
454  regMasks.clear();
455  MBBInfoMap.clear();
456 
457  return foundErrors;
458 }
459 
460 void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
461  assert(MF);
462  errs() << '\n';
463  if (!foundErrors++) {
464  if (Banner)
465  errs() << "# " << Banner << '\n';
466  if (LiveInts != nullptr)
467  LiveInts->print(errs());
468  else
469  MF->print(errs(), Indexes);
470  }
471  errs() << "*** Bad machine code: " << msg << " ***\n"
472  << "- function: " << MF->getName() << "\n";
473 }
474 
475 void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
476  assert(MBB);
477  report(msg, MBB->getParent());
478  errs() << "- basic block: " << printMBBReference(*MBB) << ' '
479  << MBB->getName() << " (" << (const void *)MBB << ')';
480  if (Indexes)
481  errs() << " [" << Indexes->getMBBStartIdx(MBB)
482  << ';' << Indexes->getMBBEndIdx(MBB) << ')';
483  errs() << '\n';
484 }
485 
486 void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
487  assert(MI);
488  report(msg, MI->getParent());
489  errs() << "- instruction: ";
490  if (Indexes && Indexes->hasIndex(*MI))
491  errs() << Indexes->getInstructionIndex(*MI) << '\t';
492  MI->print(errs(), /*SkipOpers=*/true);
493  errs() << '\n';
494 }
495 
496 void MachineVerifier::report(const char *msg,
497  const MachineOperand *MO, unsigned MONum) {
498  assert(MO);
499  report(msg, MO->getParent());
500  errs() << "- operand " << MONum << ": ";
501  MO->print(errs(), TRI);
502  errs() << "\n";
503 }
504 
505 void MachineVerifier::report_context(SlotIndex Pos) const {
506  errs() << "- at: " << Pos << '\n';
507 }
508 
509 void MachineVerifier::report_context(const LiveInterval &LI) const {
510  errs() << "- interval: " << LI << '\n';
511 }
512 
513 void MachineVerifier::report_context(const LiveRange &LR, unsigned VRegUnit,
514  LaneBitmask LaneMask) const {
515  report_context_liverange(LR);
516  report_context_vreg_regunit(VRegUnit);
517  if (LaneMask.any())
518  report_context_lanemask(LaneMask);
519 }
520 
521 void MachineVerifier::report_context(const LiveRange::Segment &S) const {
522  errs() << "- segment: " << S << '\n';
523 }
524 
525 void MachineVerifier::report_context(const VNInfo &VNI) const {
526  errs() << "- ValNo: " << VNI.id << " (def " << VNI.def << ")\n";
527 }
528 
529 void MachineVerifier::report_context_liverange(const LiveRange &LR) const {
530  errs() << "- liverange: " << LR << '\n';
531 }
532 
533 void MachineVerifier::report_context_vreg(unsigned VReg) const {
534  errs() << "- v. register: " << printReg(VReg, TRI) << '\n';
535 }
536 
537 void MachineVerifier::report_context_vreg_regunit(unsigned VRegOrUnit) const {
538  if (TargetRegisterInfo::isVirtualRegister(VRegOrUnit)) {
539  report_context_vreg(VRegOrUnit);
540  } else {
541  errs() << "- regunit: " << printRegUnit(VRegOrUnit, TRI) << '\n';
542  }
543 }
544 
545 void MachineVerifier::report_context_lanemask(LaneBitmask LaneMask) const {
546  errs() << "- lanemask: " << PrintLaneMask(LaneMask) << '\n';
547 }
548 
549 void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
550  BBInfo &MInfo = MBBInfoMap[MBB];
551  if (!MInfo.reachable) {
552  MInfo.reachable = true;
554  SuE = MBB->succ_end(); SuI != SuE; ++SuI)
555  markReachable(*SuI);
556  }
557 }
558 
559 void MachineVerifier::visitMachineFunctionBefore() {
560  lastIndex = SlotIndex();
561  regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs()
562  : TRI->getReservedRegs(*MF);
563 
564  if (!MF->empty())
565  markReachable(&MF->front());
566 
567  // Build a set of the basic blocks in the function.
568  FunctionBlocks.clear();
569  for (const auto &MBB : *MF) {
570  FunctionBlocks.insert(&MBB);
571  BBInfo &MInfo = MBBInfoMap[&MBB];
572 
573  MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end());
574  if (MInfo.Preds.size() != MBB.pred_size())
575  report("MBB has duplicate entries in its predecessor list.", &MBB);
576 
577  MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end());
578  if (MInfo.Succs.size() != MBB.succ_size())
579  report("MBB has duplicate entries in its successor list.", &MBB);
580  }
581 
582  // Check that the register use lists are sane.
583  MRI->verifyUseLists();
584 
585  if (!MF->empty())
586  verifyStackFrame();
587 }
588 
589 // Does iterator point to a and b as the first two elements?
591  const MachineBasicBlock *a, const MachineBasicBlock *b) {
592  if (*i == a)
593  return *++i == b;
594  if (*i == b)
595  return *++i == a;
596  return false;
597 }
598 
599 void
600 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
601  FirstTerminator = nullptr;
602 
603  if (!MF->getProperties().hasProperty(
605  // If this block has allocatable physical registers live-in, check that
606  // it is an entry block or landing pad.
607  for (const auto &LI : MBB->liveins()) {
608  if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() &&
609  MBB->getIterator() != MBB->getParent()->begin()) {
610  report("MBB has allocatable live-in, but isn't entry or landing-pad.", MBB);
611  }
612  }
613  }
614 
615  // Count the number of landing pad successors.
616  SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
618  E = MBB->succ_end(); I != E; ++I) {
619  if ((*I)->isEHPad())
620  LandingPadSuccs.insert(*I);
621  if (!FunctionBlocks.count(*I))
622  report("MBB has successor that isn't part of the function.", MBB);
623  if (!MBBInfoMap[*I].Preds.count(MBB)) {
624  report("Inconsistent CFG", MBB);
625  errs() << "MBB is not in the predecessor list of the successor "
626  << printMBBReference(*(*I)) << ".\n";
627  }
628  }
629 
630  // Check the predecessor list.
632  E = MBB->pred_end(); I != E; ++I) {
633  if (!FunctionBlocks.count(*I))
634  report("MBB has predecessor that isn't part of the function.", MBB);
635  if (!MBBInfoMap[*I].Succs.count(MBB)) {
636  report("Inconsistent CFG", MBB);
637  errs() << "MBB is not in the successor list of the predecessor "
638  << printMBBReference(*(*I)) << ".\n";
639  }
640  }
641 
642  const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
643  const BasicBlock *BB = MBB->getBasicBlock();
644  const Function &F = MF->getFunction();
645  if (LandingPadSuccs.size() > 1 &&
646  !(AsmInfo &&
648  BB && isa<SwitchInst>(BB->getTerminator())) &&
650  report("MBB has more than one landing pad successor", MBB);
651 
652  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
653  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
655  if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB,
656  Cond)) {
657  // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
658  // check whether its answers match up with reality.
659  if (!TBB && !FBB) {
660  // Block falls through to its successor.
662  ++MBBI;
663  if (MBBI == MF->end()) {
664  // It's possible that the block legitimately ends with a noreturn
665  // call or an unreachable, in which case it won't actually fall
666  // out the bottom of the function.
667  } else if (MBB->succ_size() == LandingPadSuccs.size()) {
668  // It's possible that the block legitimately ends with a noreturn
669  // call or an unreachable, in which case it won't actuall fall
670  // out of the block.
671  } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
672  report("MBB exits via unconditional fall-through but doesn't have "
673  "exactly one CFG successor!", MBB);
674  } else if (!MBB->isSuccessor(&*MBBI)) {
675  report("MBB exits via unconditional fall-through but its successor "
676  "differs from its CFG successor!", MBB);
677  }
678  if (!MBB->empty() && MBB->back().isBarrier() &&
679  !TII->isPredicated(MBB->back())) {
680  report("MBB exits via unconditional fall-through but ends with a "
681  "barrier instruction!", MBB);
682  }
683  if (!Cond.empty()) {
684  report("MBB exits via unconditional fall-through but has a condition!",
685  MBB);
686  }
687  } else if (TBB && !FBB && Cond.empty()) {
688  // Block unconditionally branches somewhere.
689  // If the block has exactly one successor, that happens to be a
690  // landingpad, accept it as valid control flow.
691  if (MBB->succ_size() != 1+LandingPadSuccs.size() &&
692  (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 ||
693  *MBB->succ_begin() != *LandingPadSuccs.begin())) {
694  report("MBB exits via unconditional branch but doesn't have "
695  "exactly one CFG successor!", MBB);
696  } else if (!MBB->isSuccessor(TBB)) {
697  report("MBB exits via unconditional branch but the CFG "
698  "successor doesn't match the actual successor!", MBB);
699  }
700  if (MBB->empty()) {
701  report("MBB exits via unconditional branch but doesn't contain "
702  "any instructions!", MBB);
703  } else if (!MBB->back().isBarrier()) {
704  report("MBB exits via unconditional branch but doesn't end with a "
705  "barrier instruction!", MBB);
706  } else if (!MBB->back().isTerminator()) {
707  report("MBB exits via unconditional branch but the branch isn't a "
708  "terminator instruction!", MBB);
709  }
710  } else if (TBB && !FBB && !Cond.empty()) {
711  // Block conditionally branches somewhere, otherwise falls through.
713  ++MBBI;
714  if (MBBI == MF->end()) {
715  report("MBB conditionally falls through out of function!", MBB);
716  } else if (MBB->succ_size() == 1) {
717  // A conditional branch with only one successor is weird, but allowed.
718  if (&*MBBI != TBB)
719  report("MBB exits via conditional branch/fall-through but only has "
720  "one CFG successor!", MBB);
721  else if (TBB != *MBB->succ_begin())
722  report("MBB exits via conditional branch/fall-through but the CFG "
723  "successor don't match the actual successor!", MBB);
724  } else if (MBB->succ_size() != 2) {
725  report("MBB exits via conditional branch/fall-through but doesn't have "
726  "exactly two CFG successors!", MBB);
727  } else if (!matchPair(MBB->succ_begin(), TBB, &*MBBI)) {
728  report("MBB exits via conditional branch/fall-through but the CFG "
729  "successors don't match the actual successors!", MBB);
730  }
731  if (MBB->empty()) {
732  report("MBB exits via conditional branch/fall-through but doesn't "
733  "contain any instructions!", MBB);
734  } else if (MBB->back().isBarrier()) {
735  report("MBB exits via conditional branch/fall-through but ends with a "
736  "barrier instruction!", MBB);
737  } else if (!MBB->back().isTerminator()) {
738  report("MBB exits via conditional branch/fall-through but the branch "
739  "isn't a terminator instruction!", MBB);
740  }
741  } else if (TBB && FBB) {
742  // Block conditionally branches somewhere, otherwise branches
743  // somewhere else.
744  if (MBB->succ_size() == 1) {
745  // A conditional branch with only one successor is weird, but allowed.
746  if (FBB != TBB)
747  report("MBB exits via conditional branch/branch through but only has "
748  "one CFG successor!", MBB);
749  else if (TBB != *MBB->succ_begin())
750  report("MBB exits via conditional branch/branch through but the CFG "
751  "successor don't match the actual successor!", MBB);
752  } else if (MBB->succ_size() != 2) {
753  report("MBB exits via conditional branch/branch but doesn't have "
754  "exactly two CFG successors!", MBB);
755  } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
756  report("MBB exits via conditional branch/branch but the CFG "
757  "successors don't match the actual successors!", MBB);
758  }
759  if (MBB->empty()) {
760  report("MBB exits via conditional branch/branch but doesn't "
761  "contain any instructions!", MBB);
762  } else if (!MBB->back().isBarrier()) {
763  report("MBB exits via conditional branch/branch but doesn't end with a "
764  "barrier instruction!", MBB);
765  } else if (!MBB->back().isTerminator()) {
766  report("MBB exits via conditional branch/branch but the branch "
767  "isn't a terminator instruction!", MBB);
768  }
769  if (Cond.empty()) {
770  report("MBB exits via conditinal branch/branch but there's no "
771  "condition!", MBB);
772  }
773  } else {
774  report("AnalyzeBranch returned invalid data!", MBB);
775  }
776  }
777 
778  regsLive.clear();
779  if (MRI->tracksLiveness()) {
780  for (const auto &LI : MBB->liveins()) {
781  if (!TargetRegisterInfo::isPhysicalRegister(LI.PhysReg)) {
782  report("MBB live-in list contains non-physical register", MBB);
783  continue;
784  }
785  for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true);
786  SubRegs.isValid(); ++SubRegs)
787  regsLive.insert(*SubRegs);
788  }
789  }
790 
791  const MachineFrameInfo &MFI = MF->getFrameInfo();
792  BitVector PR = MFI.getPristineRegs(*MF);
793  for (unsigned I : PR.set_bits()) {
794  for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
795  SubRegs.isValid(); ++SubRegs)
796  regsLive.insert(*SubRegs);
797  }
798 
799  regsKilled.clear();
800  regsDefined.clear();
801 
802  if (Indexes)
803  lastIndex = Indexes->getMBBStartIdx(MBB);
804 }
805 
806 // This function gets called for all bundle headers, including normal
807 // stand-alone unbundled instructions.
808 void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
809  if (Indexes && Indexes->hasIndex(*MI)) {
810  SlotIndex idx = Indexes->getInstructionIndex(*MI);
811  if (!(idx > lastIndex)) {
812  report("Instruction index out of order", MI);
813  errs() << "Last instruction was at " << lastIndex << '\n';
814  }
815  lastIndex = idx;
816  }
817 
818  // Ensure non-terminators don't follow terminators.
819  // Ignore predicated terminators formed by if conversion.
820  // FIXME: If conversion shouldn't need to violate this rule.
821  if (MI->isTerminator() && !TII->isPredicated(*MI)) {
822  if (!FirstTerminator)
823  FirstTerminator = MI;
824  } else if (FirstTerminator) {
825  report("Non-terminator instruction after the first terminator", MI);
826  errs() << "First terminator was:\t" << *FirstTerminator;
827  }
828 }
829 
830 // The operands on an INLINEASM instruction must follow a template.
831 // Verify that the flag operands make sense.
832 void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
833  // The first two operands on INLINEASM are the asm string and global flags.
834  if (MI->getNumOperands() < 2) {
835  report("Too few operands on inline asm", MI);
836  return;
837  }
838  if (!MI->getOperand(0).isSymbol())
839  report("Asm string must be an external symbol", MI);
840  if (!MI->getOperand(1).isImm())
841  report("Asm flags must be an immediate", MI);
842  // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
843  // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16,
844  // and Extra_IsConvergent = 32.
845  if (!isUInt<6>(MI->getOperand(1).getImm()))
846  report("Unknown asm flags", &MI->getOperand(1), 1);
847 
848  static_assert(InlineAsm::MIOp_FirstOperand == 2, "Asm format changed");
849 
850  unsigned OpNo = InlineAsm::MIOp_FirstOperand;
851  unsigned NumOps;
852  for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
853  const MachineOperand &MO = MI->getOperand(OpNo);
854  // There may be implicit ops after the fixed operands.
855  if (!MO.isImm())
856  break;
857  NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
858  }
859 
860  if (OpNo > MI->getNumOperands())
861  report("Missing operands in last group", MI);
862 
863  // An optional MDNode follows the groups.
864  if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
865  ++OpNo;
866 
867  // All trailing operands must be implicit registers.
868  for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
869  const MachineOperand &MO = MI->getOperand(OpNo);
870  if (!MO.isReg() || !MO.isImplicit())
871  report("Expected implicit register after groups", &MO, OpNo);
872  }
873 }
874 
875 void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
876  const MCInstrDesc &MCID = MI->getDesc();
877  if (MI->getNumOperands() < MCID.getNumOperands()) {
878  report("Too few operands", MI);
879  errs() << MCID.getNumOperands() << " operands expected, but "
880  << MI->getNumOperands() << " given.\n";
881  }
882 
883  if (MI->isPHI() && MF->getProperties().hasProperty(
885  report("Found PHI instruction with NoPHIs property set", MI);
886 
887  // Check the tied operands.
888  if (MI->isInlineAsm())
889  verifyInlineAsm(MI);
890 
891  // Check the MachineMemOperands for basic consistency.
893  E = MI->memoperands_end(); I != E; ++I) {
894  if ((*I)->isLoad() && !MI->mayLoad())
895  report("Missing mayLoad flag", MI);
896  if ((*I)->isStore() && !MI->mayStore())
897  report("Missing mayStore flag", MI);
898  }
899 
900  // Debug values must not have a slot index.
901  // Other instructions must have one, unless they are inside a bundle.
902  if (LiveInts) {
903  bool mapped = !LiveInts->isNotInMIMap(*MI);
904  if (MI->isDebugValue()) {
905  if (mapped)
906  report("Debug instruction has a slot index", MI);
907  } else if (MI->isInsideBundle()) {
908  if (mapped)
909  report("Instruction inside bundle has a slot index", MI);
910  } else {
911  if (!mapped)
912  report("Missing slot index", MI);
913  }
914  }
915 
916  // Check types.
917  if (isPreISelGenericOpcode(MCID.getOpcode())) {
918  if (isFunctionSelected)
919  report("Unexpected generic instruction in a Selected function", MI);
920 
921  // Generic instructions specify equality constraints between some
922  // of their operands. Make sure these are consistent.
923  SmallVector<LLT, 4> Types;
924  for (unsigned i = 0; i < MCID.getNumOperands(); ++i) {
925  if (!MCID.OpInfo[i].isGenericType())
926  continue;
927  size_t TypeIdx = MCID.OpInfo[i].getGenericTypeIndex();
928  Types.resize(std::max(TypeIdx + 1, Types.size()));
929 
930  LLT OpTy = MRI->getType(MI->getOperand(i).getReg());
931  if (Types[TypeIdx].isValid() && Types[TypeIdx] != OpTy)
932  report("type mismatch in generic instruction", MI);
933  Types[TypeIdx] = OpTy;
934  }
935  }
936 
937  // Generic opcodes must not have physical register operands.
938  if (isPreISelGenericOpcode(MCID.getOpcode())) {
939  for (auto &Op : MI->operands()) {
940  if (Op.isReg() && TargetRegisterInfo::isPhysicalRegister(Op.getReg()))
941  report("Generic instruction cannot have physical register", MI);
942  }
943  }
944 
946  if (!TII->verifyInstruction(*MI, ErrorInfo))
947  report(ErrorInfo.data(), MI);
948 
949  // Verify properties of various specific instruction types
950  switch(MI->getOpcode()) {
951  default:
952  break;
953  case TargetOpcode::G_LOAD:
954  case TargetOpcode::G_STORE:
955  // Generic loads and stores must have a single MachineMemOperand
956  // describing that access.
957  if (!MI->hasOneMemOperand())
958  report("Generic instruction accessing memory must have one mem operand",
959  MI);
960  break;
961  case TargetOpcode::G_PHI: {
962  LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
963  if (!DstTy.isValid() ||
964  !std::all_of(MI->operands_begin() + 1, MI->operands_end(),
965  [this, &DstTy](const MachineOperand &MO) {
966  if (!MO.isReg())
967  return true;
968  LLT Ty = MRI->getType(MO.getReg());
969  if (!Ty.isValid() || (Ty != DstTy))
970  return false;
971  return true;
972  }))
973  report("Generic Instruction G_PHI has operands with incompatible/missing "
974  "types",
975  MI);
976  break;
977  }
978  case TargetOpcode::COPY: {
979  if (foundErrors)
980  break;
981  const MachineOperand &DstOp = MI->getOperand(0);
982  const MachineOperand &SrcOp = MI->getOperand(1);
983  LLT DstTy = MRI->getType(DstOp.getReg());
984  LLT SrcTy = MRI->getType(SrcOp.getReg());
985  if (SrcTy.isValid() && DstTy.isValid()) {
986  // If both types are valid, check that the types are the same.
987  if (SrcTy != DstTy) {
988  report("Copy Instruction is illegal with mismatching types", MI);
989  errs() << "Def = " << DstTy << ", Src = " << SrcTy << "\n";
990  }
991  }
992  if (SrcTy.isValid() || DstTy.isValid()) {
993  // If one of them have valid types, let's just check they have the same
994  // size.
995  unsigned SrcSize = TRI->getRegSizeInBits(SrcOp.getReg(), *MRI);
996  unsigned DstSize = TRI->getRegSizeInBits(DstOp.getReg(), *MRI);
997  assert(SrcSize && "Expecting size here");
998  assert(DstSize && "Expecting size here");
999  if (SrcSize != DstSize)
1000  if (!DstOp.getSubReg() && !SrcOp.getSubReg()) {
1001  report("Copy Instruction is illegal with mismatching sizes", MI);
1002  errs() << "Def Size = " << DstSize << ", Src Size = " << SrcSize
1003  << "\n";
1004  }
1005  }
1006  break;
1007  }
1008  case TargetOpcode::STATEPOINT:
1009  if (!MI->getOperand(StatepointOpers::IDPos).isImm() ||
1012  report("meta operands to STATEPOINT not constant!", MI);
1013  break;
1014 
1015  auto VerifyStackMapConstant = [&](unsigned Offset) {
1016  if (!MI->getOperand(Offset).isImm() ||
1017  MI->getOperand(Offset).getImm() != StackMaps::ConstantOp ||
1018  !MI->getOperand(Offset + 1).isImm())
1019  report("stack map constant to STATEPOINT not well formed!", MI);
1020  };
1021  const unsigned VarStart = StatepointOpers(MI).getVarIdx();
1022  VerifyStackMapConstant(VarStart + StatepointOpers::CCOffset);
1023  VerifyStackMapConstant(VarStart + StatepointOpers::FlagsOffset);
1024  VerifyStackMapConstant(VarStart + StatepointOpers::NumDeoptOperandsOffset);
1025 
1026  // TODO: verify we have properly encoded deopt arguments
1027  };
1028 }
1029 
1030 void
1031 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
1032  const MachineInstr *MI = MO->getParent();
1033  const MCInstrDesc &MCID = MI->getDesc();
1034  unsigned NumDefs = MCID.getNumDefs();
1035  if (MCID.getOpcode() == TargetOpcode::PATCHPOINT)
1036  NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0;
1037 
1038  // The first MCID.NumDefs operands must be explicit register defines
1039  if (MONum < NumDefs) {
1040  const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1041  if (!MO->isReg())
1042  report("Explicit definition must be a register", MO, MONum);
1043  else if (!MO->isDef() && !MCOI.isOptionalDef())
1044  report("Explicit definition marked as use", MO, MONum);
1045  else if (MO->isImplicit())
1046  report("Explicit definition marked as implicit", MO, MONum);
1047  } else if (MONum < MCID.getNumOperands()) {
1048  const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
1049  // Don't check if it's the last operand in a variadic instruction. See,
1050  // e.g., LDM_RET in the arm back end.
1051  if (MO->isReg() &&
1052  !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
1053  if (MO->isDef() && !MCOI.isOptionalDef())
1054  report("Explicit operand marked as def", MO, MONum);
1055  if (MO->isImplicit())
1056  report("Explicit operand marked as implicit", MO, MONum);
1057  }
1058 
1059  int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
1060  if (TiedTo != -1) {
1061  if (!MO->isReg())
1062  report("Tied use must be a register", MO, MONum);
1063  else if (!MO->isTied())
1064  report("Operand should be tied", MO, MONum);
1065  else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
1066  report("Tied def doesn't match MCInstrDesc", MO, MONum);
1068  const MachineOperand &MOTied = MI->getOperand(TiedTo);
1069  if (!MOTied.isReg())
1070  report("Tied counterpart must be a register", &MOTied, TiedTo);
1071  else if (TargetRegisterInfo::isPhysicalRegister(MOTied.getReg()) &&
1072  MO->getReg() != MOTied.getReg())
1073  report("Tied physical registers must match.", &MOTied, TiedTo);
1074  }
1075  } else if (MO->isReg() && MO->isTied())
1076  report("Explicit operand should not be tied", MO, MONum);
1077  } else {
1078  // ARM adds %reg0 operands to indicate predicates. We'll allow that.
1079  if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
1080  report("Extra explicit operand on non-variadic instruction", MO, MONum);
1081  }
1082 
1083  switch (MO->getType()) {
1085  const unsigned Reg = MO->getReg();
1086  if (!Reg)
1087  return;
1088  if (MRI->tracksLiveness() && !MI->isDebugValue())
1089  checkLiveness(MO, MONum);
1090 
1091  // Verify the consistency of tied operands.
1092  if (MO->isTied()) {
1093  unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
1094  const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
1095  if (!OtherMO.isReg())
1096  report("Must be tied to a register", MO, MONum);
1097  if (!OtherMO.isTied())
1098  report("Missing tie flags on tied operand", MO, MONum);
1099  if (MI->findTiedOperandIdx(OtherIdx) != MONum)
1100  report("Inconsistent tie links", MO, MONum);
1101  if (MONum < MCID.getNumDefs()) {
1102  if (OtherIdx < MCID.getNumOperands()) {
1103  if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
1104  report("Explicit def tied to explicit use without tie constraint",
1105  MO, MONum);
1106  } else {
1107  if (!OtherMO.isImplicit())
1108  report("Explicit def should be tied to implicit use", MO, MONum);
1109  }
1110  }
1111  }
1112 
1113  // Verify two-address constraints after leaving SSA form.
1114  unsigned DefIdx;
1115  if (!MRI->isSSA() && MO->isUse() &&
1116  MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
1117  Reg != MI->getOperand(DefIdx).getReg())
1118  report("Two-address instruction operands must be identical", MO, MONum);
1119 
1120  // Check register classes.
1121  unsigned SubIdx = MO->getSubReg();
1122 
1124  if (SubIdx) {
1125  report("Illegal subregister index for physical register", MO, MONum);
1126  return;
1127  }
1128  if (MONum < MCID.getNumOperands()) {
1129  if (const TargetRegisterClass *DRC =
1130  TII->getRegClass(MCID, MONum, TRI, *MF)) {
1131  if (!DRC->contains(Reg)) {
1132  report("Illegal physical register for instruction", MO, MONum);
1133  errs() << printReg(Reg, TRI) << " is not a "
1134  << TRI->getRegClassName(DRC) << " register.\n";
1135  }
1136  }
1137  }
1138  if (MO->isRenamable()) {
1139  if (MRI->isReserved(Reg)) {
1140  report("isRenamable set on reserved register", MO, MONum);
1141  return;
1142  }
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.
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:846
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
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
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
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()
void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
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
bool isRenamable() const
isRenamable - Returns true if this register may be renamed, i.e.
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
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:1273
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:559
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:138
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:905