blob: 37d476b2c091b4d4a3b4c69585e4a4cda7fd336a [file] [log] [blame]
Bill Wendling68caaaf2010-08-19 18:52:17 +00001//===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===//
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00002//
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
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000026#include "llvm/CodeGen/Passes.h"
Chris Lattner565449d2009-08-23 03:13:20 +000027#include "llvm/ADT/DenseSet.h"
Manman Renaa6875b2013-07-15 21:26:31 +000028#include "llvm/ADT/DepthFirstIterator.h"
Chris Lattner565449d2009-08-23 03:13:20 +000029#include "llvm/ADT/SetOperations.h"
30#include "llvm/ADT/SmallVector.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000031#include "llvm/CodeGen/LiveIntervalAnalysis.h"
32#include "llvm/CodeGen/LiveStackAnalysis.h"
33#include "llvm/CodeGen/LiveVariables.h"
34#include "llvm/CodeGen/MachineFrameInfo.h"
35#include "llvm/CodeGen/MachineFunctionPass.h"
36#include "llvm/CodeGen/MachineInstrBundle.h"
37#include "llvm/CodeGen/MachineMemOperand.h"
38#include "llvm/CodeGen/MachineRegisterInfo.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000039#include "llvm/IR/BasicBlock.h"
40#include "llvm/IR/InlineAsm.h"
41#include "llvm/IR/Instructions.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000042#include "llvm/MC/MCAsmInfo.h"
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000043#include "llvm/Support/Debug.h"
Torok Edwinccb29cd2009-07-11 13:10:19 +000044#include "llvm/Support/ErrorHandling.h"
Benjamin Kramerd59664f2014-04-29 23:26:49 +000045#include "llvm/Support/FileSystem.h"
Torok Edwinccb29cd2009-07-11 13:10:19 +000046#include "llvm/Support/raw_ostream.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000047#include "llvm/Target/TargetInstrInfo.h"
48#include "llvm/Target/TargetMachine.h"
49#include "llvm/Target/TargetRegisterInfo.h"
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000050using namespace llvm;
51
52namespace {
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +000053 struct MachineVerifier {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000054
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +000055 MachineVerifier(Pass *pass, const char *b) :
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +000056 PASS(pass),
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +000057 Banner(b),
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000058 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +000059 {}
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000060
61 bool runOnMachineFunction(MachineFunction &MF);
62
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +000063 Pass *const PASS;
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +000064 const char *Banner;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000065 const char *const OutFileName;
Chris Lattner9e6f1f12009-08-23 02:51:22 +000066 raw_ostream *OS;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000067 const MachineFunction *MF;
68 const TargetMachine *TM;
Evan Cheng8d71a752011-06-27 21:26:13 +000069 const TargetInstrInfo *TII;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000070 const TargetRegisterInfo *TRI;
71 const MachineRegisterInfo *MRI;
72
73 unsigned foundErrors;
74
75 typedef SmallVector<unsigned, 16> RegVector;
Jakob Stoklund Olesen16c4a972012-02-28 01:42:41 +000076 typedef SmallVector<const uint32_t*, 4> RegMaskVector;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000077 typedef DenseSet<unsigned> RegSet;
78 typedef DenseMap<unsigned, const MachineInstr*> RegMap;
Jakob Stoklund Olesende31b522012-08-20 20:52:06 +000079 typedef SmallPtrSet<const MachineBasicBlock*, 8> BlockSet;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000080
Jakob Stoklund Olesen3bb99bc2011-09-23 22:45:39 +000081 const MachineInstr *FirstTerminator;
Jakob Stoklund Olesende31b522012-08-20 20:52:06 +000082 BlockSet FunctionBlocks;
Jakob Stoklund Olesen3bb99bc2011-09-23 22:45:39 +000083
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000084 BitVector regsReserved;
85 RegSet regsLive;
Jakob Stoklund Olesen2d59cff2009-08-08 13:19:25 +000086 RegVector regsDefined, regsDead, regsKilled;
Jakob Stoklund Olesen16c4a972012-02-28 01:42:41 +000087 RegMaskVector regMasks;
Jakob Stoklund Olesen2d59cff2009-08-08 13:19:25 +000088 RegSet regsLiveInButUnused;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000089
Jakob Stoklund Olesen58b6f4d2011-01-12 21:27:48 +000090 SlotIndex lastIndex;
91
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000092 // Add Reg and any sub-registers to RV
93 void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
94 RV.push_back(Reg);
95 if (TargetRegisterInfo::isPhysicalRegister(Reg))
Jakob Stoklund Olesen54038d72012-06-01 23:28:30 +000096 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
97 RV.push_back(*SubRegs);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +000098 }
99
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000100 struct BBInfo {
101 // Is this MBB reachable from the MF entry point?
102 bool reachable;
103
104 // Vregs that must be live in because they are used without being
105 // defined. Map value is the user.
106 RegMap vregsLiveIn;
107
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000108 // Regs killed in MBB. They may be defined again, and will then be in both
109 // regsKilled and regsLiveOut.
110 RegSet regsKilled;
111
112 // Regs defined in MBB and live out. Note that vregs passing through may
113 // be live out without being mentioned here.
114 RegSet regsLiveOut;
115
116 // Vregs that pass through MBB untouched. This set is disjoint from
117 // regsKilled and regsLiveOut.
118 RegSet vregsPassed;
119
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000120 // Vregs that must pass through MBB because they are needed by a successor
121 // block. This set is disjoint from regsLiveOut.
122 RegSet vregsRequired;
123
Jakob Stoklund Olesende31b522012-08-20 20:52:06 +0000124 // Set versions of block's predecessor and successor lists.
125 BlockSet Preds, Succs;
126
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000127 BBInfo() : reachable(false) {}
128
129 // Add register to vregsPassed if it belongs there. Return true if
130 // anything changed.
131 bool addPassed(unsigned Reg) {
132 if (!TargetRegisterInfo::isVirtualRegister(Reg))
133 return false;
134 if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
135 return false;
136 return vregsPassed.insert(Reg).second;
137 }
138
139 // Same for a full set.
140 bool addPassed(const RegSet &RS) {
141 bool changed = false;
142 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
143 if (addPassed(*I))
144 changed = true;
145 return changed;
146 }
147
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000148 // Add register to vregsRequired if it belongs there. Return true if
149 // anything changed.
150 bool addRequired(unsigned Reg) {
151 if (!TargetRegisterInfo::isVirtualRegister(Reg))
152 return false;
153 if (regsLiveOut.count(Reg))
154 return false;
155 return vregsRequired.insert(Reg).second;
156 }
157
158 // Same for a full set.
159 bool addRequired(const RegSet &RS) {
160 bool changed = false;
161 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
162 if (addRequired(*I))
163 changed = true;
164 return changed;
165 }
166
167 // Same for a full map.
168 bool addRequired(const RegMap &RM) {
169 bool changed = false;
170 for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
171 if (addRequired(I->first))
172 changed = true;
173 return changed;
174 }
175
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000176 // Live-out registers are either in regsLiveOut or vregsPassed.
177 bool isLiveOut(unsigned Reg) const {
178 return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
179 }
180 };
181
182 // Extra register info per MBB.
183 DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
184
185 bool isReserved(unsigned Reg) {
Jakob Stoklund Olesen3c2a1de2009-08-04 19:18:01 +0000186 return Reg < regsReserved.size() && regsReserved.test(Reg);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000187 }
188
Lang Hames1ce837a2012-02-14 19:17:48 +0000189 bool isAllocatable(unsigned Reg) {
Jakob Stoklund Olesen244beb42012-10-16 00:05:06 +0000190 return Reg < TRI->getNumRegs() && MRI->isAllocatable(Reg);
Lang Hames1ce837a2012-02-14 19:17:48 +0000191 }
192
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000193 // Analysis information if available
194 LiveVariables *LiveVars;
Jakob Stoklund Olesen260fa282010-10-26 22:36:07 +0000195 LiveIntervals *LiveInts;
Jakob Stoklund Olesen31fffb62010-11-01 19:49:52 +0000196 LiveStacks *LiveStks;
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000197 SlotIndexes *Indexes;
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000198
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000199 void visitMachineFunctionBefore();
200 void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +0000201 void visitMachineBundleBefore(const MachineInstr *MI);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000202 void visitMachineInstrBefore(const MachineInstr *MI);
203 void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
204 void visitMachineInstrAfter(const MachineInstr *MI);
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +0000205 void visitMachineBundleAfter(const MachineInstr *MI);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000206 void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
207 void visitMachineFunctionAfter();
208
209 void report(const char *msg, const MachineFunction *MF);
210 void report(const char *msg, const MachineBasicBlock *MBB);
211 void report(const char *msg, const MachineInstr *MI);
212 void report(const char *msg, const MachineOperand *MO, unsigned MONum);
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +0000213 void report(const char *msg, const MachineFunction *MF,
214 const LiveInterval &LI);
215 void report(const char *msg, const MachineBasicBlock *MBB,
216 const LiveInterval &LI);
Matthias Braun364e6e92013-10-10 21:28:54 +0000217 void report(const char *msg, const MachineFunction *MF,
218 const LiveRange &LR);
219 void report(const char *msg, const MachineBasicBlock *MBB,
220 const LiveRange &LR);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000221
Jakob Stoklund Olesen7a837b92012-08-29 18:11:05 +0000222 void verifyInlineAsm(const MachineInstr *MI);
Jakob Stoklund Olesen7a837b92012-08-29 18:11:05 +0000223
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +0000224 void checkLiveness(const MachineOperand *MO, unsigned MONum);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000225 void markReachable(const MachineBasicBlock *MBB);
Jakob Stoklund Olesen4cb77022010-01-05 20:59:36 +0000226 void calcRegsPassed();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000227 void checkPHIOps(const MachineBasicBlock *MBB);
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000228
229 void calcRegsRequired();
230 void verifyLiveVariables();
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +0000231 void verifyLiveIntervals();
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +0000232 void verifyLiveInterval(const LiveInterval&);
Matthias Braun364e6e92013-10-10 21:28:54 +0000233 void verifyLiveRangeValue(const LiveRange&, const VNInfo*, unsigned);
234 void verifyLiveRangeSegment(const LiveRange&,
235 const LiveRange::const_iterator I, unsigned);
236 void verifyLiveRange(const LiveRange&, unsigned);
Manman Renaa6875b2013-07-15 21:26:31 +0000237
238 void verifyStackFrame();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000239 };
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000240
241 struct MachineVerifierPass : public MachineFunctionPass {
242 static char ID; // Pass ID, replacement for typeid
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +0000243 const char *const Banner;
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000244
Craig Topperc0196b12014-04-14 00:51:57 +0000245 MachineVerifierPass(const char *b = nullptr)
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +0000246 : MachineFunctionPass(ID), Banner(b) {
Owen Anderson6c18d1a2010-10-19 17:21:58 +0000247 initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
248 }
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000249
Craig Topper4584cd52014-03-07 09:26:03 +0000250 void getAnalysisUsage(AnalysisUsage &AU) const override {
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000251 AU.setPreservesAll();
252 MachineFunctionPass::getAnalysisUsage(AU);
253 }
254
Craig Topper4584cd52014-03-07 09:26:03 +0000255 bool runOnMachineFunction(MachineFunction &MF) override {
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +0000256 MF.verify(this, Banner);
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000257 return false;
258 }
259 };
260
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000261}
262
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000263char MachineVerifierPass::ID = 0;
Owen Andersond31d82d2010-08-23 17:52:01 +0000264INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
Owen Andersondf7a4f22010-10-07 22:25:06 +0000265 "Verify generated machine code", false, false)
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000266
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +0000267FunctionPass *llvm::createMachineVerifierPass(const char *Banner) {
268 return new MachineVerifierPass(Banner);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000269}
270
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +0000271void MachineFunction::verify(Pass *p, const char *Banner) const {
272 MachineVerifier(p, Banner)
273 .runOnMachineFunction(const_cast<MachineFunction&>(*this));
Jakob Stoklund Olesen27440e72009-11-13 21:56:09 +0000274}
275
Chris Lattner9e6f1f12009-08-23 02:51:22 +0000276bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
Craig Topperc0196b12014-04-14 00:51:57 +0000277 raw_ostream *OutFile = nullptr;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000278 if (OutFileName) {
Chris Lattner9e6f1f12009-08-23 02:51:22 +0000279 std::string ErrorInfo;
Rafael Espindola90c7f1c2014-02-24 18:20:12 +0000280 OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
281 sys::fs::F_Append | sys::fs::F_Text);
Chris Lattner9e6f1f12009-08-23 02:51:22 +0000282 if (!ErrorInfo.empty()) {
283 errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
284 exit(1);
285 }
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000286
Chris Lattner9e6f1f12009-08-23 02:51:22 +0000287 OS = OutFile;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000288 } else {
Chris Lattner9e6f1f12009-08-23 02:51:22 +0000289 OS = &errs();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000290 }
291
292 foundErrors = 0;
293
294 this->MF = &MF;
295 TM = &MF.getTarget();
Evan Cheng8d71a752011-06-27 21:26:13 +0000296 TII = TM->getInstrInfo();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000297 TRI = TM->getRegisterInfo();
298 MRI = &MF.getRegInfo();
299
Craig Topperc0196b12014-04-14 00:51:57 +0000300 LiveVars = nullptr;
301 LiveInts = nullptr;
302 LiveStks = nullptr;
303 Indexes = nullptr;
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000304 if (PASS) {
Jakob Stoklund Olesene7709eb2010-08-05 22:32:21 +0000305 LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
Jakob Stoklund Olesenb4ef4a92010-08-05 23:51:26 +0000306 // We don't want to verify LiveVariables if LiveIntervals is available.
307 if (!LiveInts)
308 LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
Jakob Stoklund Olesen31fffb62010-11-01 19:49:52 +0000309 LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000310 Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +0000311 }
312
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000313 visitMachineFunctionBefore();
314 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
315 MFI!=MFE; ++MFI) {
316 visitMachineBasicBlockBefore(MFI);
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +0000317 // Keep track of the current bundle header.
Craig Topperc0196b12014-04-14 00:51:57 +0000318 const MachineInstr *CurBundle = nullptr;
Jakob Stoklund Olesen29c27712012-12-18 22:55:07 +0000319 // Do we expect the next instruction to be part of the same bundle?
320 bool InBundle = false;
321
Evan Cheng7fae11b2011-12-14 02:11:42 +0000322 for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
323 MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
Jakob Stoklund Olesenb5b4a5d2011-01-12 21:27:41 +0000324 if (MBBI->getParent() != MFI) {
325 report("Bad instruction parent pointer", MFI);
326 *OS << "Instruction: " << *MBBI;
327 continue;
328 }
Jakob Stoklund Olesen29c27712012-12-18 22:55:07 +0000329
330 // Check for consistent bundle flags.
331 if (InBundle && !MBBI->isBundledWithPred())
332 report("Missing BundledPred flag, "
333 "BundledSucc was set on predecessor", MBBI);
334 if (!InBundle && MBBI->isBundledWithPred())
335 report("BundledPred flag is set, "
336 "but BundledSucc not set on predecessor", MBBI);
337
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +0000338 // Is this a bundle header?
339 if (!MBBI->isInsideBundle()) {
340 if (CurBundle)
341 visitMachineBundleAfter(CurBundle);
342 CurBundle = MBBI;
343 visitMachineBundleBefore(CurBundle);
344 } else if (!CurBundle)
345 report("No bundle header", MBBI);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000346 visitMachineInstrBefore(MBBI);
347 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
348 visitMachineOperand(&MBBI->getOperand(I), I);
349 visitMachineInstrAfter(MBBI);
Jakob Stoklund Olesen29c27712012-12-18 22:55:07 +0000350
351 // Was this the last bundled instruction?
352 InBundle = MBBI->isBundledWithSucc();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000353 }
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +0000354 if (CurBundle)
355 visitMachineBundleAfter(CurBundle);
Jakob Stoklund Olesen29c27712012-12-18 22:55:07 +0000356 if (InBundle)
357 report("BundledSucc flag set on last instruction in block", &MFI->back());
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000358 visitMachineBasicBlockAfter(MFI);
359 }
360 visitMachineFunctionAfter();
361
Chris Lattner9e6f1f12009-08-23 02:51:22 +0000362 if (OutFile)
363 delete OutFile;
364 else if (foundErrors)
Chris Lattner2104b8d2010-04-07 22:58:41 +0000365 report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000366
Jakob Stoklund Olesendcf009c2009-08-08 15:34:50 +0000367 // Clean up.
368 regsLive.clear();
369 regsDefined.clear();
370 regsDead.clear();
371 regsKilled.clear();
Jakob Stoklund Olesen16c4a972012-02-28 01:42:41 +0000372 regMasks.clear();
Jakob Stoklund Olesendcf009c2009-08-08 15:34:50 +0000373 regsLiveInButUnused.clear();
374 MBBInfoMap.clear();
375
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000376 return false; // no changes
377}
378
Chris Lattner75f40452009-08-23 01:03:30 +0000379void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000380 assert(MF);
Chris Lattner9e6f1f12009-08-23 02:51:22 +0000381 *OS << '\n';
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +0000382 if (!foundErrors++) {
383 if (Banner)
384 *OS << "# " << Banner << '\n';
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000385 MF->print(*OS, Indexes);
Jakob Stoklund Olesenbf4550e2010-12-18 00:06:56 +0000386 }
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000387 *OS << "*** Bad machine code: " << msg << " ***\n"
Craig Toppera538d832012-08-22 06:07:19 +0000388 << "- function: " << MF->getName() << "\n";
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000389}
390
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000391void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000392 assert(MBB);
393 report(msg, MBB->getParent());
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +0000394 *OS << "- basic block: BB#" << MBB->getNumber()
395 << ' ' << MBB->getName()
Roman Divackyad06cee2012-09-05 22:26:57 +0000396 << " (" << (const void*)MBB << ')';
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000397 if (Indexes)
398 *OS << " [" << Indexes->getMBBStartIdx(MBB)
399 << ';' << Indexes->getMBBEndIdx(MBB) << ')';
400 *OS << '\n';
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000401}
402
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000403void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000404 assert(MI);
405 report(msg, MI->getParent());
406 *OS << "- instruction: ";
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000407 if (Indexes && Indexes->hasIndex(MI))
408 *OS << Indexes->getInstructionIndex(MI) << '\t';
Chris Lattnera6f074f2009-08-23 03:41:05 +0000409 MI->print(*OS, TM);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000410}
411
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000412void MachineVerifier::report(const char *msg,
413 const MachineOperand *MO, unsigned MONum) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000414 assert(MO);
415 report(msg, MO->getParent());
416 *OS << "- operand " << MONum << ": ";
417 MO->print(*OS, TM);
418 *OS << "\n";
419}
420
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +0000421void MachineVerifier::report(const char *msg, const MachineFunction *MF,
422 const LiveInterval &LI) {
423 report(msg, MF);
Matthias Braunf6fe6bf2013-10-10 21:29:05 +0000424 *OS << "- interval: " << LI << '\n';
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +0000425}
426
427void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB,
428 const LiveInterval &LI) {
429 report(msg, MBB);
Matthias Braunf6fe6bf2013-10-10 21:29:05 +0000430 *OS << "- interval: " << LI << '\n';
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +0000431}
432
Matthias Braun364e6e92013-10-10 21:28:54 +0000433void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB,
434 const LiveRange &LR) {
435 report(msg, MBB);
436 *OS << "- liverange: " << LR << "\n";
437}
438
439void MachineVerifier::report(const char *msg, const MachineFunction *MF,
440 const LiveRange &LR) {
441 report(msg, MF);
442 *OS << "- liverange: " << LR << "\n";
443}
444
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000445void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000446 BBInfo &MInfo = MBBInfoMap[MBB];
447 if (!MInfo.reachable) {
448 MInfo.reachable = true;
449 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
450 SuE = MBB->succ_end(); SuI != SuE; ++SuI)
451 markReachable(*SuI);
452 }
453}
454
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000455void MachineVerifier::visitMachineFunctionBefore() {
Jakob Stoklund Olesen58b6f4d2011-01-12 21:27:48 +0000456 lastIndex = SlotIndex();
Jakob Stoklund Olesenc30a9af2012-10-15 21:57:41 +0000457 regsReserved = MRI->getReservedRegs();
Jakob Stoklund Olesen3c2a1de2009-08-04 19:18:01 +0000458
459 // A sub-register of a reserved register is also reserved
460 for (int Reg = regsReserved.find_first(); Reg>=0;
461 Reg = regsReserved.find_next(Reg)) {
Jakob Stoklund Olesen54038d72012-06-01 23:28:30 +0000462 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
Jakob Stoklund Olesen3c2a1de2009-08-04 19:18:01 +0000463 // FIXME: This should probably be:
Jakob Stoklund Olesen54038d72012-06-01 23:28:30 +0000464 // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register");
465 regsReserved.set(*SubRegs);
Jakob Stoklund Olesen3c2a1de2009-08-04 19:18:01 +0000466 }
467 }
Lang Hames1ce837a2012-02-14 19:17:48 +0000468
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000469 markReachable(&MF->front());
Jakob Stoklund Olesende31b522012-08-20 20:52:06 +0000470
471 // Build a set of the basic blocks in the function.
472 FunctionBlocks.clear();
473 for (MachineFunction::const_iterator
474 I = MF->begin(), E = MF->end(); I != E; ++I) {
475 FunctionBlocks.insert(I);
476 BBInfo &MInfo = MBBInfoMap[I];
477
478 MInfo.Preds.insert(I->pred_begin(), I->pred_end());
479 if (MInfo.Preds.size() != I->pred_size())
480 report("MBB has duplicate entries in its predecessor list.", I);
481
482 MInfo.Succs.insert(I->succ_begin(), I->succ_end());
483 if (MInfo.Succs.size() != I->succ_size())
484 report("MBB has duplicate entries in its successor list.", I);
485 }
Jakob Stoklund Olesene17c3fd2013-04-19 21:40:57 +0000486
487 // Check that the register use lists are sane.
488 MRI->verifyUseLists();
Manman Renaa6875b2013-07-15 21:26:31 +0000489
490 verifyStackFrame();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000491}
492
Jakob Stoklund Olesen1ecc8b22009-11-13 21:55:54 +0000493// Does iterator point to a and b as the first two elements?
Dan Gohmanb29cda92010-04-15 17:08:50 +0000494static bool matchPair(MachineBasicBlock::const_succ_iterator i,
495 const MachineBasicBlock *a, const MachineBasicBlock *b) {
Jakob Stoklund Olesen1ecc8b22009-11-13 21:55:54 +0000496 if (*i == a)
497 return *++i == b;
498 if (*i == b)
499 return *++i == a;
500 return false;
501}
502
503void
504MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
Craig Topperc0196b12014-04-14 00:51:57 +0000505 FirstTerminator = nullptr;
Jakob Stoklund Olesen3bb99bc2011-09-23 22:45:39 +0000506
Lang Hames1ce837a2012-02-14 19:17:48 +0000507 if (MRI->isSSA()) {
508 // If this block has allocatable physical registers live-in, check that
509 // it is an entry block or landing pad.
510 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
511 LE = MBB->livein_end();
512 LI != LE; ++LI) {
513 unsigned reg = *LI;
514 if (isAllocatable(reg) && !MBB->isLandingPad() &&
515 MBB != MBB->getParent()->begin()) {
516 report("MBB has allocable live-in, but isn't entry or landing-pad.", MBB);
517 }
518 }
519 }
520
Jakob Stoklund Olesen7c9d5842010-10-21 18:47:06 +0000521 // Count the number of landing pad successors.
Cameron Zwarich4ffda702010-12-20 04:19:48 +0000522 SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
Jakob Stoklund Olesen7c9d5842010-10-21 18:47:06 +0000523 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
Cameron Zwarich4ffda702010-12-20 04:19:48 +0000524 E = MBB->succ_end(); I != E; ++I) {
525 if ((*I)->isLandingPad())
526 LandingPadSuccs.insert(*I);
Jakob Stoklund Olesende31b522012-08-20 20:52:06 +0000527 if (!FunctionBlocks.count(*I))
528 report("MBB has successor that isn't part of the function.", MBB);
529 if (!MBBInfoMap[*I].Preds.count(MBB)) {
530 report("Inconsistent CFG", MBB);
531 *OS << "MBB is not in the predecessor list of the successor BB#"
532 << (*I)->getNumber() << ".\n";
533 }
534 }
535
536 // Check the predecessor list.
537 for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
538 E = MBB->pred_end(); I != E; ++I) {
539 if (!FunctionBlocks.count(*I))
540 report("MBB has predecessor that isn't part of the function.", MBB);
541 if (!MBBInfoMap[*I].Succs.count(MBB)) {
542 report("Inconsistent CFG", MBB);
543 *OS << "MBB is not in the successor list of the predecessor BB#"
544 << (*I)->getNumber() << ".\n";
545 }
Cameron Zwarich4ffda702010-12-20 04:19:48 +0000546 }
Bill Wendling2a401312011-05-04 22:54:05 +0000547
548 const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
549 const BasicBlock *BB = MBB->getBasicBlock();
550 if (LandingPadSuccs.size() > 1 &&
551 !(AsmInfo &&
552 AsmInfo->getExceptionHandlingType() == ExceptionHandling::SjLj &&
553 BB && isa<SwitchInst>(BB->getTerminator())))
Jakob Stoklund Olesen7c9d5842010-10-21 18:47:06 +0000554 report("MBB has more than one landing pad successor", MBB);
555
Dan Gohman352a4952009-08-27 02:43:49 +0000556 // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
Craig Topperc0196b12014-04-14 00:51:57 +0000557 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
Dan Gohman352a4952009-08-27 02:43:49 +0000558 SmallVector<MachineOperand, 4> Cond;
559 if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
560 TBB, FBB, Cond)) {
561 // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
562 // check whether its answers match up with reality.
563 if (!TBB && !FBB) {
564 // Block falls through to its successor.
565 MachineFunction::const_iterator MBBI = MBB;
566 ++MBBI;
567 if (MBBI == MF->end()) {
Dan Gohmaned10d7c2009-08-27 18:14:26 +0000568 // It's possible that the block legitimately ends with a noreturn
569 // call or an unreachable, in which case it won't actually fall
570 // out the bottom of the function.
Cameron Zwarich4ffda702010-12-20 04:19:48 +0000571 } else if (MBB->succ_size() == LandingPadSuccs.size()) {
Dan Gohmaned10d7c2009-08-27 18:14:26 +0000572 // It's possible that the block legitimately ends with a noreturn
573 // call or an unreachable, in which case it won't actuall fall
574 // out of the block.
Cameron Zwarich4ffda702010-12-20 04:19:48 +0000575 } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000576 report("MBB exits via unconditional fall-through but doesn't have "
577 "exactly one CFG successor!", MBB);
Jakob Stoklund Olesen7c9d5842010-10-21 18:47:06 +0000578 } else if (!MBB->isSuccessor(MBBI)) {
Dan Gohman352a4952009-08-27 02:43:49 +0000579 report("MBB exits via unconditional fall-through but its successor "
580 "differs from its CFG successor!", MBB);
581 }
Akira Hatanaka1b420ac2012-06-14 20:51:13 +0000582 if (!MBB->empty() && getBundleStart(&MBB->back())->isBarrier() &&
583 !TII->isPredicated(getBundleStart(&MBB->back()))) {
Dan Gohman352a4952009-08-27 02:43:49 +0000584 report("MBB exits via unconditional fall-through but ends with a "
585 "barrier instruction!", MBB);
586 }
587 if (!Cond.empty()) {
588 report("MBB exits via unconditional fall-through but has a condition!",
589 MBB);
590 }
591 } else if (TBB && !FBB && Cond.empty()) {
592 // Block unconditionally branches somewhere.
Cameron Zwarich4ffda702010-12-20 04:19:48 +0000593 if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000594 report("MBB exits via unconditional branch but doesn't have "
595 "exactly one CFG successor!", MBB);
Jakob Stoklund Olesen7c9d5842010-10-21 18:47:06 +0000596 } else if (!MBB->isSuccessor(TBB)) {
Dan Gohman352a4952009-08-27 02:43:49 +0000597 report("MBB exits via unconditional branch but the CFG "
598 "successor doesn't match the actual successor!", MBB);
599 }
600 if (MBB->empty()) {
601 report("MBB exits via unconditional branch but doesn't contain "
602 "any instructions!", MBB);
Akira Hatanaka1b420ac2012-06-14 20:51:13 +0000603 } else if (!getBundleStart(&MBB->back())->isBarrier()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000604 report("MBB exits via unconditional branch but doesn't end with a "
605 "barrier instruction!", MBB);
Akira Hatanaka1b420ac2012-06-14 20:51:13 +0000606 } else if (!getBundleStart(&MBB->back())->isTerminator()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000607 report("MBB exits via unconditional branch but the branch isn't a "
608 "terminator instruction!", MBB);
609 }
610 } else if (TBB && !FBB && !Cond.empty()) {
611 // Block conditionally branches somewhere, otherwise falls through.
612 MachineFunction::const_iterator MBBI = MBB;
613 ++MBBI;
614 if (MBBI == MF->end()) {
615 report("MBB conditionally falls through out of function!", MBB);
Dmitri Gribenko349d1a32012-12-19 22:13:01 +0000616 } else if (MBB->succ_size() == 1) {
Jakob Stoklund Olesen7d33c572012-08-20 21:39:52 +0000617 // A conditional branch with only one successor is weird, but allowed.
618 if (&*MBBI != TBB)
619 report("MBB exits via conditional branch/fall-through but only has "
620 "one CFG successor!", MBB);
621 else if (TBB != *MBB->succ_begin())
622 report("MBB exits via conditional branch/fall-through but the CFG "
623 "successor don't match the actual successor!", MBB);
624 } else if (MBB->succ_size() != 2) {
Dan Gohman352a4952009-08-27 02:43:49 +0000625 report("MBB exits via conditional branch/fall-through but doesn't have "
626 "exactly two CFG successors!", MBB);
Jakob Stoklund Olesen1ecc8b22009-11-13 21:55:54 +0000627 } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
Dan Gohman352a4952009-08-27 02:43:49 +0000628 report("MBB exits via conditional branch/fall-through but the CFG "
629 "successors don't match the actual successors!", MBB);
630 }
631 if (MBB->empty()) {
632 report("MBB exits via conditional branch/fall-through but doesn't "
633 "contain any instructions!", MBB);
Akira Hatanaka1b420ac2012-06-14 20:51:13 +0000634 } else if (getBundleStart(&MBB->back())->isBarrier()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000635 report("MBB exits via conditional branch/fall-through but ends with a "
636 "barrier instruction!", MBB);
Akira Hatanaka1b420ac2012-06-14 20:51:13 +0000637 } else if (!getBundleStart(&MBB->back())->isTerminator()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000638 report("MBB exits via conditional branch/fall-through but the branch "
639 "isn't a terminator instruction!", MBB);
640 }
641 } else if (TBB && FBB) {
642 // Block conditionally branches somewhere, otherwise branches
643 // somewhere else.
Jakob Stoklund Olesen7d33c572012-08-20 21:39:52 +0000644 if (MBB->succ_size() == 1) {
645 // A conditional branch with only one successor is weird, but allowed.
646 if (FBB != TBB)
647 report("MBB exits via conditional branch/branch through but only has "
648 "one CFG successor!", MBB);
649 else if (TBB != *MBB->succ_begin())
650 report("MBB exits via conditional branch/branch through but the CFG "
651 "successor don't match the actual successor!", MBB);
652 } else if (MBB->succ_size() != 2) {
Dan Gohman352a4952009-08-27 02:43:49 +0000653 report("MBB exits via conditional branch/branch but doesn't have "
654 "exactly two CFG successors!", MBB);
Jakob Stoklund Olesen1ecc8b22009-11-13 21:55:54 +0000655 } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
Dan Gohman352a4952009-08-27 02:43:49 +0000656 report("MBB exits via conditional branch/branch but the CFG "
657 "successors don't match the actual successors!", MBB);
658 }
659 if (MBB->empty()) {
660 report("MBB exits via conditional branch/branch but doesn't "
661 "contain any instructions!", MBB);
Akira Hatanaka1b420ac2012-06-14 20:51:13 +0000662 } else if (!getBundleStart(&MBB->back())->isBarrier()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000663 report("MBB exits via conditional branch/branch but doesn't end with a "
664 "barrier instruction!", MBB);
Akira Hatanaka1b420ac2012-06-14 20:51:13 +0000665 } else if (!getBundleStart(&MBB->back())->isTerminator()) {
Dan Gohman352a4952009-08-27 02:43:49 +0000666 report("MBB exits via conditional branch/branch but the branch "
667 "isn't a terminator instruction!", MBB);
668 }
669 if (Cond.empty()) {
670 report("MBB exits via conditinal branch/branch but there's no "
671 "condition!", MBB);
672 }
673 } else {
674 report("AnalyzeBranch returned invalid data!", MBB);
675 }
676 }
677
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000678 regsLive.clear();
Dan Gohman9d2d0532010-04-13 16:57:55 +0000679 for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000680 E = MBB->livein_end(); I != E; ++I) {
681 if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
682 report("MBB live-in list contains non-physical register", MBB);
683 continue;
684 }
Chad Rosierabdb1d62013-05-22 23:17:36 +0000685 for (MCSubRegIterator SubRegs(*I, TRI, /*IncludeSelf=*/true);
686 SubRegs.isValid(); ++SubRegs)
Jakob Stoklund Olesen54038d72012-06-01 23:28:30 +0000687 regsLive.insert(*SubRegs);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000688 }
Jakob Stoklund Olesen2d59cff2009-08-08 13:19:25 +0000689 regsLiveInButUnused = regsLive;
Jakob Stoklund Olesen0e73fdf2009-08-13 16:19:51 +0000690
691 const MachineFrameInfo *MFI = MF->getFrameInfo();
692 assert(MFI && "Function has no frame info");
693 BitVector PR = MFI->getPristineRegs(MBB);
694 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
Chad Rosierabdb1d62013-05-22 23:17:36 +0000695 for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
696 SubRegs.isValid(); ++SubRegs)
Jakob Stoklund Olesen54038d72012-06-01 23:28:30 +0000697 regsLive.insert(*SubRegs);
Jakob Stoklund Olesen0e73fdf2009-08-13 16:19:51 +0000698 }
699
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000700 regsKilled.clear();
701 regsDefined.clear();
Jakob Stoklund Olesen58b6f4d2011-01-12 21:27:48 +0000702
703 if (Indexes)
704 lastIndex = Indexes->getMBBStartIdx(MBB);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000705}
706
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +0000707// This function gets called for all bundle headers, including normal
708// stand-alone unbundled instructions.
709void MachineVerifier::visitMachineBundleBefore(const MachineInstr *MI) {
710 if (Indexes && Indexes->hasIndex(MI)) {
711 SlotIndex idx = Indexes->getInstructionIndex(MI);
712 if (!(idx > lastIndex)) {
713 report("Instruction index out of order", MI);
714 *OS << "Last instruction was at " << lastIndex << '\n';
715 }
716 lastIndex = idx;
717 }
Pete Coopercd720162012-06-07 17:41:39 +0000718
719 // Ensure non-terminators don't follow terminators.
720 // Ignore predicated terminators formed by if conversion.
721 // FIXME: If conversion shouldn't need to violate this rule.
722 if (MI->isTerminator() && !TII->isPredicated(MI)) {
723 if (!FirstTerminator)
724 FirstTerminator = MI;
725 } else if (FirstTerminator) {
726 report("Non-terminator instruction after the first terminator", MI);
727 *OS << "First terminator was:\t" << *FirstTerminator;
728 }
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +0000729}
730
Jakob Stoklund Olesen7a837b92012-08-29 18:11:05 +0000731// The operands on an INLINEASM instruction must follow a template.
732// Verify that the flag operands make sense.
733void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
734 // The first two operands on INLINEASM are the asm string and global flags.
735 if (MI->getNumOperands() < 2) {
736 report("Too few operands on inline asm", MI);
737 return;
738 }
739 if (!MI->getOperand(0).isSymbol())
740 report("Asm string must be an external symbol", MI);
741 if (!MI->getOperand(1).isImm())
742 report("Asm flags must be an immediate", MI);
Chad Rosier9e1274f2012-10-30 19:11:54 +0000743 // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
744 // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16.
745 if (!isUInt<5>(MI->getOperand(1).getImm()))
Jakob Stoklund Olesen7a837b92012-08-29 18:11:05 +0000746 report("Unknown asm flags", &MI->getOperand(1), 1);
747
748 assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed");
749
750 unsigned OpNo = InlineAsm::MIOp_FirstOperand;
751 unsigned NumOps;
752 for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
753 const MachineOperand &MO = MI->getOperand(OpNo);
754 // There may be implicit ops after the fixed operands.
755 if (!MO.isImm())
756 break;
757 NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
758 }
759
760 if (OpNo > MI->getNumOperands())
761 report("Missing operands in last group", MI);
762
763 // An optional MDNode follows the groups.
764 if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
765 ++OpNo;
766
767 // All trailing operands must be implicit registers.
768 for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
769 const MachineOperand &MO = MI->getOperand(OpNo);
770 if (!MO.isReg() || !MO.isImplicit())
771 report("Expected implicit register after groups", &MO, OpNo);
772 }
773}
774
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000775void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
Evan Cheng6cc775f2011-06-28 19:10:37 +0000776 const MCInstrDesc &MCID = MI->getDesc();
777 if (MI->getNumOperands() < MCID.getNumOperands()) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000778 report("Too few operands", MI);
Evan Cheng6cc775f2011-06-28 19:10:37 +0000779 *OS << MCID.getNumOperands() << " operands expected, but "
Matt Arsenault23c92742013-11-15 22:18:19 +0000780 << MI->getNumOperands() << " given.\n";
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000781 }
Dan Gohmandb9493c2009-10-07 17:36:00 +0000782
Jakob Stoklund Olesendbbff782012-08-29 00:38:03 +0000783 // Check the tied operands.
Jakob Stoklund Olesen7a837b92012-08-29 18:11:05 +0000784 if (MI->isInlineAsm())
785 verifyInlineAsm(MI);
Jakob Stoklund Olesendbbff782012-08-29 00:38:03 +0000786
Dan Gohmandb9493c2009-10-07 17:36:00 +0000787 // Check the MachineMemOperands for basic consistency.
788 for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
789 E = MI->memoperands_end(); I != E; ++I) {
Evan Cheng7f8e5632011-12-07 07:15:52 +0000790 if ((*I)->isLoad() && !MI->mayLoad())
Dan Gohmandb9493c2009-10-07 17:36:00 +0000791 report("Missing mayLoad flag", MI);
Evan Cheng7f8e5632011-12-07 07:15:52 +0000792 if ((*I)->isStore() && !MI->mayStore())
Dan Gohmandb9493c2009-10-07 17:36:00 +0000793 report("Missing mayStore flag", MI);
794 }
Jakob Stoklund Olesene7709eb2010-08-05 22:32:21 +0000795
796 // Debug values must not have a slot index.
Jakob Stoklund Olesen5aafb562012-02-27 18:24:30 +0000797 // Other instructions must have one, unless they are inside a bundle.
Jakob Stoklund Olesene7709eb2010-08-05 22:32:21 +0000798 if (LiveInts) {
799 bool mapped = !LiveInts->isNotInMIMap(MI);
800 if (MI->isDebugValue()) {
801 if (mapped)
802 report("Debug instruction has a slot index", MI);
Jakob Stoklund Olesen5aafb562012-02-27 18:24:30 +0000803 } else if (MI->isInsideBundle()) {
804 if (mapped)
805 report("Instruction inside bundle has a slot index", MI);
Jakob Stoklund Olesene7709eb2010-08-05 22:32:21 +0000806 } else {
807 if (!mapped)
808 report("Missing slot index", MI);
809 }
810 }
811
Andrew Trick924123a2011-09-21 02:20:46 +0000812 StringRef ErrorInfo;
813 if (!TII->verifyInstruction(MI, ErrorInfo))
814 report(ErrorInfo.data(), MI);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000815}
816
817void
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +0000818MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000819 const MachineInstr *MI = MO->getParent();
Evan Cheng6cc775f2011-06-28 19:10:37 +0000820 const MCInstrDesc &MCID = MI->getDesc();
Jakob Stoklund Olesene61c7a32009-05-16 07:25:20 +0000821
Evan Cheng6cc775f2011-06-28 19:10:37 +0000822 // The first MCID.NumDefs operands must be explicit register defines
823 if (MONum < MCID.getNumDefs()) {
Richard Smith8f3447c2012-08-15 01:39:31 +0000824 const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
Jakob Stoklund Olesene61c7a32009-05-16 07:25:20 +0000825 if (!MO->isReg())
826 report("Explicit definition must be a register", MO, MONum);
Evan Cheng76f6e262012-05-29 19:40:44 +0000827 else if (!MO->isDef() && !MCOI.isOptionalDef())
Jakob Stoklund Olesene61c7a32009-05-16 07:25:20 +0000828 report("Explicit definition marked as use", MO, MONum);
829 else if (MO->isImplicit())
830 report("Explicit definition marked as implicit", MO, MONum);
Evan Cheng6cc775f2011-06-28 19:10:37 +0000831 } else if (MONum < MCID.getNumOperands()) {
Richard Smith8f3447c2012-08-15 01:39:31 +0000832 const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
Eric Christopherbcc230a72010-11-17 00:55:36 +0000833 // Don't check if it's the last operand in a variadic instruction. See,
834 // e.g., LDM_RET in the arm back end.
Evan Cheng6cc775f2011-06-28 19:10:37 +0000835 if (MO->isReg() &&
Evan Cheng7f8e5632011-12-07 07:15:52 +0000836 !(MI->isVariadic() && MONum == MCID.getNumOperands()-1)) {
Evan Cheng6cc775f2011-06-28 19:10:37 +0000837 if (MO->isDef() && !MCOI.isOptionalDef())
Matthias Braun6a57acf2013-10-04 16:53:00 +0000838 report("Explicit operand marked as def", MO, MONum);
Jakob Stoklund Olesen75b9c272009-09-23 20:57:55 +0000839 if (MO->isImplicit())
840 report("Explicit operand marked as implicit", MO, MONum);
841 }
Jakob Stoklund Olesendbbff782012-08-29 00:38:03 +0000842
Jakob Stoklund Olesenc7579cd2012-09-04 18:38:28 +0000843 int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
844 if (TiedTo != -1) {
Jakob Stoklund Olesendbbff782012-08-29 00:38:03 +0000845 if (!MO->isReg())
846 report("Tied use must be a register", MO, MONum);
847 else if (!MO->isTied())
848 report("Operand should be tied", MO, MONum);
Jakob Stoklund Olesenc7579cd2012-09-04 18:38:28 +0000849 else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
850 report("Tied def doesn't match MCInstrDesc", MO, MONum);
Jakob Stoklund Olesendbbff782012-08-29 00:38:03 +0000851 } else if (MO->isReg() && MO->isTied())
852 report("Explicit operand should not be tied", MO, MONum);
Jakob Stoklund Olesen75b9c272009-09-23 20:57:55 +0000853 } else {
Jakob Stoklund Olesen3db495232009-12-22 21:48:20 +0000854 // ARM adds %reg0 operands to indicate predicates. We'll allow that.
Evan Cheng7f8e5632011-12-07 07:15:52 +0000855 if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
Jakob Stoklund Olesen75b9c272009-09-23 20:57:55 +0000856 report("Extra explicit operand on non-variadic instruction", MO, MONum);
Jakob Stoklund Olesene61c7a32009-05-16 07:25:20 +0000857 }
858
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000859 switch (MO->getType()) {
860 case MachineOperand::MO_Register: {
861 const unsigned Reg = MO->getReg();
862 if (!Reg)
863 return;
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +0000864 if (MRI->tracksLiveness() && !MI->isDebugValue())
865 checkLiveness(MO, MONum);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000866
Jakob Stoklund Olesenc7579cd2012-09-04 18:38:28 +0000867 // Verify the consistency of tied operands.
868 if (MO->isTied()) {
869 unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
870 const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
871 if (!OtherMO.isReg())
872 report("Must be tied to a register", MO, MONum);
873 if (!OtherMO.isTied())
874 report("Missing tie flags on tied operand", MO, MONum);
875 if (MI->findTiedOperandIdx(OtherIdx) != MONum)
876 report("Inconsistent tie links", MO, MONum);
877 if (MONum < MCID.getNumDefs()) {
878 if (OtherIdx < MCID.getNumOperands()) {
879 if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
880 report("Explicit def tied to explicit use without tie constraint",
881 MO, MONum);
882 } else {
883 if (!OtherMO.isImplicit())
884 report("Explicit def should be tied to implicit use", MO, MONum);
885 }
886 }
887 }
888
Jakob Stoklund Olesenc6fd3de2012-07-25 16:49:11 +0000889 // Verify two-address constraints after leaving SSA form.
890 unsigned DefIdx;
891 if (!MRI->isSSA() && MO->isUse() &&
892 MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
893 Reg != MI->getOperand(DefIdx).getReg())
894 report("Two-address instruction operands must be identical", MO, MONum);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000895
896 // Check register classes.
Evan Cheng6cc775f2011-06-28 19:10:37 +0000897 if (MONum < MCID.getNumOperands() && !MO->isImplicit()) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000898 unsigned SubIdx = MO->getSubReg();
899
900 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000901 if (SubIdx) {
Jakob Stoklund Oleseneb38bd8c2011-10-05 22:12:57 +0000902 report("Illegal subregister index for physical register", MO, MONum);
903 return;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000904 }
Jakob Stoklund Olesen3c52f022012-05-07 22:10:26 +0000905 if (const TargetRegisterClass *DRC =
906 TII->getRegClass(MCID, MONum, TRI, *MF)) {
Jakob Stoklund Oleseneb38bd8c2011-10-05 22:12:57 +0000907 if (!DRC->contains(Reg)) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000908 report("Illegal physical register for instruction", MO, MONum);
Jakob Stoklund Oleseneb38bd8c2011-10-05 22:12:57 +0000909 *OS << TRI->getName(Reg) << " is not a "
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000910 << DRC->getName() << " register.\n";
911 }
912 }
913 } else {
914 // Virtual register.
915 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
916 if (SubIdx) {
Jakob Stoklund Oleseneb38bd8c2011-10-05 22:12:57 +0000917 const TargetRegisterClass *SRC =
918 TRI->getSubClassWithSubReg(RC, SubIdx);
Jakob Stoklund Olesen48431782010-05-18 17:31:12 +0000919 if (!SRC) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000920 report("Invalid subregister index for virtual register", MO, MONum);
Jakob Stoklund Olesen48431782010-05-18 17:31:12 +0000921 *OS << "Register class " << RC->getName()
922 << " does not support subreg index " << SubIdx << "\n";
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000923 return;
924 }
Jakob Stoklund Oleseneb38bd8c2011-10-05 22:12:57 +0000925 if (RC != SRC) {
926 report("Invalid register class for subregister index", MO, MONum);
927 *OS << "Register class " << RC->getName()
928 << " does not fully support subreg index " << SubIdx << "\n";
929 return;
930 }
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000931 }
Jakob Stoklund Olesen3c52f022012-05-07 22:10:26 +0000932 if (const TargetRegisterClass *DRC =
933 TII->getRegClass(MCID, MONum, TRI, *MF)) {
Jakob Stoklund Oleseneb38bd8c2011-10-05 22:12:57 +0000934 if (SubIdx) {
935 const TargetRegisterClass *SuperRC =
936 TRI->getLargestLegalSuperClass(RC);
937 if (!SuperRC) {
938 report("No largest legal super class exists.", MO, MONum);
939 return;
940 }
941 DRC = TRI->getMatchingSuperRegClass(SuperRC, DRC, SubIdx);
942 if (!DRC) {
943 report("No matching super-reg register class.", MO, MONum);
944 return;
945 }
946 }
Jakob Stoklund Olesenaff10602011-06-02 05:43:46 +0000947 if (!RC->hasSuperClassEq(DRC)) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000948 report("Illegal virtual register for instruction", MO, MONum);
949 *OS << "Expected a " << DRC->getName() << " register, but got a "
950 << RC->getName() << " register\n";
951 }
952 }
953 }
954 }
955 break;
956 }
Jakob Stoklund Olesenf6eb7d82009-09-21 07:19:08 +0000957
Jakob Stoklund Olesen16c4a972012-02-28 01:42:41 +0000958 case MachineOperand::MO_RegisterMask:
959 regMasks.push_back(MO->getRegMask());
960 break;
961
Jakob Stoklund Olesenf6eb7d82009-09-21 07:19:08 +0000962 case MachineOperand::MO_MachineBasicBlock:
Chris Lattnerb06015a2010-02-09 19:54:29 +0000963 if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
964 report("PHI operand is not in the CFG", MO, MONum);
Jakob Stoklund Olesenf6eb7d82009-09-21 07:19:08 +0000965 break;
966
Jakob Stoklund Olesen31fffb62010-11-01 19:49:52 +0000967 case MachineOperand::MO_FrameIndex:
968 if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
969 LiveInts && !LiveInts->isNotInMIMap(MI)) {
970 LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
971 SlotIndex Idx = LiveInts->getInstructionIndex(MI);
Evan Cheng7f8e5632011-12-07 07:15:52 +0000972 if (MI->mayLoad() && !LI.liveAt(Idx.getRegSlot(true))) {
Jakob Stoklund Olesen31fffb62010-11-01 19:49:52 +0000973 report("Instruction loads from dead spill slot", MO, MONum);
974 *OS << "Live stack: " << LI << '\n';
975 }
Evan Cheng7f8e5632011-12-07 07:15:52 +0000976 if (MI->mayStore() && !LI.liveAt(Idx.getRegSlot())) {
Jakob Stoklund Olesen31fffb62010-11-01 19:49:52 +0000977 report("Instruction stores to dead spill slot", MO, MONum);
978 *OS << "Live stack: " << LI << '\n';
979 }
980 }
981 break;
982
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +0000983 default:
984 break;
985 }
986}
987
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +0000988void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
989 const MachineInstr *MI = MO->getParent();
990 const unsigned Reg = MO->getReg();
991
992 // Both use and def operands can read a register.
993 if (MO->readsReg()) {
994 regsLiveInButUnused.erase(Reg);
995
Jakob Stoklund Olesenc6fd3de2012-07-25 16:49:11 +0000996 if (MO->isKill())
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +0000997 addRegWithSubRegs(regsKilled, Reg);
998
999 // Check that LiveVars knows this kill.
1000 if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
1001 MO->isKill()) {
1002 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1003 if (std::find(VI.Kills.begin(), VI.Kills.end(), MI) == VI.Kills.end())
1004 report("Kill missing from LiveVariables", MO, MONum);
1005 }
1006
1007 // Check LiveInts liveness and kill.
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001008 if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
1009 SlotIndex UseIdx = LiveInts->getInstructionIndex(MI);
1010 // Check the cached regunit intervals.
1011 if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isReserved(Reg)) {
1012 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
Matthias Braun34e1be92013-10-10 21:29:02 +00001013 if (const LiveRange *LR = LiveInts->getCachedRegUnit(*Units)) {
1014 LiveQueryResult LRQ = LR->Query(UseIdx);
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001015 if (!LRQ.valueIn()) {
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001016 report("No live segment at use", MO, MONum);
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001017 *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI)
Matthias Braun34e1be92013-10-10 21:29:02 +00001018 << ' ' << *LR << '\n';
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001019 }
1020 if (MO->isKill() && !LRQ.isKill()) {
1021 report("Live range continues after kill flag", MO, MONum);
Matthias Braun34e1be92013-10-10 21:29:02 +00001022 *OS << PrintRegUnit(*Units, TRI) << ' ' << *LR << '\n';
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001023 }
1024 }
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001025 }
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001026 }
1027
1028 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1029 if (LiveInts->hasInterval(Reg)) {
1030 // This is a virtual register interval.
1031 const LiveInterval &LI = LiveInts->getInterval(Reg);
Matthias Braun88dd0ab2013-10-10 21:28:52 +00001032 LiveQueryResult LRQ = LI.Query(UseIdx);
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001033 if (!LRQ.valueIn()) {
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001034 report("No live segment at use", MO, MONum);
Jakob Stoklund Olesena766b472012-08-01 23:52:40 +00001035 *OS << UseIdx << " is not live in " << LI << '\n';
1036 }
1037 // Check for extra kill flags.
1038 // Note that we allow missing kill flags for now.
1039 if (MO->isKill() && !LRQ.isKill()) {
1040 report("Live range continues after kill flag", MO, MONum);
1041 *OS << "Live range: " << LI << '\n';
1042 }
1043 } else {
1044 report("Virtual register has no live interval", MO, MONum);
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001045 }
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001046 }
1047 }
1048
1049 // Use of a dead register.
1050 if (!regsLive.count(Reg)) {
1051 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1052 // Reserved registers may be used even when 'dead'.
1053 if (!isReserved(Reg))
1054 report("Using an undefined physical register", MO, MONum);
Pete Cooperdcf94db2012-07-19 23:40:38 +00001055 } else if (MRI->def_empty(Reg)) {
1056 report("Reading virtual register without a def", MO, MONum);
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001057 } else {
1058 BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1059 // We don't know which virtual registers are live in, so only complain
1060 // if vreg was killed in this MBB. Otherwise keep track of vregs that
1061 // must be live in. PHI instructions are handled separately.
1062 if (MInfo.regsKilled.count(Reg))
1063 report("Using a killed virtual register", MO, MONum);
1064 else if (!MI->isPHI())
1065 MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
1066 }
1067 }
1068 }
1069
1070 if (MO->isDef()) {
1071 // Register defined.
1072 // TODO: verify that earlyclobber ops are not used.
1073 if (MO->isDead())
1074 addRegWithSubRegs(regsDead, Reg);
1075 else
1076 addRegWithSubRegs(regsDefined, Reg);
1077
1078 // Verify SSA form.
1079 if (MRI->isSSA() && TargetRegisterInfo::isVirtualRegister(Reg) &&
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +00001080 std::next(MRI->def_begin(Reg)) != MRI->def_end())
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001081 report("Multiple virtual register defs in SSA form", MO, MONum);
1082
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001083 // Check LiveInts for a live segment, but only for virtual registers.
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001084 if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
1085 !LiveInts->isNotInMIMap(MI)) {
Jakob Stoklund Olesenb033ded2012-06-22 22:23:58 +00001086 SlotIndex DefIdx = LiveInts->getInstructionIndex(MI);
1087 DefIdx = DefIdx.getRegSlot(MO->isEarlyClobber());
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001088 if (LiveInts->hasInterval(Reg)) {
1089 const LiveInterval &LI = LiveInts->getInterval(Reg);
1090 if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
1091 assert(VNI && "NULL valno is not allowed");
Jakob Stoklund Olesenb033ded2012-06-22 22:23:58 +00001092 if (VNI->def != DefIdx) {
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001093 report("Inconsistent valno->def", MO, MONum);
1094 *OS << "Valno " << VNI->id << " is not defined at "
1095 << DefIdx << " in " << LI << '\n';
1096 }
1097 } else {
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001098 report("No live segment at def", MO, MONum);
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001099 *OS << DefIdx << " is not live in " << LI << '\n';
1100 }
Pedro Artigas71f87cb2013-11-08 22:46:28 +00001101 // Check that, if the dead def flag is present, LiveInts agree.
1102 if (MO->isDead()) {
1103 LiveQueryResult LRQ = LI.Query(DefIdx);
1104 if (!LRQ.isDeadDef()) {
1105 report("Live range continues after dead def flag", MO, MONum);
1106 *OS << "Live range: " << LI << '\n';
1107 }
1108 }
Jakob Stoklund Olesenb21df322012-03-28 20:47:35 +00001109 } else {
1110 report("Virtual register has no Live interval", MO, MONum);
1111 }
1112 }
1113 }
1114}
1115
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +00001116void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
Jakob Stoklund Olesen00e7dff2012-06-06 22:34:30 +00001117}
1118
1119// This function gets called after visiting all instructions in a bundle. The
1120// argument points to the bundle header.
1121// Normal stand-alone instructions are also considered 'bundles', and this
1122// function is called for all of them.
1123void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001124 BBInfo &MInfo = MBBInfoMap[MI->getParent()];
1125 set_union(MInfo.regsKilled, regsKilled);
Jakob Stoklund Olesen45833552010-08-05 18:59:59 +00001126 set_subtract(regsLive, regsKilled); regsKilled.clear();
Jakob Stoklund Olesen16c4a972012-02-28 01:42:41 +00001127 // Kill any masked registers.
1128 while (!regMasks.empty()) {
1129 const uint32_t *Mask = regMasks.pop_back_val();
1130 for (RegSet::iterator I = regsLive.begin(), E = regsLive.end(); I != E; ++I)
1131 if (TargetRegisterInfo::isPhysicalRegister(*I) &&
1132 MachineOperand::clobbersPhysReg(Mask, *I))
1133 regsDead.push_back(*I);
1134 }
Jakob Stoklund Olesen45833552010-08-05 18:59:59 +00001135 set_subtract(regsLive, regsDead); regsDead.clear();
1136 set_union(regsLive, regsDefined); regsDefined.clear();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001137}
1138
1139void
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +00001140MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001141 MBBInfoMap[MBB].regsLiveOut = regsLive;
1142 regsLive.clear();
Jakob Stoklund Olesen58b6f4d2011-01-12 21:27:48 +00001143
1144 if (Indexes) {
1145 SlotIndex stop = Indexes->getMBBEndIdx(MBB);
1146 if (!(stop > lastIndex)) {
1147 report("Block ends before last instruction index", MBB);
1148 *OS << "Block ends at " << stop
1149 << " last instruction was at " << lastIndex << '\n';
1150 }
1151 lastIndex = stop;
1152 }
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001153}
1154
1155// Calculate the largest possible vregsPassed sets. These are the registers that
1156// can pass through an MBB live, but may not be live every time. It is assumed
1157// that all vregsPassed sets are empty before the call.
Jakob Stoklund Olesen4cb77022010-01-05 20:59:36 +00001158void MachineVerifier::calcRegsPassed() {
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001159 // First push live-out regs to successors' vregsPassed. Remember the MBBs that
1160 // have any vregsPassed.
Jakob Stoklund Olesen6ea6a1442012-03-10 00:36:04 +00001161 SmallPtrSet<const MachineBasicBlock*, 8> todo;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001162 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1163 MFI != MFE; ++MFI) {
1164 const MachineBasicBlock &MBB(*MFI);
1165 BBInfo &MInfo = MBBInfoMap[&MBB];
1166 if (!MInfo.reachable)
1167 continue;
1168 for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
1169 SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
1170 BBInfo &SInfo = MBBInfoMap[*SuI];
1171 if (SInfo.addPassed(MInfo.regsLiveOut))
1172 todo.insert(*SuI);
1173 }
1174 }
1175
1176 // Iteratively push vregsPassed to successors. This will converge to the same
1177 // final state regardless of DenseSet iteration order.
1178 while (!todo.empty()) {
1179 const MachineBasicBlock *MBB = *todo.begin();
1180 todo.erase(MBB);
1181 BBInfo &MInfo = MBBInfoMap[MBB];
1182 for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
1183 SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
1184 if (*SuI == MBB)
1185 continue;
1186 BBInfo &SInfo = MBBInfoMap[*SuI];
1187 if (SInfo.addPassed(MInfo.vregsPassed))
1188 todo.insert(*SuI);
1189 }
1190 }
1191}
1192
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001193// Calculate the set of virtual registers that must be passed through each basic
1194// block in order to satisfy the requirements of successor blocks. This is very
Jakob Stoklund Olesen4cb77022010-01-05 20:59:36 +00001195// similar to calcRegsPassed, only backwards.
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001196void MachineVerifier::calcRegsRequired() {
1197 // First push live-in regs to predecessors' vregsRequired.
Jakob Stoklund Olesen6ea6a1442012-03-10 00:36:04 +00001198 SmallPtrSet<const MachineBasicBlock*, 8> todo;
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001199 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1200 MFI != MFE; ++MFI) {
1201 const MachineBasicBlock &MBB(*MFI);
1202 BBInfo &MInfo = MBBInfoMap[&MBB];
1203 for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
1204 PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
1205 BBInfo &PInfo = MBBInfoMap[*PrI];
1206 if (PInfo.addRequired(MInfo.vregsLiveIn))
1207 todo.insert(*PrI);
1208 }
1209 }
1210
1211 // Iteratively push vregsRequired to predecessors. This will converge to the
1212 // same final state regardless of DenseSet iteration order.
1213 while (!todo.empty()) {
1214 const MachineBasicBlock *MBB = *todo.begin();
1215 todo.erase(MBB);
1216 BBInfo &MInfo = MBBInfoMap[MBB];
1217 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1218 PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1219 if (*PrI == MBB)
1220 continue;
1221 BBInfo &SInfo = MBBInfoMap[*PrI];
1222 if (SInfo.addRequired(MInfo.vregsRequired))
1223 todo.insert(*PrI);
1224 }
1225 }
1226}
1227
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001228// Check PHI instructions at the beginning of MBB. It is assumed that
Jakob Stoklund Olesen4cb77022010-01-05 20:59:36 +00001229// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +00001230void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
Jakob Stoklund Olesen6ea6a1442012-03-10 00:36:04 +00001231 SmallPtrSet<const MachineBasicBlock*, 8> seen;
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001232 for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
Chris Lattnerb06015a2010-02-09 19:54:29 +00001233 BBI != BBE && BBI->isPHI(); ++BBI) {
Jakob Stoklund Olesen6ea6a1442012-03-10 00:36:04 +00001234 seen.clear();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001235
1236 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
1237 unsigned Reg = BBI->getOperand(i).getReg();
1238 const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
1239 if (!Pre->isSuccessor(MBB))
1240 continue;
1241 seen.insert(Pre);
1242 BBInfo &PrInfo = MBBInfoMap[Pre];
1243 if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
1244 report("PHI operand is not live-out from predecessor",
1245 &BBI->getOperand(i), i);
1246 }
1247
1248 // Did we see all predecessors?
1249 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
1250 PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
1251 if (!seen.count(*PrI)) {
1252 report("Missing PHI operand", BBI);
Dan Gohman34341e62009-10-31 20:19:03 +00001253 *OS << "BB#" << (*PrI)->getNumber()
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001254 << " is a predecessor according to the CFG.\n";
1255 }
1256 }
1257 }
1258}
1259
Jakob Stoklund Olesen63c733f2009-10-04 18:18:39 +00001260void MachineVerifier::visitMachineFunctionAfter() {
Jakob Stoklund Olesen4cb77022010-01-05 20:59:36 +00001261 calcRegsPassed();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001262
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001263 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1264 MFI != MFE; ++MFI) {
1265 BBInfo &MInfo = MBBInfoMap[MFI];
1266
1267 // Skip unreachable MBBs.
1268 if (!MInfo.reachable)
1269 continue;
1270
1271 checkPHIOps(MFI);
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001272 }
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001273
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001274 // Now check liveness info if available
Jakob Stoklund Olesen9f3e5742012-03-10 00:36:06 +00001275 calcRegsRequired();
1276
Jakob Stoklund Olesenda9ea1d2012-06-29 21:00:00 +00001277 // Check for killed virtual registers that should be live out.
1278 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1279 MFI != MFE; ++MFI) {
1280 BBInfo &MInfo = MBBInfoMap[MFI];
1281 for (RegSet::iterator
1282 I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
1283 ++I)
1284 if (MInfo.regsKilled.count(*I)) {
Bill Wendlingd1634052012-07-19 00:04:14 +00001285 report("Virtual register killed in block, but needed live out.", MFI);
1286 *OS << "Virtual register " << PrintReg(*I)
Jakob Stoklund Olesenda9ea1d2012-06-29 21:00:00 +00001287 << " is used after the block.\n";
1288 }
1289 }
1290
Jakob Stoklund Olesena57fc122012-06-25 18:18:27 +00001291 if (!MF->empty()) {
Jakob Stoklund Olesen9f3e5742012-03-10 00:36:06 +00001292 BBInfo &MInfo = MBBInfoMap[&MF->front()];
1293 for (RegSet::iterator
1294 I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
Jakob Stoklund Olesen99014ff2012-03-10 00:44:11 +00001295 ++I)
1296 report("Virtual register def doesn't dominate all uses.",
1297 MRI->getVRegDef(*I));
Jakob Stoklund Olesen9f3e5742012-03-10 00:36:06 +00001298 }
1299
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001300 if (LiveVars)
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001301 verifyLiveVariables();
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001302 if (LiveInts)
1303 verifyLiveIntervals();
Jakob Stoklund Olesen36c027a2009-05-16 00:33:53 +00001304}
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001305
1306void MachineVerifier::verifyLiveVariables() {
1307 assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
Jakob Stoklund Olesen6ff70ad32011-01-08 23:11:02 +00001308 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1309 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001310 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
1311 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
1312 MFI != MFE; ++MFI) {
1313 BBInfo &MInfo = MBBInfoMap[MFI];
1314
1315 // Our vregsRequired should be identical to LiveVariables' AliveBlocks
1316 if (MInfo.vregsRequired.count(Reg)) {
1317 if (!VI.AliveBlocks.test(MFI->getNumber())) {
1318 report("LiveVariables: Block missing from AliveBlocks", MFI);
Jakob Stoklund Olesen1331a152011-01-09 03:05:53 +00001319 *OS << "Virtual register " << PrintReg(Reg)
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001320 << " must be live through the block.\n";
1321 }
1322 } else {
1323 if (VI.AliveBlocks.test(MFI->getNumber())) {
1324 report("LiveVariables: Block should not be in AliveBlocks", MFI);
Jakob Stoklund Olesen1331a152011-01-09 03:05:53 +00001325 *OS << "Virtual register " << PrintReg(Reg)
Jakob Stoklund Olesen9cbffd22009-11-18 20:36:57 +00001326 << " is not needed live through the block.\n";
1327 }
1328 }
1329 }
1330 }
1331}
1332
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001333void MachineVerifier::verifyLiveIntervals() {
1334 assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
Jakob Stoklund Olesen781e0b92012-06-20 23:23:59 +00001335 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1336 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
Jakob Stoklund Olesen1a065e42010-10-06 23:54:35 +00001337
1338 // Spilling and splitting may leave unused registers around. Skip them.
Jakob Stoklund Olesen781e0b92012-06-20 23:23:59 +00001339 if (MRI->reg_nodbg_empty(Reg))
Jakob Stoklund Olesen1a065e42010-10-06 23:54:35 +00001340 continue;
1341
Jakob Stoklund Olesen781e0b92012-06-20 23:23:59 +00001342 if (!LiveInts->hasInterval(Reg)) {
1343 report("Missing live interval for virtual register", MF);
1344 *OS << PrintReg(Reg, TRI) << " still has defs or uses\n";
Jakob Stoklund Olesendc5e7062010-10-28 20:44:22 +00001345 continue;
Jakob Stoklund Olesen781e0b92012-06-20 23:23:59 +00001346 }
Jakob Stoklund Olesendc5e7062010-10-28 20:44:22 +00001347
Jakob Stoklund Olesen781e0b92012-06-20 23:23:59 +00001348 const LiveInterval &LI = LiveInts->getInterval(Reg);
1349 assert(Reg == LI.reg && "Invalid reg to interval mapping");
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001350 verifyLiveInterval(LI);
1351 }
Jakob Stoklund Olesen637c4672012-08-02 16:36:50 +00001352
1353 // Verify all the cached regunit intervals.
1354 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
Matthias Braun34e1be92013-10-10 21:29:02 +00001355 if (const LiveRange *LR = LiveInts->getCachedRegUnit(i))
1356 verifyLiveRange(*LR, i);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001357}
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001358
Matthias Braun364e6e92013-10-10 21:28:54 +00001359void MachineVerifier::verifyLiveRangeValue(const LiveRange &LR,
1360 const VNInfo *VNI,
1361 unsigned Reg) {
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001362 if (VNI->isUnused())
1363 return;
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001364
Matthias Braun364e6e92013-10-10 21:28:54 +00001365 const VNInfo *DefVNI = LR.getVNInfoAt(VNI->def);
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001366
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001367 if (!DefVNI) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001368 report("Valno not live at def and not marked unused", MF, LR);
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001369 *OS << "Valno #" << VNI->id << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001370 return;
1371 }
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001372
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001373 if (DefVNI != VNI) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001374 report("Live segment at def has different valno", MF, LR);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001375 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001376 << " where valno #" << DefVNI->id << " is live\n";
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001377 return;
1378 }
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001379
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001380 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
1381 if (!MBB) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001382 report("Invalid definition index", MF, LR);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001383 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
Matthias Braun364e6e92013-10-10 21:28:54 +00001384 << " in " << LR << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001385 return;
1386 }
Jakob Stoklund Olesen0fb303d2010-10-22 22:48:58 +00001387
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001388 if (VNI->isPHIDef()) {
1389 if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001390 report("PHIDef value is not defined at MBB start", MBB, LR);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001391 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001392 << ", not at the beginning of BB#" << MBB->getNumber() << '\n';
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001393 }
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001394 return;
1395 }
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001396
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001397 // Non-PHI def.
1398 const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1399 if (!MI) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001400 report("No instruction at def index", MBB, LR);
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001401 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001402 return;
1403 }
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001404
Matthias Braun364e6e92013-10-10 21:28:54 +00001405 if (Reg != 0) {
1406 bool hasDef = false;
1407 bool isEarlyClobber = false;
1408 for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
1409 if (!MOI->isReg() || !MOI->isDef())
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001410 continue;
Matthias Braun364e6e92013-10-10 21:28:54 +00001411 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1412 if (MOI->getReg() != Reg)
1413 continue;
1414 } else {
1415 if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
1416 !TRI->hasRegUnit(MOI->getReg(), Reg))
1417 continue;
1418 }
1419 hasDef = true;
1420 if (MOI->isEarlyClobber())
1421 isEarlyClobber = true;
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001422 }
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001423
Matthias Braun364e6e92013-10-10 21:28:54 +00001424 if (!hasDef) {
1425 report("Defining instruction does not modify register", MI);
1426 *OS << "Valno #" << VNI->id << " in " << LR << '\n';
1427 }
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001428
Matthias Braun364e6e92013-10-10 21:28:54 +00001429 // Early clobber defs begin at USE slots, but other defs must begin at
1430 // DEF slots.
1431 if (isEarlyClobber) {
1432 if (!VNI->def.isEarlyClobber()) {
1433 report("Early clobber def must be at an early-clobber slot", MBB, LR);
1434 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
1435 }
1436 } else if (!VNI->def.isRegister()) {
1437 report("Non-PHI, non-early clobber def must be at a register slot",
1438 MBB, LR);
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001439 *OS << "Valno #" << VNI->id << " is defined at " << VNI->def << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001440 }
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001441 }
1442}
1443
Matthias Braun364e6e92013-10-10 21:28:54 +00001444void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
1445 const LiveRange::const_iterator I,
1446 unsigned Reg) {
1447 const LiveRange::Segment &S = *I;
1448 const VNInfo *VNI = S.valno;
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001449 assert(VNI && "Live segment has no valno");
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001450
Matthias Braun364e6e92013-10-10 21:28:54 +00001451 if (VNI->id >= LR.getNumValNums() || VNI != LR.getValNumInfo(VNI->id)) {
1452 report("Foreign valno in live segment", MF, LR);
1453 *OS << S << " has a bad valno\n";
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001454 }
1455
1456 if (VNI->isUnused()) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001457 report("Live segment valno is marked unused", MF, LR);
1458 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001459 }
1460
Matthias Braun364e6e92013-10-10 21:28:54 +00001461 const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(S.start);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001462 if (!MBB) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001463 report("Bad start of live segment, no basic block", MF, LR);
1464 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001465 return;
1466 }
1467 SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
Matthias Braun364e6e92013-10-10 21:28:54 +00001468 if (S.start != MBBStartIdx && S.start != VNI->def) {
1469 report("Live segment must begin at MBB entry or valno def", MBB, LR);
1470 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001471 }
1472
1473 const MachineBasicBlock *EndMBB =
Matthias Braun364e6e92013-10-10 21:28:54 +00001474 LiveInts->getMBBFromIndex(S.end.getPrevSlot());
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001475 if (!EndMBB) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001476 report("Bad end of live segment, no basic block", MF, LR);
1477 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001478 return;
1479 }
1480
1481 // No more checks for live-out segments.
Matthias Braun364e6e92013-10-10 21:28:54 +00001482 if (S.end == LiveInts->getMBBEndIdx(EndMBB))
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001483 return;
1484
Jakob Stoklund Olesen637c4672012-08-02 16:36:50 +00001485 // RegUnit intervals are allowed dead phis.
Matthias Braun364e6e92013-10-10 21:28:54 +00001486 if (!TargetRegisterInfo::isVirtualRegister(Reg) && VNI->isPHIDef() &&
1487 S.start == VNI->def && S.end == VNI->def.getDeadSlot())
Jakob Stoklund Olesen637c4672012-08-02 16:36:50 +00001488 return;
1489
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001490 // The live segment is ending inside EndMBB
1491 const MachineInstr *MI =
Matthias Braun364e6e92013-10-10 21:28:54 +00001492 LiveInts->getInstructionFromIndex(S.end.getPrevSlot());
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001493 if (!MI) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001494 report("Live segment doesn't end at a valid instruction", EndMBB, LR);
1495 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001496 return;
1497 }
1498
1499 // The block slot must refer to a basic block boundary.
Matthias Braun364e6e92013-10-10 21:28:54 +00001500 if (S.end.isBlock()) {
1501 report("Live segment ends at B slot of an instruction", EndMBB, LR);
1502 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001503 }
1504
Matthias Braun364e6e92013-10-10 21:28:54 +00001505 if (S.end.isDead()) {
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001506 // Segment ends on the dead slot.
1507 // That means there must be a dead def.
Matthias Braun364e6e92013-10-10 21:28:54 +00001508 if (!SlotIndex::isSameInstr(S.start, S.end)) {
1509 report("Live segment ending at dead slot spans instructions", EndMBB, LR);
1510 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001511 }
1512 }
1513
1514 // A live segment can only end at an early-clobber slot if it is being
1515 // redefined by an early-clobber def.
Matthias Braun364e6e92013-10-10 21:28:54 +00001516 if (S.end.isEarlyClobber()) {
1517 if (I+1 == LR.end() || (I+1)->start != S.end) {
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001518 report("Live segment ending at early clobber slot must be "
Matthias Braun364e6e92013-10-10 21:28:54 +00001519 "redefined by an EC def in the same instruction", EndMBB, LR);
1520 *OS << S << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001521 }
1522 }
1523
1524 // The following checks only apply to virtual registers. Physreg liveness
1525 // is too weird to check.
Matthias Braun364e6e92013-10-10 21:28:54 +00001526 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001527 // A live segment can end with either a redefinition, a kill flag on a
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001528 // use, or a dead flag on a def.
1529 bool hasRead = false;
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001530 for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001531 if (!MOI->isReg() || MOI->getReg() != Reg)
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001532 continue;
1533 if (MOI->readsReg())
1534 hasRead = true;
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001535 }
Pedro Artigas71f87cb2013-11-08 22:46:28 +00001536 if (!S.end.isDead()) {
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001537 if (!hasRead) {
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001538 report("Instruction ending live segment doesn't read the register", MI);
Matthias Braun364e6e92013-10-10 21:28:54 +00001539 *OS << S << " in " << LR << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001540 }
1541 }
1542 }
1543
1544 // Now check all the basic blocks in this live segment.
1545 MachineFunction::const_iterator MFI = MBB;
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001546 // Is this live segment the beginning of a non-PHIDef VN?
Matthias Braun364e6e92013-10-10 21:28:54 +00001547 if (S.start == VNI->def && !VNI->isPHIDef()) {
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001548 // Not live-in to any blocks.
1549 if (MBB == EndMBB)
1550 return;
1551 // Skip this block.
1552 ++MFI;
1553 }
1554 for (;;) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001555 assert(LiveInts->isLiveInToMBB(LR, MFI));
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001556 // We don't know how to track physregs into a landing pad.
Matthias Braun364e6e92013-10-10 21:28:54 +00001557 if (!TargetRegisterInfo::isVirtualRegister(Reg) &&
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001558 MFI->isLandingPad()) {
1559 if (&*MFI == EndMBB)
1560 break;
1561 ++MFI;
1562 continue;
1563 }
1564
1565 // Is VNI a PHI-def in the current block?
1566 bool IsPHI = VNI->isPHIDef() &&
1567 VNI->def == LiveInts->getMBBStartIdx(MFI);
1568
1569 // Check that VNI is live-out of all predecessors.
1570 for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1571 PE = MFI->pred_end(); PI != PE; ++PI) {
1572 SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
Matthias Braun364e6e92013-10-10 21:28:54 +00001573 const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001574
1575 // All predecessors must have a live-out value.
1576 if (!PVNI) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001577 report("Register not marked live out of predecessor", *PI, LR);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001578 *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1579 << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001580 << PEnd << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001581 continue;
1582 }
1583
1584 // Only PHI-defs can take different predecessor values.
1585 if (!IsPHI && PVNI != VNI) {
Matthias Braun364e6e92013-10-10 21:28:54 +00001586 report("Different value live out of predecessor", *PI, LR);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001587 *OS << "Valno #" << PVNI->id << " live out of BB#"
1588 << (*PI)->getNumber() << '@' << PEnd
1589 << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001590 << '@' << LiveInts->getMBBStartIdx(MFI) << '\n';
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001591 }
1592 }
1593 if (&*MFI == EndMBB)
1594 break;
1595 ++MFI;
1596 }
1597}
1598
Matthias Braun364e6e92013-10-10 21:28:54 +00001599void MachineVerifier::verifyLiveRange(const LiveRange &LR, unsigned Reg) {
1600 for (LiveRange::const_vni_iterator I = LR.vni_begin(), E = LR.vni_end();
1601 I != E; ++I)
1602 verifyLiveRangeValue(LR, *I, Reg);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001603
Matthias Braun364e6e92013-10-10 21:28:54 +00001604 for (LiveRange::const_iterator I = LR.begin(), E = LR.end(); I != E; ++I)
1605 verifyLiveRangeSegment(LR, I, Reg);
1606}
1607
1608void MachineVerifier::verifyLiveInterval(const LiveInterval &LI) {
1609 verifyLiveRange(LI, LI.reg);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001610
1611 // Check the LI only has one connected component.
1612 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1613 ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1614 unsigned NumComp = ConEQ.Classify(&LI);
1615 if (NumComp > 1) {
Jakob Stoklund Olesenbde5dc52012-08-02 14:31:49 +00001616 report("Multiple connected components in live interval", MF, LI);
Jakob Stoklund Olesene736b972012-08-02 00:20:20 +00001617 for (unsigned comp = 0; comp != NumComp; ++comp) {
1618 *OS << comp << ": valnos";
1619 for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1620 E = LI.vni_end(); I!=E; ++I)
1621 if (comp == ConEQ.getEqClass(*I))
1622 *OS << ' ' << (*I)->id;
1623 *OS << '\n';
Jakob Stoklund Olesen0e7a0112010-10-27 00:39:01 +00001624 }
Jakob Stoklund Olesen260fa282010-10-26 22:36:07 +00001625 }
Jakob Stoklund Olesen8147d7a2010-08-06 18:04:19 +00001626 }
1627}
Manman Renaa6875b2013-07-15 21:26:31 +00001628
1629namespace {
1630 // FrameSetup and FrameDestroy can have zero adjustment, so using a single
1631 // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
1632 // value is zero.
1633 // We use a bool plus an integer to capture the stack state.
1634 struct StackStateOfBB {
1635 StackStateOfBB() : EntryValue(0), ExitValue(0), EntryIsSetup(false),
1636 ExitIsSetup(false) { }
1637 StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
1638 EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
1639 ExitIsSetup(ExitSetup) { }
1640 // Can be negative, which means we are setting up a frame.
1641 int EntryValue;
1642 int ExitValue;
1643 bool EntryIsSetup;
1644 bool ExitIsSetup;
1645 };
1646}
1647
1648/// Make sure on every path through the CFG, a FrameSetup <n> is always followed
1649/// by a FrameDestroy <n>, stack adjustments are identical on all
1650/// CFG edges to a merge point, and frame is destroyed at end of a return block.
1651void MachineVerifier::verifyStackFrame() {
1652 int FrameSetupOpcode = TII->getCallFrameSetupOpcode();
1653 int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
1654
1655 SmallVector<StackStateOfBB, 8> SPState;
1656 SPState.resize(MF->getNumBlockIDs());
1657 SmallPtrSet<const MachineBasicBlock*, 8> Reachable;
1658
1659 // Visit the MBBs in DFS order.
1660 for (df_ext_iterator<const MachineFunction*,
1661 SmallPtrSet<const MachineBasicBlock*, 8> >
1662 DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
1663 DFI != DFE; ++DFI) {
1664 const MachineBasicBlock *MBB = *DFI;
1665
1666 StackStateOfBB BBState;
1667 // Check the exit state of the DFS stack predecessor.
1668 if (DFI.getPathLength() >= 2) {
1669 const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
1670 assert(Reachable.count(StackPred) &&
1671 "DFS stack predecessor is already visited.\n");
1672 BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
1673 BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
1674 BBState.ExitValue = BBState.EntryValue;
1675 BBState.ExitIsSetup = BBState.EntryIsSetup;
1676 }
1677
1678 // Update stack state by checking contents of MBB.
1679 for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
1680 I != E; ++I) {
1681 if (I->getOpcode() == FrameSetupOpcode) {
1682 // The first operand of a FrameOpcode should be i32.
1683 int Size = I->getOperand(0).getImm();
1684 assert(Size >= 0 &&
1685 "Value should be non-negative in FrameSetup and FrameDestroy.\n");
1686
1687 if (BBState.ExitIsSetup)
1688 report("FrameSetup is after another FrameSetup", I);
1689 BBState.ExitValue -= Size;
1690 BBState.ExitIsSetup = true;
1691 }
1692
1693 if (I->getOpcode() == FrameDestroyOpcode) {
1694 // The first operand of a FrameOpcode should be i32.
1695 int Size = I->getOperand(0).getImm();
1696 assert(Size >= 0 &&
1697 "Value should be non-negative in FrameSetup and FrameDestroy.\n");
1698
1699 if (!BBState.ExitIsSetup)
1700 report("FrameDestroy is not after a FrameSetup", I);
1701 int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
1702 BBState.ExitValue;
1703 if (BBState.ExitIsSetup && AbsSPAdj != Size) {
1704 report("FrameDestroy <n> is after FrameSetup <m>", I);
1705 *OS << "FrameDestroy <" << Size << "> is after FrameSetup <"
1706 << AbsSPAdj << ">.\n";
1707 }
1708 BBState.ExitValue += Size;
1709 BBState.ExitIsSetup = false;
1710 }
1711 }
1712 SPState[MBB->getNumber()] = BBState;
1713
1714 // Make sure the exit state of any predecessor is consistent with the entry
1715 // state.
1716 for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
1717 E = MBB->pred_end(); I != E; ++I) {
1718 if (Reachable.count(*I) &&
1719 (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue ||
1720 SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
1721 report("The exit stack state of a predecessor is inconsistent.", MBB);
1722 *OS << "Predecessor BB#" << (*I)->getNumber() << " has exit state ("
1723 << SPState[(*I)->getNumber()].ExitValue << ", "
1724 << SPState[(*I)->getNumber()].ExitIsSetup
1725 << "), while BB#" << MBB->getNumber() << " has entry state ("
1726 << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
1727 }
1728 }
1729
1730 // Make sure the entry state of any successor is consistent with the exit
1731 // state.
1732 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
1733 E = MBB->succ_end(); I != E; ++I) {
1734 if (Reachable.count(*I) &&
1735 (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue ||
1736 SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
1737 report("The entry stack state of a successor is inconsistent.", MBB);
1738 *OS << "Successor BB#" << (*I)->getNumber() << " has entry state ("
1739 << SPState[(*I)->getNumber()].EntryValue << ", "
1740 << SPState[(*I)->getNumber()].EntryIsSetup
1741 << "), while BB#" << MBB->getNumber() << " has exit state ("
1742 << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
1743 }
1744 }
1745
1746 // Make sure a basic block with return ends with zero stack adjustment.
1747 if (!MBB->empty() && MBB->back().isReturn()) {
1748 if (BBState.ExitIsSetup)
1749 report("A return block ends with a FrameSetup.", MBB);
1750 if (BBState.ExitValue)
1751 report("A return block ends with a nonzero stack adjustment.", MBB);
1752 }
1753 }
1754}