lib/Analysis/ProfileVerifierPass.cpp

   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>
  22 using namespace llvm;
  23
  24 static bool DisableAssertions = false;
  25 static cl::opt<bool,true>
  26 ProfileVerifierDisableAssertions("profile-verifier-noassert",
  27     cl::location(DisableAssertions), cl::desc("Disable assertions"));
  28 bool PrintedDebugTree = false;
  29
  30 namespace {
  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
  62 char ProfileVerifierPass::ID = 0;
  63 static RegisterPass<ProfileVerifierPass>
  64 X("profile-verifier", "Verify profiling information", false, true);
  65
  66 namespace llvm {
  67   FunctionPass *createProfileVerifierPass() {
  68     return new ProfileVerifierPass();
  69   }
  70 }
  71
  72 #ifndef NDEBUG
  73 void 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
 119 void 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
 134 static 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) \
 148 if (C) { \
 149   if (DisableAssertions) { errs()<<(M)<<"\n"; } else { assert((!(C)) && (M)); } \
 150 }
 151
 152 #define CHECKDEBUG(C,M,D) \
 153 if (C) { \
 154   DEBUG(debugEntry(BB, BBWeight, inWeight,  inCount, \
 155                                  outWeight, outCount, (D))); \
 156   if (DisableAssertions) { errs()<<(M)<<"\n"; } else { assert((!(C)) && (M)); } \
 157 }
 158
 159 void 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
 210 bool 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 }