ProfileVerifierPass.cpp revision e7ddcfdebe357b4067f9c7d68d44616e11351a23 
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/Pass.h"
16#include "llvm/Analysis/ProfileInfo.h"
17#include "llvm/Support/CommandLine.h"
18#include "llvm/Support/CFG.h"
19#include "llvm/Support/raw_ostream.h"
20#include "llvm/Support/Debug.h"
21#include <set>
22using namespace llvm;
23
24static bool DisableAssertions = false;
25static cl::opt<bool,true>
26ProfileVerifierDisableAssertions("profile-verifier-noassert",
27    cl::location(DisableAssertions), cl::desc("Disable assertions"));
28bool PrintedDebugTree = false;
29
30namespace {
31  class VISIBILITY_HIDDEN ProfileVerifierPass : public FunctionPass {
32    ProfileInfo *PI;
33    std::set<const BasicBlock*> BBisVisited;
34#ifndef NDEBUG
35    std::set<const BasicBlock*> BBisPrinted;
36    void debugEntry(const BasicBlock* BB, double w, double inw, int inc,
37                    double outw, int outc, double d);
38    void printDebugInfo(const BasicBlock *BB);
39#endif
40  public:
41    static char ID; // Class identification, replacement for typeinfo
42
43    explicit ProfileVerifierPass () : FunctionPass(&ID) {
44      DisableAssertions = ProfileVerifierDisableAssertions;
45    }
46
47    void getAnalysisUsage(AnalysisUsage &AU) const {
48      AU.setPreservesAll();
49      AU.addRequired<ProfileInfo>();
50    }
51
52    const char *getPassName() const {
53      return "Profiling information verifier";
54    }
55
56    /// run - Verify the profile information.
57    bool runOnFunction(Function &F);
58    void recurseBasicBlock(const BasicBlock *BB);
59  };
60}  // End of anonymous namespace
61
62char ProfileVerifierPass::ID = 0;
63static RegisterPass<ProfileVerifierPass>
64X("profile-verifier", "Verify profiling information", false, true);
65
66namespace llvm {
67  FunctionPass *createProfileVerifierPass() {
68    return new ProfileVerifierPass();
69  }
70}
71
72#ifndef NDEBUG
73void ProfileVerifierPass::printDebugInfo(const BasicBlock *BB) {
74
75  if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
76
77  double BBWeight = PI->getExecutionCount(BB);
78  if (BBWeight == ProfileInfo::MissingValue) { BBWeight = 0; }
79  double inWeight = 0;
80  int inCount = 0;
81  std::set<const BasicBlock*> ProcessedPreds;
82  for ( pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
83        bbi != bbe; ++bbi ) {
84    if (ProcessedPreds.insert(*bbi).second) {
85      double EdgeWeight = PI->getEdgeWeight(PI->getEdge(*bbi,BB));
86      if (EdgeWeight == ProfileInfo::MissingValue) { EdgeWeight = 0; }
87      DEBUG(errs()<<"calculated in-edge ("<<(*bbi)->getNameStr()<<","<<BB->getNameStr()
88          <<"): "<<EdgeWeight<<"\n");
89      inWeight += EdgeWeight;
90      inCount++;
91    }
92  }
93  double outWeight = 0;
94  int outCount = 0;
95  std::set<const BasicBlock*> ProcessedSuccs;
96  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
97        bbi != bbe; ++bbi ) {
98    if (ProcessedSuccs.insert(*bbi).second) {
99      double EdgeWeight = PI->getEdgeWeight(PI->getEdge(BB,*bbi));
100      if (EdgeWeight == ProfileInfo::MissingValue) { EdgeWeight = 0; }
101      DEBUG(errs()<<"calculated out-edge ("<<BB->getNameStr()<<","<<(*bbi)->getNameStr()
102          <<"): "<<EdgeWeight<<"\n");
103      outWeight += EdgeWeight;
104      outCount++;
105    }
106  }
107  DEBUG(errs()<<"Block "<<BB->getNameStr()<<" in "<<BB->getParent()->getNameStr()
108      <<",BBWeight="<<BBWeight<<",inWeight="<<inWeight<<",inCount="<<inCount
109      <<",outWeight="<<outWeight<<",outCount"<<outCount<<"\n");
110
111  // mark as visited and recurse into subnodes
112  BBisPrinted.insert(BB);
113  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
114        bbi != bbe; ++bbi ) {
115    printDebugInfo(*bbi);
116  }
117}
118
119void ProfileVerifierPass::debugEntry (const BasicBlock* BB, double w,
120                                      double inw,  int inc, double outw, int
121                                      outc, double d) {
122  DEBUG(errs()<<"TROUBLE: Block "<<BB->getNameStr()<<" in "<<BB->getParent()->getNameStr()
123      <<",BBWeight="<<w<<",inWeight="<<inw<<",inCount="<<inc<<",outWeight="
124      <<outw<<",outCount"<<outc<<"\n");
125  DEBUG(errs()<<"DELTA:"<<d<<"\n");
126  if (!PrintedDebugTree) {
127    PrintedDebugTree = true;
128    printDebugInfo(&(BB->getParent()->getEntryBlock()));
129  }
130}
131#endif
132
133// compare with relative error
134static bool dcmp(double A, double B) {
135  double maxRelativeError = 0.0000001;
136  if (A == B)
137    return true;
138  double relativeError;
139  if (fabs(B) > fabs(A))
140    relativeError = fabs((A - B) / B);
141  else
142    relativeError = fabs((A - B) / A);
143  if (relativeError <= maxRelativeError) return true;
144  return false;
145}
146
147#define CHECK(C,M) \
148if (C) { \
149  if (DisableAssertions) { errs()<<(M)<<"\n"; } else { assert((!(C)) && (M)); } \
150}
151
152#define CHECKDEBUG(C,M,D) \
153if (C) { \
154  DEBUG(debugEntry(BB, BBWeight, inWeight,  inCount, \
155                                 outWeight, outCount, (D))); \
156  if (DisableAssertions) { errs()<<(M)<<"\n"; } else { assert((!(C)) && (M)); } \
157}
158
159void ProfileVerifierPass::recurseBasicBlock(const BasicBlock *BB) {
160
161  if (BBisVisited.find(BB) != BBisVisited.end()) return;
162
163  double inWeight = 0;
164  int inCount = 0;
165  std::set<const BasicBlock*> ProcessedPreds;
166  for ( pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
167        bbi != bbe; ++bbi ) {
168    if (ProcessedPreds.insert(*bbi).second) {
169      double EdgeWeight = PI->getEdgeWeight(PI->getEdge(*bbi,BB));
170      CHECK(EdgeWeight == ProfileInfo::MissingValue,
171            "ASSERT:Edge has missing value");
172      inWeight += EdgeWeight; inCount++;
173    }
174  }
175
176  double outWeight = 0;
177  int outCount = 0;
178  std::set<const BasicBlock*> ProcessedSuccs;
179  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
180        bbi != bbe; ++bbi ) {
181    if (ProcessedSuccs.insert(*bbi).second) {
182      double EdgeWeight = PI->getEdgeWeight(PI->getEdge(BB,*bbi));
183      CHECK(EdgeWeight == ProfileInfo::MissingValue,
184            "ASSERT:Edge has missing value");
185      outWeight += EdgeWeight; outCount++;
186    }
187  }
188
189  double BBWeight = PI->getExecutionCount(BB);
190  CHECKDEBUG(BBWeight == ProfileInfo::MissingValue,
191             "ASSERT:BasicBlock has missing value",-1);
192
193  if (inCount > 0) {
194    CHECKDEBUG(!dcmp(inWeight,BBWeight),
195        "ASSERT:inWeight and BBWeight do not match",inWeight-BBWeight);
196  }
197  if (outCount > 0) {
198    CHECKDEBUG(!dcmp(outWeight,BBWeight),
199        "ASSERT:outWeight and BBWeight do not match",outWeight-BBWeight);
200  }
201
202  // mark as visited and recurse into subnodes
203  BBisVisited.insert(BB);
204  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
205        bbi != bbe; ++bbi ) {
206    recurseBasicBlock(*bbi);
207  }
208}
209
210bool ProfileVerifierPass::runOnFunction(Function &F) {
211  PI = &getAnalysis<ProfileInfo>();
212
213  if (PI->getExecutionCount(&F) == ProfileInfo::MissingValue) {
214    DEBUG(errs()<<"Function "<<F.getNameStr()<<" has no profile\n");
215    return false;
216  }
217
218  PrintedDebugTree = false;
219  BBisVisited.clear();
220
221  const BasicBlock *entry = &F.getEntryBlock();
222  recurseBasicBlock(entry);
223
224  if (!DisableAssertions)
225    assert((PI->getExecutionCount(&F)==PI->getExecutionCount(entry)) &&
226           "Function count and entry block count do not match");
227  return false;
228}
229