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