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 { |
46 |
47 MachineVerifier(Pass *pass, bool allowDoubleDefs) : 48 PASS(pass), |
49 allowVirtDoubleDefs(allowDoubleDefs), 50 allowPhysDoubleDefs(allowDoubleDefs), 51 OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS")) |
52 {} |
53 |
54 bool runOnMachineFunction(MachineFunction &MF); 55 |
56 Pass *const PASS; |
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 |
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 |
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 |
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(); |
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 |
220} 221 |
222char MachineVerifierPass::ID = 0; 223static RegisterPass<MachineVerifierPass> |
224MachineVer("machineverifier", "Verify generated machine code"); 225static const PassInfo *const MachineVerifyID = &MachineVer; 226 227FunctionPass *llvm::createMachineVerifierPass(bool allowPhysDoubleDefs) { |
228 return new MachineVerifierPass(allowPhysDoubleDefs); |
229} 230 |
231void MachineFunction::verify(Pass *p, bool allowDoubleDefs) const { 232 MachineVerifier(p, allowDoubleDefs) 233 .runOnMachineFunction(const_cast<MachineFunction&>(*this)); |
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 |
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; |
582 if (MO->isKill()) { |
583 isKill = true; |
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) |
593 isKill = true; |
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 |
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 |
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 } |
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 |