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