• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- ProfileVerifierPass.cpp - LLVM Pass to estimate profile info -------===//
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 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a pass that checks profiling information for
11 // plausibility.
12 //
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"
27 #include <set>
28 using namespace llvm;
29 
30 static cl::opt<bool,false>
31 ProfileVerifierDisableAssertions("profile-verifier-noassert",
32      cl::desc("Disable assertions"));
33 
34 namespace {
35   template<class FType, class BType>
36   class ProfileVerifierPassT : public FunctionPass {
37 
38     struct DetailedBlockInfo {
39       const BType *BB;
40       double      BBWeight;
41       double      inWeight;
42       int         inCount;
43       double      outWeight;
44       int         outCount;
45     };
46 
47     ProfileInfoT<FType, BType> *PI;
48     std::set<const BType*> BBisVisited;
49     std::set<const FType*>   FisVisited;
50     bool DisableAssertions;
51 
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
54     // functions.
55     bool PrintedDebugTree;
56     std::set<const BType*> BBisPrinted;
57     void debugEntry(DetailedBlockInfo*);
58     void printDebugInfo(const BType *BB);
59 
60   public:
61     static char ID; // Class identification, replacement for typeinfo
62 
ProfileVerifierPassT()63     explicit ProfileVerifierPassT () : FunctionPass(ID) {
64       initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
65       DisableAssertions = ProfileVerifierDisableAssertions;
66     }
ProfileVerifierPassT(bool da)67     explicit ProfileVerifierPassT (bool da) : FunctionPass(ID),
68                                               DisableAssertions(da) {
69       initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
70     }
71 
getAnalysisUsage(AnalysisUsage & AU) const72     void getAnalysisUsage(AnalysisUsage &AU) const {
73       AU.setPreservesAll();
74       AU.addRequired<ProfileInfoT<FType, BType> >();
75     }
76 
getPassName() const77     const char *getPassName() const {
78       return "Profiling information verifier";
79     }
80 
81     /// run - Verify the profile information.
82     bool runOnFunction(FType &F);
83     void recurseBasicBlock(const BType*);
84 
85     bool   exitReachable(const FType*);
86     double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge);
87     void   CheckValue(bool, const char*, DetailedBlockInfo*);
88   };
89 
90   typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass;
91 
92   template<class FType, class BType>
printDebugInfo(const BType * BB)93   void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) {
94 
95     if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
96 
97     double BBWeight = PI->getExecutionCount(BB);
98     if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; }
99     double inWeight = 0;
100     int inCount = 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;
111         inCount++;
112       }
113     }
114     double outWeight = 0;
115     int outCount = 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;
126         outCount++;
127       }
128     }
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";
136 
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);
142     }
143   }
144 
145   template<class FType, class BType>
debugEntry(DetailedBlockInfo * DI)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()));
157     }
158   }
159 
160   // This compares A and B for equality.
Equals(double A,double B)161   static bool Equals(double A, double B) {
162     return A == B;
163   }
164 
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>
exitReachable(const FType * F)169   bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) {
170     if (!F) return false;
171 
172     if (FisVisited.count(F)) return false;
173 
174     FType *Exit = F->getParent()->getFunction("exit");
175     if (Exit == F) {
176       return true;
177     }
178 
179     FisVisited.insert(F);
180     bool exits = false;
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();
184         if (F) {
185           exits |= exitReachable(F);
186         } else {
187           // This is a call to a pointer, all bets are off...
188           exits = true;
189         }
190         if (exits) break;
191       }
192     }
193     return exits;
194   }
195 
196   #define ASSERTMESSAGE(M) \
197     { dbgs() << "ASSERT:" << (M) << "\n"; \
198       if (!DisableAssertions) assert(0 && (M)); }
199 
200   template<class FType, class BType>
ReadOrAssert(typename ProfileInfoT<FType,BType>::Edge E)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");
207       return 0;
208     } else {
209       if (EdgeWeight < 0) {
210         dbgs() << "Edge " << E << " in Function "
211                << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": ";
212         ASSERTMESSAGE("Edge has negative value");
213       }
214       return EdgeWeight;
215     }
216   }
217 
218   template<class FType, class BType>
CheckValue(bool Error,const char * Message,DetailedBlockInfo * DI)219   void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error,
220                                                       const char *Message,
221                                                       DetailedBlockInfo *DI) {
222     if (Error) {
223       DEBUG(debugEntry(DI));
224       dbgs() << "Block " << DI->BB->getName() << " in Function "
225              << DI->BB->getParent()->getName() << ": ";
226       ASSERTMESSAGE(Message);
227     }
228     return;
229   }
230 
231   // This calculates the Information for a block and then recurses into the
232   // successors.
233   template<class FType, class BType>
recurseBasicBlock(const BType * BB)234   void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) {
235 
236     // Break the recursion by remembering all visited blocks.
237     if (BBisVisited.find(BB) != BBisVisited.end()) return;
238 
239     // Use a data structure to store all the information, this can then be handed
240     // to debug printers.
241     DetailedBlockInfo DI;
242     DI.BB = BB;
243     DI.outCount = DI.inCount = 0;
244     DI.inWeight = DI.outWeight = 0;
245 
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.
250     if (bpi == bpe) {
251       DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
252       DI.inCount++;
253     }
254     for (;bpi != bpe; ++bpi) {
255       if (ProcessedPreds.insert(*bpi).second) {
256         DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
257         DI.inCount++;
258       }
259     }
260 
261     // Read successors.
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) {
269       DI.outWeight += w;
270       DI.outCount++;
271     }
272     for (;bbi != bbe; ++bbi) {
273       if (ProcessedSuccs.insert(*bbi).second) {
274         DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
275         DI.outCount++;
276       }
277     }
278 
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);
285 
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();
290            i != ie; ++i) {
291         if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
292           FType *F = CI->getCalledFunction();
293           if (F && (F->getName() == "_setjmp")) {
294             isSetJmpTarget = true; break;
295           }
296         }
297       }
298     }
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();
303            i != ie; ++i) {
304         if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
305           FType *F = CI->getCalledFunction();
306           if (F) {
307             FisVisited.clear();
308             isExitReachable |= exitReachable(F);
309           } else {
310             // This is a call to a pointer, all bets are off...
311             isExitReachable = true;
312           }
313           if (isExitReachable) break;
314         }
315       }
316     }
317 
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);
323       }
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);
329     } else {
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);
337     }
338 
339 
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);
345     }
346   }
347 
348   template<class FType, class BType>
runOnFunction(FType & F)349   bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) {
350     PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >();
351     if (!PI)
352       ASSERTMESSAGE("No ProfileInfo available");
353 
354     // Prepare global variables.
355     PrintedDebugTree = false;
356     BBisVisited.clear();
357 
358     // Fetch entry block and recurse into it.
359     const BType *entry = &F.getEntryBlock();
360     recurseBasicBlock(entry);
361 
362     if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry))
363       ASSERTMESSAGE("Function count and entry block count do not match");
364 
365     return false;
366   }
367 
368   template<class FType, class BType>
369   char ProfileVerifierPassT<FType, BType>::ID = 0;
370 }
371 
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)
377 
378 namespace llvm {
createProfileVerifierPass()379   FunctionPass *createProfileVerifierPass() {
380     return new ProfileVerifierPass(ProfileVerifierDisableAssertions);
381   }
382 }
383 
384