Deleted Added
sdiff udiff text old ( 199481 ) new ( 199511 )
full compact
MachineVerifier.cpp (199481) MachineVerifier.cpp (199511)
1//===-- MachineVerifier.cpp - Machine Code Verifier -------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 28 unchanged lines hidden (view full) ---

37#include "llvm/ADT/SetOperations.h"
38#include "llvm/ADT/SmallVector.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/ErrorHandling.h"
41#include "llvm/Support/raw_ostream.h"
42using namespace llvm;
43
44namespace {
1//===-- MachineVerifier.cpp - Machine Code Verifier -------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 28 unchanged lines hidden (view full) ---

37#include "llvm/ADT/SetOperations.h"
38#include "llvm/ADT/SmallVector.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/ErrorHandling.h"
41#include "llvm/Support/raw_ostream.h"
42using namespace llvm;
43
44namespace {
45 struct MachineVerifier : public MachineFunctionPass {
46 static char ID; // Pass ID, replacement for typeid
45 struct MachineVerifier {
47
46
48 MachineVerifier(bool allowDoubleDefs = false) :
49 MachineFunctionPass(&ID),
47 MachineVerifier(Pass *pass, bool allowDoubleDefs) :
48 PASS(pass),
50 allowVirtDoubleDefs(allowDoubleDefs),
51 allowPhysDoubleDefs(allowDoubleDefs),
52 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
49 allowVirtDoubleDefs(allowDoubleDefs),
50 allowPhysDoubleDefs(allowDoubleDefs),
51 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
53 {}
52 {}
54
53
55 void getAnalysisUsage(AnalysisUsage &AU) const {
56 AU.setPreservesAll();
57 MachineFunctionPass::getAnalysisUsage(AU);
58 }
59
60 bool runOnMachineFunction(MachineFunction &MF);
61
54 bool runOnMachineFunction(MachineFunction &MF);
55
56 Pass *const PASS;
62 const bool allowVirtDoubleDefs;
63 const bool allowPhysDoubleDefs;
64
65 const char *const OutFileName;
66 raw_ostream *OS;
67 const MachineFunction *MF;
68 const TargetMachine *TM;
69 const TargetRegisterInfo *TRI;

--- 37 unchanged lines hidden (view full) ---

107 // Regs defined in MBB and live out. Note that vregs passing through may
108 // be live out without being mentioned here.
109 RegSet regsLiveOut;
110
111 // Vregs that pass through MBB untouched. This set is disjoint from
112 // regsKilled and regsLiveOut.
113 RegSet vregsPassed;
114
57 const bool allowVirtDoubleDefs;
58 const bool allowPhysDoubleDefs;
59
60 const char *const OutFileName;
61 raw_ostream *OS;
62 const MachineFunction *MF;
63 const TargetMachine *TM;
64 const TargetRegisterInfo *TRI;

--- 37 unchanged lines hidden (view full) ---

102 // Regs defined in MBB and live out. Note that vregs passing through may
103 // be live out without being mentioned here.
104 RegSet regsLiveOut;
105
106 // Vregs that pass through MBB untouched. This set is disjoint from
107 // regsKilled and regsLiveOut.
108 RegSet vregsPassed;
109
110 // Vregs that must pass through MBB because they are needed by a successor
111 // block. This set is disjoint from regsLiveOut.
112 RegSet vregsRequired;
113
115 BBInfo() : reachable(false) {}
116
117 // Add register to vregsPassed if it belongs there. Return true if
118 // anything changed.
119 bool addPassed(unsigned Reg) {
120 if (!TargetRegisterInfo::isVirtualRegister(Reg))
121 return false;
122 if (regsKilled.count(Reg) || regsLiveOut.count(Reg))

--- 5 unchanged lines hidden (view full) ---

128 bool addPassed(const RegSet &RS) {
129 bool changed = false;
130 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
131 if (addPassed(*I))
132 changed = true;
133 return changed;
134 }
135
114 BBInfo() : reachable(false) {}
115
116 // Add register to vregsPassed if it belongs there. Return true if
117 // anything changed.
118 bool addPassed(unsigned Reg) {
119 if (!TargetRegisterInfo::isVirtualRegister(Reg))
120 return false;
121 if (regsKilled.count(Reg) || regsLiveOut.count(Reg))

--- 5 unchanged lines hidden (view full) ---

127 bool addPassed(const RegSet &RS) {
128 bool changed = false;
129 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
130 if (addPassed(*I))
131 changed = true;
132 return changed;
133 }
134
135 // Add register to vregsRequired if it belongs there. Return true if
136 // anything changed.
137 bool addRequired(unsigned Reg) {
138 if (!TargetRegisterInfo::isVirtualRegister(Reg))
139 return false;
140 if (regsLiveOut.count(Reg))
141 return false;
142 return vregsRequired.insert(Reg).second;
143 }
144
145 // Same for a full set.
146 bool addRequired(const RegSet &RS) {
147 bool changed = false;
148 for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
149 if (addRequired(*I))
150 changed = true;
151 return changed;
152 }
153
154 // Same for a full map.
155 bool addRequired(const RegMap &RM) {
156 bool changed = false;
157 for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
158 if (addRequired(I->first))
159 changed = true;
160 return changed;
161 }
162
136 // Live-out registers are either in regsLiveOut or vregsPassed.
137 bool isLiveOut(unsigned Reg) const {
138 return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
139 }
140 };
141
142 // Extra register info per MBB.
143 DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
144
145 bool isReserved(unsigned Reg) {
146 return Reg < regsReserved.size() && regsReserved.test(Reg);
147 }
148
163 // Live-out registers are either in regsLiveOut or vregsPassed.
164 bool isLiveOut(unsigned Reg) const {
165 return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
166 }
167 };
168
169 // Extra register info per MBB.
170 DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
171
172 bool isReserved(unsigned Reg) {
173 return Reg < regsReserved.size() && regsReserved.test(Reg);
174 }
175
176 // Analysis information if available
177 LiveVariables *LiveVars;
178
149 void visitMachineFunctionBefore();
150 void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
151 void visitMachineInstrBefore(const MachineInstr *MI);
152 void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
153 void visitMachineInstrAfter(const MachineInstr *MI);
154 void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
155 void visitMachineFunctionAfter();
156
157 void report(const char *msg, const MachineFunction *MF);
158 void report(const char *msg, const MachineBasicBlock *MBB);
159 void report(const char *msg, const MachineInstr *MI);
160 void report(const char *msg, const MachineOperand *MO, unsigned MONum);
161
162 void markReachable(const MachineBasicBlock *MBB);
163 void calcMaxRegsPassed();
164 void calcMinRegsPassed();
165 void checkPHIOps(const MachineBasicBlock *MBB);
179 void visitMachineFunctionBefore();
180 void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
181 void visitMachineInstrBefore(const MachineInstr *MI);
182 void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
183 void visitMachineInstrAfter(const MachineInstr *MI);
184 void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
185 void visitMachineFunctionAfter();
186
187 void report(const char *msg, const MachineFunction *MF);
188 void report(const char *msg, const MachineBasicBlock *MBB);
189 void report(const char *msg, const MachineInstr *MI);
190 void report(const char *msg, const MachineOperand *MO, unsigned MONum);
191
192 void markReachable(const MachineBasicBlock *MBB);
193 void calcMaxRegsPassed();
194 void calcMinRegsPassed();
195 void checkPHIOps(const MachineBasicBlock *MBB);
196
197 void calcRegsRequired();
198 void verifyLiveVariables();
166 };
199 };
200
201 struct MachineVerifierPass : public MachineFunctionPass {
202 static char ID; // Pass ID, replacement for typeid
203 bool AllowDoubleDefs;
204
205 explicit MachineVerifierPass(bool allowDoubleDefs = false)
206 : MachineFunctionPass(&ID),
207 AllowDoubleDefs(allowDoubleDefs) {}
208
209 void getAnalysisUsage(AnalysisUsage &AU) const {
210 AU.setPreservesAll();
211 MachineFunctionPass::getAnalysisUsage(AU);
212 }
213
214 bool runOnMachineFunction(MachineFunction &MF) {
215 MF.verify(this, AllowDoubleDefs);
216 return false;
217 }
218 };
219
167}
168
220}
221
169char MachineVerifier::ID = 0;
170static RegisterPass
222char MachineVerifierPass::ID = 0;
223static RegisterPass<MachineVerifierPass>
171MachineVer("machineverifier", "Verify generated machine code");
172static const PassInfo *const MachineVerifyID = &MachineVer;
173
174FunctionPass *llvm::createMachineVerifierPass(bool allowPhysDoubleDefs) {
224MachineVer("machineverifier", "Verify generated machine code");
225static const PassInfo *const MachineVerifyID = &MachineVer;
226
227FunctionPass *llvm::createMachineVerifierPass(bool allowPhysDoubleDefs) {
175 return new MachineVerifier(allowPhysDoubleDefs);
228 return new MachineVerifierPass(allowPhysDoubleDefs);
176}
177
229}
230
178void MachineFunction::verify() const {
179 MachineVerifier().runOnMachineFunction(const_cast<MachineFunction&>(*this));
231void MachineFunction::verify(Pass *p, bool allowDoubleDefs) const {
232 MachineVerifier(p, allowDoubleDefs)
233 .runOnMachineFunction(const_cast<MachineFunction&>(*this));
180}
181
182bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
183 raw_ostream *OutFile = 0;
184 if (OutFileName) {
185 std::string ErrorInfo;
186 OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
187 raw_fd_ostream::F_Append);

--- 9 unchanged lines hidden (view full) ---

197
198 foundErrors = 0;
199
200 this->MF = &MF;
201 TM = &MF.getTarget();
202 TRI = TM->getRegisterInfo();
203 MRI = &MF.getRegInfo();
204
234}
235
236bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
237 raw_ostream *OutFile = 0;
238 if (OutFileName) {
239 std::string ErrorInfo;
240 OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
241 raw_fd_ostream::F_Append);

--- 9 unchanged lines hidden (view full) ---

251
252 foundErrors = 0;
253
254 this->MF = &MF;
255 TM = &MF.getTarget();
256 TRI = TM->getRegisterInfo();
257 MRI = &MF.getRegInfo();
258
259 if (PASS) {
260 LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
261 } else {
262 LiveVars = NULL;
263 }
264
205 visitMachineFunctionBefore();
206 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
207 MFI!=MFE; ++MFI) {
208 visitMachineBasicBlockBefore(MFI);
209 for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
210 MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
211 visitMachineInstrBefore(MBBI);
212 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)

--- 300 unchanged lines hidden (view full) ---

513 return;
514
515 // Check Live Variables.
516 if (MO->isUndef()) {
517 // An <undef> doesn't refer to any register, so just skip it.
518 } else if (MO->isUse()) {
519 regsLiveInButUnused.erase(Reg);
520
265 visitMachineFunctionBefore();
266 for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
267 MFI!=MFE; ++MFI) {
268 visitMachineBasicBlockBefore(MFI);
269 for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
270 MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
271 visitMachineInstrBefore(MBBI);
272 for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)

--- 300 unchanged lines hidden (view full) ---

573 return;
574
575 // Check Live Variables.
576 if (MO->isUndef()) {
577 // An <undef> doesn't refer to any register, so just skip it.
578 } else if (MO->isUse()) {
579 regsLiveInButUnused.erase(Reg);
580
581 bool isKill = false;
521 if (MO->isKill()) {
582 if (MO->isKill()) {
522 addRegWithSubRegs(regsKilled, Reg);
583 isKill = true;
523 // Tied operands on two-address instuctions MUST NOT have a <kill> flag.
524 if (MI->isRegTiedToDefOperand(MONum))
525 report("Illegal kill flag on two-address instruction operand",
526 MO, MONum);
527 } else {
528 // TwoAddress instr modifying a reg is treated as kill+def.
529 unsigned defIdx;
530 if (MI->isRegTiedToDefOperand(MONum, &defIdx) &&
531 MI->getOperand(defIdx).getReg() == Reg)
584 // Tied operands on two-address instuctions MUST NOT have a <kill> flag.
585 if (MI->isRegTiedToDefOperand(MONum))
586 report("Illegal kill flag on two-address instruction operand",
587 MO, MONum);
588 } else {
589 // TwoAddress instr modifying a reg is treated as kill+def.
590 unsigned defIdx;
591 if (MI->isRegTiedToDefOperand(MONum, &defIdx) &&
592 MI->getOperand(defIdx).getReg() == Reg)
532 addRegWithSubRegs(regsKilled, Reg);
593 isKill = true;
533 }
594 }
595 if (isKill) {
596 addRegWithSubRegs(regsKilled, Reg);
597
598 // Check that LiveVars knows this kill
599 if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg)) {
600 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
601 if (std::find(VI.Kills.begin(),
602 VI.Kills.end(), MI) == VI.Kills.end())
603 report("Kill missing from LiveVariables", MO, MONum);
604 }
605 }
606
534 // Use of a dead register.
535 if (!regsLive.count(Reg)) {
536 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
537 // Reserved registers may be used even when 'dead'.
538 if (!isReserved(Reg))
539 report("Using an undefined physical register", MO, MONum);
540 } else {
541 BBInfo &MInfo = MBBInfoMap[MI->getParent()];

--- 187 unchanged lines hidden (view full) ---

729 // If any regs removed, we need to recheck successors.
730 if (!dead.empty()) {
731 set_subtract(MInfo.vregsPassed, dead);
732 todo.insert(MBB->succ_begin(), MBB->succ_end());
733 }
734 }
735}
736
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);
613 } else {
614 BBInfo &MInfo = MBBInfoMap[MI->getParent()];

--- 187 unchanged lines hidden (view full) ---

802 // If any regs removed, we need to recheck successors.
803 if (!dead.empty()) {
804 set_subtract(MInfo.vregsPassed, dead);
805 todo.insert(MBB->succ_begin(), MBB->succ_end());
806 }
807 }
808}
809
810// Calculate the set of virtual registers that must be passed through each basic
811// block in order to satisfy the requirements of successor blocks. This is very
812// similar to calcMaxRegsPassed, only backwards.
813void MachineVerifier::calcRegsRequired() {
814 // First push live-in regs to predecessors' vregsRequired.
815 DenseSet<const MachineBasicBlock*> todo;
816 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
817 MFI != MFE; ++MFI) {
818 const MachineBasicBlock &MBB(*MFI);
819 BBInfo &MInfo = MBBInfoMap[&MBB];
820 for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
821 PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
822 BBInfo &PInfo = MBBInfoMap[*PrI];
823 if (PInfo.addRequired(MInfo.vregsLiveIn))
824 todo.insert(*PrI);
825 }
826 }
827
828 // Iteratively push vregsRequired to predecessors. This will converge to the
829 // same final state regardless of DenseSet iteration order.
830 while (!todo.empty()) {
831 const MachineBasicBlock *MBB = *todo.begin();
832 todo.erase(MBB);
833 BBInfo &MInfo = MBBInfoMap[MBB];
834 for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
835 PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
836 if (*PrI == MBB)
837 continue;
838 BBInfo &SInfo = MBBInfoMap[*PrI];
839 if (SInfo.addRequired(MInfo.vregsRequired))
840 todo.insert(*PrI);
841 }
842 }
843}
844
737// Check PHI instructions at the beginning of MBB. It is assumed that
738// calcMinRegsPassed has been run so BBInfo::isLiveOut is valid.
739void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
740 for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
741 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
742 DenseSet<const MachineBasicBlock*> seen;
743
744 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {

--- 99 unchanged lines hidden (view full) ---

844 *OS << "Register %reg" << I->first
845 << " is not live-out from predecessor MBB #"
846 << (*PrI)->getNumber()
847 << ".\n";
848 }
849 }
850 }
851 }
845// Check PHI instructions at the beginning of MBB. It is assumed that
846// calcMinRegsPassed has been run so BBInfo::isLiveOut is valid.
847void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
848 for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
849 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
850 DenseSet<const MachineBasicBlock*> seen;
851
852 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {

--- 99 unchanged lines hidden (view full) ---

952 *OS << "Register %reg" << I->first
953 << " is not live-out from predecessor MBB #"
954 << (*PrI)->getNumber()
955 << ".\n";
956 }
957 }
958 }
959 }
960
961 // Now check LiveVariables info if available
962 if (LiveVars) {
963 calcRegsRequired();
964 verifyLiveVariables();
965 }
852}
966}
967
968void MachineVerifier::verifyLiveVariables() {
969 assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
970 for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
971 RegE = MRI->getLastVirtReg()-1; Reg != RegE; ++Reg) {
972 LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
973 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
974 MFI != MFE; ++MFI) {
975 BBInfo &MInfo = MBBInfoMap[MFI];
976
977 // Our vregsRequired should be identical to LiveVariables' AliveBlocks
978 if (MInfo.vregsRequired.count(Reg)) {
979 if (!VI.AliveBlocks.test(MFI->getNumber())) {
980 report("LiveVariables: Block missing from AliveBlocks", MFI);
981 *OS << "Virtual register %reg" << Reg
982 << " must be live through the block.\n";
983 }
984 } else {
985 if (VI.AliveBlocks.test(MFI->getNumber())) {
986 report("LiveVariables: Block should not be in AliveBlocks", MFI);
987 *OS << "Virtual register %reg" << Reg
988 << " is not needed live through the block.\n";
989 }
990 }
991 }
992 }
993}
994
995