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/Analysis/Passes.h"
16 #include "llvm/Analysis/ProfileInfo.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/Module.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Support/CFG.h"
21 #include "llvm/Support/CallSite.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/Format.h"
25 #include "llvm/Support/InstIterator.h"
26 #include "llvm/Support/raw_ostream.h"
30 static cl::opt<bool,false>
31 ProfileVerifierDisableAssertions("profile-verifier-noassert",
32 cl::desc("Disable assertions"));
35 template<class FType, class BType>
36 class ProfileVerifierPassT : public FunctionPass {
38 struct DetailedBlockInfo {
47 ProfileInfoT<FType, BType> *PI;
48 std::set<const BType*> BBisVisited;
49 std::set<const FType*> FisVisited;
50 bool DisableAssertions;
52 // When debugging is enabled, the verifier prints a whole slew of debug
53 // information, otherwise its just the assert. These are all the helper
55 bool PrintedDebugTree;
56 std::set<const BType*> BBisPrinted;
57 void debugEntry(DetailedBlockInfo*);
58 void printDebugInfo(const BType *BB);
61 static char ID; // Class identification, replacement for typeinfo
63 explicit ProfileVerifierPassT () : FunctionPass(ID) {
64 initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
65 DisableAssertions = ProfileVerifierDisableAssertions;
67 explicit ProfileVerifierPassT (bool da) : FunctionPass(ID),
68 DisableAssertions(da) {
69 initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
72 void getAnalysisUsage(AnalysisUsage &AU) const {
74 AU.addRequired<ProfileInfoT<FType, BType> >();
77 const char *getPassName() const {
78 return "Profiling information verifier";
81 /// run - Verify the profile information.
82 bool runOnFunction(FType &F);
83 void recurseBasicBlock(const BType*);
85 bool exitReachable(const FType*);
86 double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge);
87 void CheckValue(bool, const char*, DetailedBlockInfo*);
90 typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass;
92 template<class FType, class BType>
93 void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) {
95 if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
97 double BBWeight = PI->getExecutionCount(BB);
98 if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; }
101 std::set<const BType*> ProcessedPreds;
102 for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
103 bbi != bbe; ++bbi ) {
104 if (ProcessedPreds.insert(*bbi).second) {
105 typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB);
106 double EdgeWeight = PI->getEdgeWeight(E);
107 if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
108 dbgs() << "calculated in-edge " << E << ": "
109 << format("%20.20g",EdgeWeight) << "\n";
110 inWeight += EdgeWeight;
114 double outWeight = 0;
116 std::set<const BType*> ProcessedSuccs;
117 for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
118 bbi != bbe; ++bbi ) {
119 if (ProcessedSuccs.insert(*bbi).second) {
120 typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi);
121 double EdgeWeight = PI->getEdgeWeight(E);
122 if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
123 dbgs() << "calculated out-edge " << E << ": "
124 << format("%20.20g",EdgeWeight) << "\n";
125 outWeight += EdgeWeight;
129 dbgs() << "Block " << BB->getName() << " in "
130 << BB->getParent()->getName() << ":"
131 << "BBWeight=" << format("%20.20g",BBWeight) << ","
132 << "inWeight=" << format("%20.20g",inWeight) << ","
133 << "inCount=" << inCount << ","
134 << "outWeight=" << format("%20.20g",outWeight) << ","
135 << "outCount" << outCount << "\n";
137 // mark as visited and recurse into subnodes
138 BBisPrinted.insert(BB);
139 for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
140 bbi != bbe; ++bbi ) {
141 printDebugInfo(*bbi);
145 template<class FType, class BType>
146 void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) {
147 dbgs() << "TROUBLE: Block " << DI->BB->getName() << " in "
148 << DI->BB->getParent()->getName() << ":"
149 << "BBWeight=" << format("%20.20g",DI->BBWeight) << ","
150 << "inWeight=" << format("%20.20g",DI->inWeight) << ","
151 << "inCount=" << DI->inCount << ","
152 << "outWeight=" << format("%20.20g",DI->outWeight) << ","
153 << "outCount=" << DI->outCount << "\n";
154 if (!PrintedDebugTree) {
155 PrintedDebugTree = true;
156 printDebugInfo(&(DI->BB->getParent()->getEntryBlock()));
160 // This compares A and B for equality.
161 static bool Equals(double A, double B) {
165 // This checks if the function "exit" is reachable from an given function
166 // via calls, this is necessary to check if a profile is valid despite the
167 // counts not fitting exactly.
168 template<class FType, class BType>
169 bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) {
170 if (!F) return false;
172 if (FisVisited.count(F)) return false;
174 FType *Exit = F->getParent()->getFunction("exit");
179 FisVisited.insert(F);
181 for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
182 if (const CallInst *CI = dyn_cast<CallInst>(&*I)) {
183 FType *F = CI->getCalledFunction();
185 exits |= exitReachable(F);
187 // This is a call to a pointer, all bets are off...
196 #define ASSERTMESSAGE(M) \
197 { dbgs() << "ASSERT:" << (M) << "\n"; \
198 if (!DisableAssertions) assert(0 && (M)); }
200 template<class FType, class BType>
201 double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) {
202 double EdgeWeight = PI->getEdgeWeight(E);
203 if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) {
204 dbgs() << "Edge " << E << " in Function "
205 << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": ";
206 ASSERTMESSAGE("Edge has missing value");
209 if (EdgeWeight < 0) {
210 dbgs() << "Edge " << E << " in Function "
211 << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": ";
212 ASSERTMESSAGE("Edge has negative value");
218 template<class FType, class BType>
219 void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error,
221 DetailedBlockInfo *DI) {
223 DEBUG(debugEntry(DI));
224 dbgs() << "Block " << DI->BB->getName() << " in Function "
225 << DI->BB->getParent()->getName() << ": ";
226 ASSERTMESSAGE(Message);
231 // This calculates the Information for a block and then recurses into the
233 template<class FType, class BType>
234 void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) {
236 // Break the recursion by remembering all visited blocks.
237 if (BBisVisited.find(BB) != BBisVisited.end()) return;
239 // Use a data structure to store all the information, this can then be handed
240 // to debug printers.
241 DetailedBlockInfo DI;
243 DI.outCount = DI.inCount = 0;
244 DI.inWeight = DI.outWeight = 0;
246 // Read predecessors.
247 std::set<const BType*> ProcessedPreds;
248 const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB);
249 // If there are none, check for (0,BB) edge.
251 DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
254 for (;bpi != bpe; ++bpi) {
255 if (ProcessedPreds.insert(*bpi).second) {
256 DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
262 std::set<const BType*> ProcessedSuccs;
263 succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
264 // If there is an (0,BB) edge, consider it too. (This is done not only when
265 // there are no successors, but every time; not every function contains
266 // return blocks with no successors (think loop latch as return block)).
267 double w = PI->getEdgeWeight(PI->getEdge(BB,0));
268 if (w != ProfileInfoT<FType, BType>::MissingValue) {
272 for (;bbi != bbe; ++bbi) {
273 if (ProcessedSuccs.insert(*bbi).second) {
274 DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
279 // Read block weight.
280 DI.BBWeight = PI->getExecutionCount(BB);
281 CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue,
282 "BasicBlock has missing value", &DI);
283 CheckValue(DI.BBWeight < 0,
284 "BasicBlock has negative value", &DI);
286 // Check if this block is a setjmp target.
287 bool isSetJmpTarget = false;
288 if (DI.outWeight > DI.inWeight) {
289 for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
291 if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
292 FType *F = CI->getCalledFunction();
293 if (F && (F->getName() == "_setjmp")) {
294 isSetJmpTarget = true; break;
299 // Check if this block is eventually reaching exit.
300 bool isExitReachable = false;
301 if (DI.inWeight > DI.outWeight) {
302 for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
304 if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
305 FType *F = CI->getCalledFunction();
308 isExitReachable |= exitReachable(F);
310 // This is a call to a pointer, all bets are off...
311 isExitReachable = true;
313 if (isExitReachable) break;
318 if (DI.inCount > 0 && DI.outCount == 0) {
319 // If this is a block with no successors.
320 if (!isSetJmpTarget) {
321 CheckValue(!Equals(DI.inWeight,DI.BBWeight),
322 "inWeight and BBWeight do not match", &DI);
324 } else if (DI.inCount == 0 && DI.outCount > 0) {
325 // If this is a block with no predecessors.
326 if (!isExitReachable)
327 CheckValue(!Equals(DI.BBWeight,DI.outWeight),
328 "BBWeight and outWeight do not match", &DI);
330 // If this block has successors and predecessors.
331 if (DI.inWeight > DI.outWeight && !isExitReachable)
332 CheckValue(!Equals(DI.inWeight,DI.outWeight),
333 "inWeight and outWeight do not match", &DI);
334 if (DI.inWeight < DI.outWeight && !isSetJmpTarget)
335 CheckValue(!Equals(DI.inWeight,DI.outWeight),
336 "inWeight and outWeight do not match", &DI);
340 // Mark this block as visited, rescurse into successors.
341 BBisVisited.insert(BB);
342 for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
343 bbi != bbe; ++bbi ) {
344 recurseBasicBlock(*bbi);
348 template<class FType, class BType>
349 bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) {
350 PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >();
352 ASSERTMESSAGE("No ProfileInfo available");
354 // Prepare global variables.
355 PrintedDebugTree = false;
358 // Fetch entry block and recurse into it.
359 const BType *entry = &F.getEntryBlock();
360 recurseBasicBlock(entry);
362 if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry))
363 ASSERTMESSAGE("Function count and entry block count do not match");
368 template<class FType, class BType>
369 char ProfileVerifierPassT<FType, BType>::ID = 0;
372 INITIALIZE_PASS_BEGIN(ProfileVerifierPass, "profile-verifier",
373 "Verify profiling information", false, true)
374 INITIALIZE_AG_DEPENDENCY(ProfileInfo)
375 INITIALIZE_PASS_END(ProfileVerifierPass, "profile-verifier",
376 "Verify profiling information", false, true)
379 FunctionPass *createProfileVerifierPass() {
380 return new ProfileVerifierPass(ProfileVerifierDisableAssertions);