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/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"
26#include <set>
27using namespace llvm;
28
29static cl::opt<bool,false>
30ProfileVerifierDisableAssertions("profile-verifier-noassert",
31     cl::desc("Disable assertions"));
32
33namespace llvm {
34  template<class FType, class BType>
35  class ProfileVerifierPassT : public FunctionPass {
36
37    struct DetailedBlockInfo {
38      const BType *BB;
39      double      BBWeight;
40      double      inWeight;
41      int         inCount;
42      double      outWeight;
43      int         outCount;
44    };
45
46    ProfileInfoT<FType, BType> *PI;
47    std::set<const BType*> BBisVisited;
48    std::set<const FType*>   FisVisited;
49    bool DisableAssertions;
50
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
53    // functions.
54    bool PrintedDebugTree;
55    std::set<const BType*> BBisPrinted;
56    void debugEntry(DetailedBlockInfo*);
57    void printDebugInfo(const BType *BB);
58
59  public:
60    static char ID; // Class identification, replacement for typeinfo
61
62    explicit ProfileVerifierPassT () : FunctionPass(ID) {
63      initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
64      DisableAssertions = ProfileVerifierDisableAssertions;
65    }
66    explicit ProfileVerifierPassT (bool da) : FunctionPass(ID),
67                                              DisableAssertions(da) {
68      initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
69    }
70
71    void getAnalysisUsage(AnalysisUsage &AU) const {
72      AU.setPreservesAll();
73      AU.addRequired<ProfileInfoT<FType, BType> >();
74    }
75
76    const char *getPassName() const {
77      return "Profiling information verifier";
78    }
79
80    /// run - Verify the profile information.
81    bool runOnFunction(FType &F);
82    void recurseBasicBlock(const BType*);
83
84    bool   exitReachable(const FType*);
85    double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge);
86    void   CheckValue(bool, const char*, DetailedBlockInfo*);
87  };
88
89  typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass;
90
91  template<class FType, class BType>
92  void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) {
93
94    if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
95
96    double BBWeight = PI->getExecutionCount(BB);
97    if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; }
98    double inWeight = 0;
99    int inCount = 0;
100    std::set<const BType*> ProcessedPreds;
101    for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
102         bbi != bbe; ++bbi ) {
103      if (ProcessedPreds.insert(*bbi).second) {
104        typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB);
105        double EdgeWeight = PI->getEdgeWeight(E);
106        if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
107        dbgs() << "calculated in-edge " << E << ": "
108               << format("%20.20g",EdgeWeight) << "\n";
109        inWeight += EdgeWeight;
110        inCount++;
111      }
112    }
113    double outWeight = 0;
114    int outCount = 0;
115    std::set<const BType*> ProcessedSuccs;
116    for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
117          bbi != bbe; ++bbi ) {
118      if (ProcessedSuccs.insert(*bbi).second) {
119        typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi);
120        double EdgeWeight = PI->getEdgeWeight(E);
121        if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
122        dbgs() << "calculated out-edge " << E << ": "
123               << format("%20.20g",EdgeWeight) << "\n";
124        outWeight += EdgeWeight;
125        outCount++;
126      }
127    }
128    dbgs() << "Block " << BB->getNameStr()                << " in "
129           << BB->getParent()->getNameStr()               << ":"
130           << "BBWeight="  << format("%20.20g",BBWeight)  << ","
131           << "inWeight="  << format("%20.20g",inWeight)  << ","
132           << "inCount="   << inCount                     << ","
133           << "outWeight=" << format("%20.20g",outWeight) << ","
134           << "outCount"   << outCount                    << "\n";
135
136    // mark as visited and recurse into subnodes
137    BBisPrinted.insert(BB);
138    for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
139          bbi != bbe; ++bbi ) {
140      printDebugInfo(*bbi);
141    }
142  }
143
144  template<class FType, class BType>
145  void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) {
146    dbgs() << "TROUBLE: Block " << DI->BB->getNameStr()       << " in "
147           << DI->BB->getParent()->getNameStr()               << ":"
148           << "BBWeight="  << format("%20.20g",DI->BBWeight)  << ","
149           << "inWeight="  << format("%20.20g",DI->inWeight)  << ","
150           << "inCount="   << DI->inCount                     << ","
151           << "outWeight=" << format("%20.20g",DI->outWeight) << ","
152           << "outCount="  << DI->outCount                    << "\n";
153    if (!PrintedDebugTree) {
154      PrintedDebugTree = true;
155      printDebugInfo(&(DI->BB->getParent()->getEntryBlock()));
156    }
157  }
158
159  // This compares A and B for equality.
160  static bool Equals(double A, double B) {
161    return A == B;
162  }
163
164  // This checks if the function "exit" is reachable from an given function
165  // via calls, this is necessary to check if a profile is valid despite the
166  // counts not fitting exactly.
167  template<class FType, class BType>
168  bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) {
169    if (!F) return false;
170
171    if (FisVisited.count(F)) return false;
172
173    FType *Exit = F->getParent()->getFunction("exit");
174    if (Exit == F) {
175      return true;
176    }
177
178    FisVisited.insert(F);
179    bool exits = false;
180    for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
181      if (const CallInst *CI = dyn_cast<CallInst>(&*I)) {
182        FType *F = CI->getCalledFunction();
183        if (F) {
184          exits |= exitReachable(F);
185        } else {
186          // This is a call to a pointer, all bets are off...
187          exits = true;
188        }
189        if (exits) break;
190      }
191    }
192    return exits;
193  }
194
195  #define ASSERTMESSAGE(M) \
196    { dbgs() << "ASSERT:" << (M) << "\n"; \
197      if (!DisableAssertions) assert(0 && (M)); }
198
199  template<class FType, class BType>
200  double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) {
201    double EdgeWeight = PI->getEdgeWeight(E);
202    if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) {
203      dbgs() << "Edge " << E << " in Function "
204             << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
205      ASSERTMESSAGE("Edge has missing value");
206      return 0;
207    } else {
208      if (EdgeWeight < 0) {
209        dbgs() << "Edge " << E << " in Function "
210               << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
211        ASSERTMESSAGE("Edge has negative value");
212      }
213      return EdgeWeight;
214    }
215  }
216
217  template<class FType, class BType>
218  void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error,
219                                                      const char *Message,
220                                                      DetailedBlockInfo *DI) {
221    if (Error) {
222      DEBUG(debugEntry(DI));
223      dbgs() << "Block " << DI->BB->getNameStr() << " in Function "
224             << DI->BB->getParent()->getNameStr() << ": ";
225      ASSERTMESSAGE(Message);
226    }
227    return;
228  }
229
230  // This calculates the Information for a block and then recurses into the
231  // successors.
232  template<class FType, class BType>
233  void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) {
234
235    // Break the recursion by remembering all visited blocks.
236    if (BBisVisited.find(BB) != BBisVisited.end()) return;
237
238    // Use a data structure to store all the information, this can then be handed
239    // to debug printers.
240    DetailedBlockInfo DI;
241    DI.BB = BB;
242    DI.outCount = DI.inCount = 0;
243    DI.inWeight = DI.outWeight = 0;
244
245    // Read predecessors.
246    std::set<const BType*> ProcessedPreds;
247    const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB);
248    // If there are none, check for (0,BB) edge.
249    if (bpi == bpe) {
250      DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
251      DI.inCount++;
252    }
253    for (;bpi != bpe; ++bpi) {
254      if (ProcessedPreds.insert(*bpi).second) {
255        DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
256        DI.inCount++;
257      }
258    }
259
260    // Read successors.
261    std::set<const BType*> ProcessedSuccs;
262    succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
263    // If there is an (0,BB) edge, consider it too. (This is done not only when
264    // there are no successors, but every time; not every function contains
265    // return blocks with no successors (think loop latch as return block)).
266    double w = PI->getEdgeWeight(PI->getEdge(BB,0));
267    if (w != ProfileInfoT<FType, BType>::MissingValue) {
268      DI.outWeight += w;
269      DI.outCount++;
270    }
271    for (;bbi != bbe; ++bbi) {
272      if (ProcessedSuccs.insert(*bbi).second) {
273        DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
274        DI.outCount++;
275      }
276    }
277
278    // Read block weight.
279    DI.BBWeight = PI->getExecutionCount(BB);
280    CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue,
281               "BasicBlock has missing value", &DI);
282    CheckValue(DI.BBWeight < 0,
283               "BasicBlock has negative value", &DI);
284
285    // Check if this block is a setjmp target.
286    bool isSetJmpTarget = false;
287    if (DI.outWeight > DI.inWeight) {
288      for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
289           i != ie; ++i) {
290        if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
291          FType *F = CI->getCalledFunction();
292          if (F && (F->getName() == "_setjmp")) {
293            isSetJmpTarget = true; break;
294          }
295        }
296      }
297    }
298    // Check if this block is eventually reaching exit.
299    bool isExitReachable = false;
300    if (DI.inWeight > DI.outWeight) {
301      for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
302           i != ie; ++i) {
303        if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
304          FType *F = CI->getCalledFunction();
305          if (F) {
306            FisVisited.clear();
307            isExitReachable |= exitReachable(F);
308          } else {
309            // This is a call to a pointer, all bets are off...
310            isExitReachable = true;
311          }
312          if (isExitReachable) break;
313        }
314      }
315    }
316
317    if (DI.inCount > 0 && DI.outCount == 0) {
318       // If this is a block with no successors.
319      if (!isSetJmpTarget) {
320        CheckValue(!Equals(DI.inWeight,DI.BBWeight),
321                   "inWeight and BBWeight do not match", &DI);
322      }
323    } else if (DI.inCount == 0 && DI.outCount > 0) {
324      // If this is a block with no predecessors.
325      if (!isExitReachable)
326        CheckValue(!Equals(DI.BBWeight,DI.outWeight),
327                   "BBWeight and outWeight do not match", &DI);
328    } else {
329      // If this block has successors and predecessors.
330      if (DI.inWeight > DI.outWeight && !isExitReachable)
331        CheckValue(!Equals(DI.inWeight,DI.outWeight),
332                   "inWeight and outWeight do not match", &DI);
333      if (DI.inWeight < DI.outWeight && !isSetJmpTarget)
334        CheckValue(!Equals(DI.inWeight,DI.outWeight),
335                   "inWeight and outWeight do not match", &DI);
336    }
337
338
339    // Mark this block as visited, rescurse into successors.
340    BBisVisited.insert(BB);
341    for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
342          bbi != bbe; ++bbi ) {
343      recurseBasicBlock(*bbi);
344    }
345  }
346
347  template<class FType, class BType>
348  bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) {
349    PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >();
350    if (!PI)
351      ASSERTMESSAGE("No ProfileInfo available");
352
353    // Prepare global variables.
354    PrintedDebugTree = false;
355    BBisVisited.clear();
356
357    // Fetch entry block and recurse into it.
358    const BType *entry = &F.getEntryBlock();
359    recurseBasicBlock(entry);
360
361    if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry))
362      ASSERTMESSAGE("Function count and entry block count do not match");
363
364    return false;
365  }
366
367  template<class FType, class BType>
368  char ProfileVerifierPassT<FType, BType>::ID = 0;
369}
370
371INITIALIZE_PASS_BEGIN(ProfileVerifierPass, "profile-verifier",
372                "Verify profiling information", false, true)
373INITIALIZE_AG_DEPENDENCY(ProfileInfo)
374INITIALIZE_PASS_END(ProfileVerifierPass, "profile-verifier",
375                "Verify profiling information", false, true)
376
377namespace llvm {
378  FunctionPass *createProfileVerifierPass() {
379    return new ProfileVerifierPass(ProfileVerifierDisableAssertions);
380  }
381}
382
383