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 cl::opt<bool,true>
  25 ProfileVerifierDisableAssertions("profile-verifier-noassert",
  26      cl::desc("Disable assertions"));
  27
  28 namespace {
  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
  77 char ProfileVerifierPass::ID = 0;
  78 static RegisterPass<ProfileVerifierPass>
  79 X("profile-verifier", "Verify profiling information", false, true);
  80
  81 namespace llvm {
  82   FunctionPass *createProfileVerifierPass() {
  83     return new ProfileVerifierPass(ProfileVerifierDisableAssertions);
  84   }
  85 }
  86
  87 void 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
 133 void 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
 148 static 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
 161 double 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
 177 void 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
 189 void 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
 232 bool 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 }