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