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>
28using namespace llvm;
29
30static cl::opt<bool,false>
31ProfileVerifierDisableAssertions("profile-verifier-noassert",
32     cl::desc("Disable assertions"));
33
34namespace {
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
63    explicit ProfileVerifierPassT () : FunctionPass(ID) {
64      initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
65      DisableAssertions = ProfileVerifierDisableAssertions;
66    }
67    explicit ProfileVerifierPassT (bool da) : FunctionPass(ID),
68                                              DisableAssertions(da) {
69      initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
70    }
71
72    void getAnalysisUsage(AnalysisUsage &AU) const {
73      AU.setPreservesAll();
74      AU.addRequired<ProfileInfoT<FType, BType> >();
75    }
76
77    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>
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>
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.
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>
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>
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>
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>
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>
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
372INITIALIZE_PASS_BEGIN(ProfileVerifierPass, "profile-verifier",
373                "Verify profiling information", false, true)
374INITIALIZE_AG_DEPENDENCY(ProfileInfo)
375INITIALIZE_PASS_END(ProfileVerifierPass, "profile-verifier",
376                "Verify profiling information", false, true)
377
378namespace llvm {
379  FunctionPass *createProfileVerifierPass() {
380    return new ProfileVerifierPass(ProfileVerifierDisableAssertions);
381  }
382}
383
384