1 //===- ProfileVerifierPass.cpp - LLVM Pass to estimate profile info -------===//
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 // This file implements a pass that checks profiling information for
13 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "profile-verifier"
15 #include "llvm/Instructions.h"
16 #include "llvm/Module.h"
17 #include "llvm/Pass.h"
18 #include "llvm/Analysis/ProfileInfo.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Support/CallSite.h"
21 #include "llvm/Support/CFG.h"
22 #include "llvm/Support/InstIterator.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Support/Format.h"
25 #include "llvm/Support/Debug.h"
29 static cl::opt<bool,false>
30 ProfileVerifierDisableAssertions("profile-verifier-noassert",
31 cl::desc("Disable assertions"));
34 template<class FType, class BType>
35 class ProfileVerifierPassT : public FunctionPass {
37 struct DetailedBlockInfo {
46 ProfileInfoT<FType, BType> *PI;
47 std::set<const BType*> BBisVisited;
48 std::set<const FType*> FisVisited;
49 bool DisableAssertions;
51 // When debugging is enabled, the verifier prints a whole slew of debug
52 // information, otherwise its just the assert. These are all the helper
54 bool PrintedDebugTree;
55 std::set<const BType*> BBisPrinted;
56 void debugEntry(DetailedBlockInfo*);
57 void printDebugInfo(const BType *BB);
60 static char ID; // Class identification, replacement for typeinfo
62 explicit ProfileVerifierPassT () : FunctionPass(&ID) {
63 DisableAssertions = ProfileVerifierDisableAssertions;
65 explicit ProfileVerifierPassT (bool da) : FunctionPass(&ID),
66 DisableAssertions(da) {
69 void getAnalysisUsage(AnalysisUsage &AU) const {
71 AU.addRequired<ProfileInfoT<FType, BType> >();
74 const char *getPassName() const {
75 return "Profiling information verifier";
78 /// run - Verify the profile information.
79 bool runOnFunction(FType &F);
80 void recurseBasicBlock(const BType*);
82 bool exitReachable(const FType*);
83 double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge);
84 void CheckValue(bool, const char*, DetailedBlockInfo*);
87 typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass;
89 template<class FType, class BType>
90 void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) {
92 if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
94 double BBWeight = PI->getExecutionCount(BB);
95 if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; }
98 std::set<const BType*> ProcessedPreds;
99 for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
100 bbi != bbe; ++bbi ) {
101 if (ProcessedPreds.insert(*bbi).second) {
102 typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB);
103 double EdgeWeight = PI->getEdgeWeight(E);
104 if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
105 dbgs() << "calculated in-edge " << E << ": "
106 << format("%20.20g",EdgeWeight) << "\n";
107 inWeight += EdgeWeight;
111 double outWeight = 0;
113 std::set<const BType*> ProcessedSuccs;
114 for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
115 bbi != bbe; ++bbi ) {
116 if (ProcessedSuccs.insert(*bbi).second) {
117 typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi);
118 double EdgeWeight = PI->getEdgeWeight(E);
119 if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
120 dbgs() << "calculated out-edge " << E << ": "
121 << format("%20.20g",EdgeWeight) << "\n";
122 outWeight += EdgeWeight;
126 dbgs() << "Block " << BB->getNameStr() << " in "
127 << BB->getParent()->getNameStr() << ":"
128 << "BBWeight=" << format("%20.20g",BBWeight) << ","
129 << "inWeight=" << format("%20.20g",inWeight) << ","
130 << "inCount=" << inCount << ","
131 << "outWeight=" << format("%20.20g",outWeight) << ","
132 << "outCount" << outCount << "\n";
134 // mark as visited and recurse into subnodes
135 BBisPrinted.insert(BB);
136 for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
137 bbi != bbe; ++bbi ) {
138 printDebugInfo(*bbi);
142 template<class FType, class BType>
143 void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) {
144 dbgs() << "TROUBLE: Block " << DI->BB->getNameStr() << " in "
145 << DI->BB->getParent()->getNameStr() << ":"
146 << "BBWeight=" << format("%20.20g",DI->BBWeight) << ","
147 << "inWeight=" << format("%20.20g",DI->inWeight) << ","
148 << "inCount=" << DI->inCount << ","
149 << "outWeight=" << format("%20.20g",DI->outWeight) << ","
150 << "outCount=" << DI->outCount << "\n";
151 if (!PrintedDebugTree) {
152 PrintedDebugTree = true;
153 printDebugInfo(&(DI->BB->getParent()->getEntryBlock()));
157 // This compares A and B for equality.
158 static bool Equals(double A, double B) {
162 // This checks if the function "exit" is reachable from an given function
163 // via calls, this is necessary to check if a profile is valid despite the
164 // counts not fitting exactly.
165 template<class FType, class BType>
166 bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) {
167 if (!F) return false;
169 if (FisVisited.count(F)) return false;
171 FType *Exit = F->getParent()->getFunction("exit");
176 FisVisited.insert(F);
178 for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
179 if (const CallInst *CI = dyn_cast<CallInst>(&*I)) {
180 FType *F = CI->getCalledFunction();
182 exits |= exitReachable(F);
184 // This is a call to a pointer, all bets are off...
193 #define ASSERTMESSAGE(M) \
194 { dbgs() << "ASSERT:" << (M) << "\n"; \
195 if (!DisableAssertions) assert(0 && (M)); }
197 template<class FType, class BType>
198 double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) {
199 double EdgeWeight = PI->getEdgeWeight(E);
200 if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) {
201 dbgs() << "Edge " << E << " in Function "
202 << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
203 ASSERTMESSAGE("Edge has missing value");
206 if (EdgeWeight < 0) {
207 dbgs() << "Edge " << E << " in Function "
208 << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
209 ASSERTMESSAGE("Edge has negative value");
215 template<class FType, class BType>
216 void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error,
218 DetailedBlockInfo *DI) {
220 DEBUG(debugEntry(DI));
221 dbgs() << "Block " << DI->BB->getNameStr() << " in Function "
222 << DI->BB->getParent()->getNameStr() << ": ";
223 ASSERTMESSAGE(Message);
228 // This calculates the Information for a block and then recurses into the
230 template<class FType, class BType>
231 void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) {
233 // Break the recursion by remembering all visited blocks.
234 if (BBisVisited.find(BB) != BBisVisited.end()) return;
236 // Use a data structure to store all the information, this can then be handed
237 // to debug printers.
238 DetailedBlockInfo DI;
240 DI.outCount = DI.inCount = 0;
241 DI.inWeight = DI.outWeight = 0;
243 // Read predecessors.
244 std::set<const BType*> ProcessedPreds;
245 const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB);
246 // If there are none, check for (0,BB) edge.
248 DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
251 for (;bpi != bpe; ++bpi) {
252 if (ProcessedPreds.insert(*bpi).second) {
253 DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
259 std::set<const BType*> ProcessedSuccs;
260 succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
261 // If there is an (0,BB) edge, consider it too. (This is done not only when
262 // there are no successors, but every time; not every function contains
263 // return blocks with no successors (think loop latch as return block)).
264 double w = PI->getEdgeWeight(PI->getEdge(BB,0));
265 if (w != ProfileInfoT<FType, BType>::MissingValue) {
269 for (;bbi != bbe; ++bbi) {
270 if (ProcessedSuccs.insert(*bbi).second) {
271 DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
276 // Read block weight.
277 DI.BBWeight = PI->getExecutionCount(BB);
278 CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue,
279 "BasicBlock has missing value", &DI);
280 CheckValue(DI.BBWeight < 0,
281 "BasicBlock has negative value", &DI);
283 // Check if this block is a setjmp target.
284 bool isSetJmpTarget = false;
285 if (DI.outWeight > DI.inWeight) {
286 for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
288 if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
289 FType *F = CI->getCalledFunction();
290 if (F && (F->getNameStr() == "_setjmp")) {
291 isSetJmpTarget = true; break;
296 // Check if this block is eventually reaching exit.
297 bool isExitReachable = false;
298 if (DI.inWeight > DI.outWeight) {
299 for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
301 if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
302 FType *F = CI->getCalledFunction();
305 isExitReachable |= exitReachable(F);
307 // This is a call to a pointer, all bets are off...
308 isExitReachable = true;
310 if (isExitReachable) break;
315 if (DI.inCount > 0 && DI.outCount == 0) {
316 // If this is a block with no successors.
317 if (!isSetJmpTarget) {
318 CheckValue(!Equals(DI.inWeight,DI.BBWeight),
319 "inWeight and BBWeight do not match", &DI);
321 } else if (DI.inCount == 0 && DI.outCount > 0) {
322 // If this is a block with no predecessors.
323 if (!isExitReachable)
324 CheckValue(!Equals(DI.BBWeight,DI.outWeight),
325 "BBWeight and outWeight do not match", &DI);
327 // If this block has successors and predecessors.
328 if (DI.inWeight > DI.outWeight && !isExitReachable)
329 CheckValue(!Equals(DI.inWeight,DI.outWeight),
330 "inWeight and outWeight do not match", &DI);
331 if (DI.inWeight < DI.outWeight && !isSetJmpTarget)
332 CheckValue(!Equals(DI.inWeight,DI.outWeight),
333 "inWeight and outWeight do not match", &DI);
337 // Mark this block as visited, rescurse into successors.
338 BBisVisited.insert(BB);
339 for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
340 bbi != bbe; ++bbi ) {
341 recurseBasicBlock(*bbi);
345 template<class FType, class BType>
346 bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) {
347 PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >();
349 ASSERTMESSAGE("No ProfileInfo available");
351 // Prepare global variables.
352 PrintedDebugTree = false;
355 // Fetch entry block and recurse into it.
356 const BType *entry = &F.getEntryBlock();
357 recurseBasicBlock(entry);
359 if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry))
360 ASSERTMESSAGE("Function count and entry block count do not match");
365 template<class FType, class BType>
366 char ProfileVerifierPassT<FType, BType>::ID = 0;
369 static RegisterPass<ProfileVerifierPass>
370 X("profile-verifier", "Verify profiling information", false, true);
373 FunctionPass *createProfileVerifierPass() {
374 return new ProfileVerifierPass(ProfileVerifierDisableAssertions);