1
//===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// Pass to verify generated machine code. The following is checked:
12
// Operand counts: All explicit operands must be present.
14
// Register classes: All physical and virtual register operands must be
15
// compatible with the register class required by the instruction descriptor.
17
// Register live intervals: Registers must be defined only once, and must be
18
// defined before use.
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
//===----------------------------------------------------------------------===//
26
#include "llvm/Function.h"
27
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
28
#include "llvm/CodeGen/LiveVariables.h"
29
#include "llvm/CodeGen/MachineFunctionPass.h"
30
#include "llvm/CodeGen/MachineFrameInfo.h"
31
#include "llvm/CodeGen/MachineMemOperand.h"
32
#include "llvm/CodeGen/MachineRegisterInfo.h"
33
#include "llvm/CodeGen/Passes.h"
34
#include "llvm/Target/TargetMachine.h"
35
#include "llvm/Target/TargetRegisterInfo.h"
36
#include "llvm/Target/TargetInstrInfo.h"
37
#include "llvm/ADT/DenseSet.h"
38
#include "llvm/ADT/SetOperations.h"
39
#include "llvm/ADT/SmallVector.h"
40
#include "llvm/Support/Debug.h"
41
#include "llvm/Support/ErrorHandling.h"
42
#include "llvm/Support/raw_ostream.h"
46
struct MachineVerifier {
48
MachineVerifier(Pass *pass) :
50
OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
53
bool runOnMachineFunction(MachineFunction &MF);
56
const char *const OutFileName;
58
const MachineFunction *MF;
59
const TargetMachine *TM;
60
const TargetRegisterInfo *TRI;
61
const MachineRegisterInfo *MRI;
65
typedef SmallVector<unsigned, 16> RegVector;
66
typedef DenseSet<unsigned> RegSet;
67
typedef DenseMap<unsigned, const MachineInstr*> RegMap;
69
BitVector regsReserved;
71
RegVector regsDefined, regsDead, regsKilled;
72
RegSet regsLiveInButUnused;
74
// Add Reg and any sub-registers to RV
75
void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
77
if (TargetRegisterInfo::isPhysicalRegister(Reg))
78
for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
83
// Is this MBB reachable from the MF entry point?
86
// Vregs that must be live in because they are used without being
87
// defined. Map value is the user.
90
// Regs killed in MBB. They may be defined again, and will then be in both
91
// regsKilled and regsLiveOut.
94
// Regs defined in MBB and live out. Note that vregs passing through may
95
// be live out without being mentioned here.
98
// Vregs that pass through MBB untouched. This set is disjoint from
99
// regsKilled and regsLiveOut.
102
// Vregs that must pass through MBB because they are needed by a successor
103
// block. This set is disjoint from regsLiveOut.
104
RegSet vregsRequired;
106
BBInfo() : reachable(false) {}
108
// Add register to vregsPassed if it belongs there. Return true if
110
bool addPassed(unsigned Reg) {
111
if (!TargetRegisterInfo::isVirtualRegister(Reg))
113
if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
115
return vregsPassed.insert(Reg).second;
118
// Same for a full set.
119
bool addPassed(const RegSet &RS) {
120
bool changed = false;
121
for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
127
// Add register to vregsRequired if it belongs there. Return true if
129
bool addRequired(unsigned Reg) {
130
if (!TargetRegisterInfo::isVirtualRegister(Reg))
132
if (regsLiveOut.count(Reg))
134
return vregsRequired.insert(Reg).second;
137
// Same for a full set.
138
bool addRequired(const RegSet &RS) {
139
bool changed = false;
140
for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
146
// Same for a full map.
147
bool addRequired(const RegMap &RM) {
148
bool changed = false;
149
for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
150
if (addRequired(I->first))
155
// Live-out registers are either in regsLiveOut or vregsPassed.
156
bool isLiveOut(unsigned Reg) const {
157
return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
161
// Extra register info per MBB.
162
DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
164
bool isReserved(unsigned Reg) {
165
return Reg < regsReserved.size() && regsReserved.test(Reg);
168
// Analysis information if available
169
LiveVariables *LiveVars;
170
const LiveIntervals *LiveInts;
172
void visitMachineFunctionBefore();
173
void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
174
void visitMachineInstrBefore(const MachineInstr *MI);
175
void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
176
void visitMachineInstrAfter(const MachineInstr *MI);
177
void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
178
void visitMachineFunctionAfter();
180
void report(const char *msg, const MachineFunction *MF);
181
void report(const char *msg, const MachineBasicBlock *MBB);
182
void report(const char *msg, const MachineInstr *MI);
183
void report(const char *msg, const MachineOperand *MO, unsigned MONum);
185
void markReachable(const MachineBasicBlock *MBB);
186
void calcRegsPassed();
187
void checkPHIOps(const MachineBasicBlock *MBB);
189
void calcRegsRequired();
190
void verifyLiveVariables();
191
void verifyLiveIntervals();
194
struct MachineVerifierPass : public MachineFunctionPass {
195
static char ID; // Pass ID, replacement for typeid
197
MachineVerifierPass()
198
: MachineFunctionPass(ID) {}
200
void getAnalysisUsage(AnalysisUsage &AU) const {
201
AU.setPreservesAll();
202
MachineFunctionPass::getAnalysisUsage(AU);
205
bool runOnMachineFunction(MachineFunction &MF) {
213
char MachineVerifierPass::ID = 0;
214
INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
215
"Verify generated machine code", false, false);
217
FunctionPass *llvm::createMachineVerifierPass() {
218
return new MachineVerifierPass();
221
void MachineFunction::verify(Pass *p) const {
222
MachineVerifier(p).runOnMachineFunction(const_cast<MachineFunction&>(*this));
225
bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
226
raw_ostream *OutFile = 0;
228
std::string ErrorInfo;
229
OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
230
raw_fd_ostream::F_Append);
231
if (!ErrorInfo.empty()) {
232
errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
244
TM = &MF.getTarget();
245
TRI = TM->getRegisterInfo();
246
MRI = &MF.getRegInfo();
251
LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
252
// We don't want to verify LiveVariables if LiveIntervals is available.
254
LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
257
visitMachineFunctionBefore();
258
for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
260
visitMachineBasicBlockBefore(MFI);
261
for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
262
MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
263
visitMachineInstrBefore(MBBI);
264
for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
265
visitMachineOperand(&MBBI->getOperand(I), I);
266
visitMachineInstrAfter(MBBI);
268
visitMachineBasicBlockAfter(MFI);
270
visitMachineFunctionAfter();
274
else if (foundErrors)
275
report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
282
regsLiveInButUnused.clear();
285
return false; // no changes
288
void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
293
*OS << "*** Bad machine code: " << msg << " ***\n"
294
<< "- function: " << MF->getFunction()->getNameStr() << "\n";
297
void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
299
report(msg, MBB->getParent());
300
*OS << "- basic block: " << MBB->getName()
302
<< " (BB#" << MBB->getNumber() << ")\n";
305
void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
307
report(msg, MI->getParent());
308
*OS << "- instruction: ";
312
void MachineVerifier::report(const char *msg,
313
const MachineOperand *MO, unsigned MONum) {
315
report(msg, MO->getParent());
316
*OS << "- operand " << MONum << ": ";
321
void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
322
BBInfo &MInfo = MBBInfoMap[MBB];
323
if (!MInfo.reachable) {
324
MInfo.reachable = true;
325
for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
326
SuE = MBB->succ_end(); SuI != SuE; ++SuI)
331
void MachineVerifier::visitMachineFunctionBefore() {
332
regsReserved = TRI->getReservedRegs(*MF);
334
// A sub-register of a reserved register is also reserved
335
for (int Reg = regsReserved.find_first(); Reg>=0;
336
Reg = regsReserved.find_next(Reg)) {
337
for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
338
// FIXME: This should probably be:
339
// assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
340
regsReserved.set(*Sub);
343
markReachable(&MF->front());
346
// Does iterator point to a and b as the first two elements?
347
static bool matchPair(MachineBasicBlock::const_succ_iterator i,
348
const MachineBasicBlock *a, const MachineBasicBlock *b) {
357
MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
358
const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
360
// Call AnalyzeBranch. If it succeeds, there several more conditions to check.
361
MachineBasicBlock *TBB = 0, *FBB = 0;
362
SmallVector<MachineOperand, 4> Cond;
363
if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
365
// Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
366
// check whether its answers match up with reality.
368
// Block falls through to its successor.
369
MachineFunction::const_iterator MBBI = MBB;
371
if (MBBI == MF->end()) {
372
// It's possible that the block legitimately ends with a noreturn
373
// call or an unreachable, in which case it won't actually fall
374
// out the bottom of the function.
375
} else if (MBB->succ_empty()) {
376
// It's possible that the block legitimately ends with a noreturn
377
// call or an unreachable, in which case it won't actuall fall
379
} else if (MBB->succ_size() != 1) {
380
report("MBB exits via unconditional fall-through but doesn't have "
381
"exactly one CFG successor!", MBB);
382
} else if (MBB->succ_begin()[0] != MBBI) {
383
report("MBB exits via unconditional fall-through but its successor "
384
"differs from its CFG successor!", MBB);
386
if (!MBB->empty() && MBB->back().getDesc().isBarrier() &&
387
!TII->isPredicated(&MBB->back())) {
388
report("MBB exits via unconditional fall-through but ends with a "
389
"barrier instruction!", MBB);
392
report("MBB exits via unconditional fall-through but has a condition!",
395
} else if (TBB && !FBB && Cond.empty()) {
396
// Block unconditionally branches somewhere.
397
if (MBB->succ_size() != 1) {
398
report("MBB exits via unconditional branch but doesn't have "
399
"exactly one CFG successor!", MBB);
400
} else if (MBB->succ_begin()[0] != TBB) {
401
report("MBB exits via unconditional branch but the CFG "
402
"successor doesn't match the actual successor!", MBB);
405
report("MBB exits via unconditional branch but doesn't contain "
406
"any instructions!", MBB);
407
} else if (!MBB->back().getDesc().isBarrier()) {
408
report("MBB exits via unconditional branch but doesn't end with a "
409
"barrier instruction!", MBB);
410
} else if (!MBB->back().getDesc().isTerminator()) {
411
report("MBB exits via unconditional branch but the branch isn't a "
412
"terminator instruction!", MBB);
414
} else if (TBB && !FBB && !Cond.empty()) {
415
// Block conditionally branches somewhere, otherwise falls through.
416
MachineFunction::const_iterator MBBI = MBB;
418
if (MBBI == MF->end()) {
419
report("MBB conditionally falls through out of function!", MBB);
420
} if (MBB->succ_size() != 2) {
421
report("MBB exits via conditional branch/fall-through but doesn't have "
422
"exactly two CFG successors!", MBB);
423
} else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
424
report("MBB exits via conditional branch/fall-through but the CFG "
425
"successors don't match the actual successors!", MBB);
428
report("MBB exits via conditional branch/fall-through but doesn't "
429
"contain any instructions!", MBB);
430
} else if (MBB->back().getDesc().isBarrier()) {
431
report("MBB exits via conditional branch/fall-through but ends with a "
432
"barrier instruction!", MBB);
433
} else if (!MBB->back().getDesc().isTerminator()) {
434
report("MBB exits via conditional branch/fall-through but the branch "
435
"isn't a terminator instruction!", MBB);
437
} else if (TBB && FBB) {
438
// Block conditionally branches somewhere, otherwise branches
440
if (MBB->succ_size() != 2) {
441
report("MBB exits via conditional branch/branch but doesn't have "
442
"exactly two CFG successors!", MBB);
443
} else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
444
report("MBB exits via conditional branch/branch but the CFG "
445
"successors don't match the actual successors!", MBB);
448
report("MBB exits via conditional branch/branch but doesn't "
449
"contain any instructions!", MBB);
450
} else if (!MBB->back().getDesc().isBarrier()) {
451
report("MBB exits via conditional branch/branch but doesn't end with a "
452
"barrier instruction!", MBB);
453
} else if (!MBB->back().getDesc().isTerminator()) {
454
report("MBB exits via conditional branch/branch but the branch "
455
"isn't a terminator instruction!", MBB);
458
report("MBB exits via conditinal branch/branch but there's no "
462
report("AnalyzeBranch returned invalid data!", MBB);
467
for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
468
E = MBB->livein_end(); I != E; ++I) {
469
if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
470
report("MBB live-in list contains non-physical register", MBB);
474
for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
477
regsLiveInButUnused = regsLive;
479
const MachineFrameInfo *MFI = MF->getFrameInfo();
480
assert(MFI && "Function has no frame info");
481
BitVector PR = MFI->getPristineRegs(MBB);
482
for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
484
for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
492
void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
493
const TargetInstrDesc &TI = MI->getDesc();
494
if (MI->getNumOperands() < TI.getNumOperands()) {
495
report("Too few operands", MI);
496
*OS << TI.getNumOperands() << " operands expected, but "
497
<< MI->getNumExplicitOperands() << " given.\n";
500
// Check the MachineMemOperands for basic consistency.
501
for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
502
E = MI->memoperands_end(); I != E; ++I) {
503
if ((*I)->isLoad() && !TI.mayLoad())
504
report("Missing mayLoad flag", MI);
505
if ((*I)->isStore() && !TI.mayStore())
506
report("Missing mayStore flag", MI);
509
// Debug values must not have a slot index.
510
// Other instructions must have one.
512
bool mapped = !LiveInts->isNotInMIMap(MI);
513
if (MI->isDebugValue()) {
515
report("Debug instruction has a slot index", MI);
518
report("Missing slot index", MI);
525
MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
526
const MachineInstr *MI = MO->getParent();
527
const TargetInstrDesc &TI = MI->getDesc();
529
// The first TI.NumDefs operands must be explicit register defines
530
if (MONum < TI.getNumDefs()) {
532
report("Explicit definition must be a register", MO, MONum);
533
else if (!MO->isDef())
534
report("Explicit definition marked as use", MO, MONum);
535
else if (MO->isImplicit())
536
report("Explicit definition marked as implicit", MO, MONum);
537
} else if (MONum < TI.getNumOperands()) {
540
report("Explicit operand marked as def", MO, MONum);
541
if (MO->isImplicit())
542
report("Explicit operand marked as implicit", MO, MONum);
545
// ARM adds %reg0 operands to indicate predicates. We'll allow that.
546
if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic() && MO->getReg())
547
report("Extra explicit operand on non-variadic instruction", MO, MONum);
550
switch (MO->getType()) {
551
case MachineOperand::MO_Register: {
552
const unsigned Reg = MO->getReg();
556
// Check Live Variables.
558
// An <undef> doesn't refer to any register, so just skip it.
559
} else if (MO->isUse()) {
560
regsLiveInButUnused.erase(Reg);
564
if (MI->isRegTiedToDefOperand(MONum, &defIdx)) {
565
// A two-addr use counts as a kill if use and def are the same.
566
unsigned DefReg = MI->getOperand(defIdx).getReg();
569
// ANd in that case an explicit kill flag is not allowed.
571
report("Illegal kill flag on two-address instruction operand",
573
} else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
574
report("Two-address instruction operands must be identical",
578
isKill = MO->isKill();
581
addRegWithSubRegs(regsKilled, Reg);
583
// Check that LiveVars knows this kill.
584
if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
586
LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
587
if (std::find(VI.Kills.begin(),
588
VI.Kills.end(), MI) == VI.Kills.end())
589
report("Kill missing from LiveVariables", MO, MONum);
592
// Check LiveInts liveness and kill.
593
if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
594
SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getUseIndex();
595
if (LiveInts->hasInterval(Reg)) {
596
const LiveInterval &LI = LiveInts->getInterval(Reg);
597
if (!LI.liveAt(UseIdx)) {
598
report("No live range at use", MO, MONum);
599
*OS << UseIdx << " is not live in " << LI << '\n';
601
// TODO: Verify isKill == LI.killedAt.
602
} else if (TargetRegisterInfo::isVirtualRegister(Reg)) {
603
report("Virtual register has no Live interval", MO, MONum);
607
// Use of a dead register.
608
if (!regsLive.count(Reg)) {
609
if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
610
// Reserved registers may be used even when 'dead'.
611
if (!isReserved(Reg))
612
report("Using an undefined physical register", MO, MONum);
614
BBInfo &MInfo = MBBInfoMap[MI->getParent()];
615
// We don't know which virtual registers are live in, so only complain
616
// if vreg was killed in this MBB. Otherwise keep track of vregs that
617
// must be live in. PHI instructions are handled separately.
618
if (MInfo.regsKilled.count(Reg))
619
report("Using a killed virtual register", MO, MONum);
620
else if (!MI->isPHI())
621
MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
627
// TODO: verify that earlyclobber ops are not used.
629
addRegWithSubRegs(regsDead, Reg);
631
addRegWithSubRegs(regsDefined, Reg);
633
// Check LiveInts for a live range, but only for virtual registers.
634
if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
635
!LiveInts->isNotInMIMap(MI)) {
636
SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getDefIndex();
637
if (LiveInts->hasInterval(Reg)) {
638
const LiveInterval &LI = LiveInts->getInterval(Reg);
639
if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) {
640
assert(LR->valno && "NULL valno is not allowed");
641
if (LR->valno->def != DefIdx) {
642
report("Inconsistent valno->def", MO, MONum);
643
*OS << "Valno " << LR->valno->id << " is not defined at "
644
<< DefIdx << " in " << LI << '\n';
647
report("No live range at def", MO, MONum);
648
*OS << DefIdx << " is not live in " << LI << '\n';
651
report("Virtual register has no Live interval", MO, MONum);
656
// Check register classes.
657
if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
658
const TargetOperandInfo &TOI = TI.OpInfo[MONum];
659
unsigned SubIdx = MO->getSubReg();
661
if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
664
unsigned s = TRI->getSubReg(Reg, SubIdx);
666
report("Invalid subregister index for physical register",
672
if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
673
if (!DRC->contains(sr)) {
674
report("Illegal physical register for instruction", MO, MONum);
675
*OS << TRI->getName(sr) << " is not a "
676
<< DRC->getName() << " register.\n";
681
const TargetRegisterClass *RC = MRI->getRegClass(Reg);
683
const TargetRegisterClass *SRC = RC->getSubRegisterRegClass(SubIdx);
685
report("Invalid subregister index for virtual register", MO, MONum);
686
*OS << "Register class " << RC->getName()
687
<< " does not support subreg index " << SubIdx << "\n";
692
if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
693
if (RC != DRC && !RC->hasSuperClass(DRC)) {
694
report("Illegal virtual register for instruction", MO, MONum);
695
*OS << "Expected a " << DRC->getName() << " register, but got a "
696
<< RC->getName() << " register\n";
704
case MachineOperand::MO_MachineBasicBlock:
705
if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
706
report("PHI operand is not in the CFG", MO, MONum);
714
void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
715
BBInfo &MInfo = MBBInfoMap[MI->getParent()];
716
set_union(MInfo.regsKilled, regsKilled);
717
set_subtract(regsLive, regsKilled); regsKilled.clear();
718
set_subtract(regsLive, regsDead); regsDead.clear();
719
set_union(regsLive, regsDefined); regsDefined.clear();
723
MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
724
MBBInfoMap[MBB].regsLiveOut = regsLive;
728
// Calculate the largest possible vregsPassed sets. These are the registers that
729
// can pass through an MBB live, but may not be live every time. It is assumed
730
// that all vregsPassed sets are empty before the call.
731
void MachineVerifier::calcRegsPassed() {
732
// First push live-out regs to successors' vregsPassed. Remember the MBBs that
733
// have any vregsPassed.
734
DenseSet<const MachineBasicBlock*> todo;
735
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
737
const MachineBasicBlock &MBB(*MFI);
738
BBInfo &MInfo = MBBInfoMap[&MBB];
739
if (!MInfo.reachable)
741
for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
742
SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
743
BBInfo &SInfo = MBBInfoMap[*SuI];
744
if (SInfo.addPassed(MInfo.regsLiveOut))
749
// Iteratively push vregsPassed to successors. This will converge to the same
750
// final state regardless of DenseSet iteration order.
751
while (!todo.empty()) {
752
const MachineBasicBlock *MBB = *todo.begin();
754
BBInfo &MInfo = MBBInfoMap[MBB];
755
for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
756
SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
759
BBInfo &SInfo = MBBInfoMap[*SuI];
760
if (SInfo.addPassed(MInfo.vregsPassed))
766
// Calculate the set of virtual registers that must be passed through each basic
767
// block in order to satisfy the requirements of successor blocks. This is very
768
// similar to calcRegsPassed, only backwards.
769
void MachineVerifier::calcRegsRequired() {
770
// First push live-in regs to predecessors' vregsRequired.
771
DenseSet<const MachineBasicBlock*> todo;
772
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
774
const MachineBasicBlock &MBB(*MFI);
775
BBInfo &MInfo = MBBInfoMap[&MBB];
776
for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
777
PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
778
BBInfo &PInfo = MBBInfoMap[*PrI];
779
if (PInfo.addRequired(MInfo.vregsLiveIn))
784
// Iteratively push vregsRequired to predecessors. This will converge to the
785
// same final state regardless of DenseSet iteration order.
786
while (!todo.empty()) {
787
const MachineBasicBlock *MBB = *todo.begin();
789
BBInfo &MInfo = MBBInfoMap[MBB];
790
for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
791
PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
794
BBInfo &SInfo = MBBInfoMap[*PrI];
795
if (SInfo.addRequired(MInfo.vregsRequired))
801
// Check PHI instructions at the beginning of MBB. It is assumed that
802
// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
803
void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
804
for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
805
BBI != BBE && BBI->isPHI(); ++BBI) {
806
DenseSet<const MachineBasicBlock*> seen;
808
for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
809
unsigned Reg = BBI->getOperand(i).getReg();
810
const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
811
if (!Pre->isSuccessor(MBB))
814
BBInfo &PrInfo = MBBInfoMap[Pre];
815
if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
816
report("PHI operand is not live-out from predecessor",
817
&BBI->getOperand(i), i);
820
// Did we see all predecessors?
821
for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
822
PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
823
if (!seen.count(*PrI)) {
824
report("Missing PHI operand", BBI);
825
*OS << "BB#" << (*PrI)->getNumber()
826
<< " is a predecessor according to the CFG.\n";
832
void MachineVerifier::visitMachineFunctionAfter() {
835
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
837
BBInfo &MInfo = MBBInfoMap[MFI];
839
// Skip unreachable MBBs.
840
if (!MInfo.reachable)
846
// Now check liveness info if available
847
if (LiveVars || LiveInts)
850
verifyLiveVariables();
852
verifyLiveIntervals();
855
void MachineVerifier::verifyLiveVariables() {
856
assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
857
for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
858
RegE = MRI->getLastVirtReg()-1; Reg != RegE; ++Reg) {
859
LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
860
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
862
BBInfo &MInfo = MBBInfoMap[MFI];
864
// Our vregsRequired should be identical to LiveVariables' AliveBlocks
865
if (MInfo.vregsRequired.count(Reg)) {
866
if (!VI.AliveBlocks.test(MFI->getNumber())) {
867
report("LiveVariables: Block missing from AliveBlocks", MFI);
868
*OS << "Virtual register %reg" << Reg
869
<< " must be live through the block.\n";
872
if (VI.AliveBlocks.test(MFI->getNumber())) {
873
report("LiveVariables: Block should not be in AliveBlocks", MFI);
874
*OS << "Virtual register %reg" << Reg
875
<< " is not needed live through the block.\n";
882
void MachineVerifier::verifyLiveIntervals() {
883
assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
884
for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
885
LVE = LiveInts->end(); LVI != LVE; ++LVI) {
886
const LiveInterval &LI = *LVI->second;
887
assert(LVI->first == LI.reg && "Invalid reg to interval mapping");
889
for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
892
const LiveRange *DefLR = LI.getLiveRangeContaining(VNI->def);
895
if (!VNI->isUnused()) {
896
report("Valno not live at def and not marked unused", MF);
897
*OS << "Valno #" << VNI->id << " in " << LI << '\n';
905
if (DefLR->valno != VNI) {
906
report("Live range at def has different valno", MF);
908
*OS << " should use valno #" << VNI->id << " in " << LI << '\n';
913
for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
914
const LiveRange &LR = *I;
915
assert(LR.valno && "Live range has no valno");
917
if (LR.valno->id >= LI.getNumValNums() ||
918
LR.valno != LI.getValNumInfo(LR.valno->id)) {
919
report("Foreign valno in live range", MF);
921
*OS << " has a valno not in " << LI << '\n';
924
if (LR.valno->isUnused()) {
925
report("Live range valno is marked unused", MF);
927
*OS << " in " << LI << '\n';