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/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>
  26 using namespace llvm;
  27
  28 static cl::opt<bool,false>
  29 ProfileVerifierDisableAssertions("profile-verifier-noassert",
  30      cl::desc("Disable assertions"));
  31
  32 namespace {
  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
  86 char ProfileVerifierPass::ID = 0;
  87 static RegisterPass<ProfileVerifierPass>
  88 X("profile-verifier", "Verify profiling information", false, true);
  89
  90 namespace llvm {
  91   FunctionPass *createProfileVerifierPass() {
  92     return new ProfileVerifierPass(ProfileVerifierDisableAssertions);
  93   }
  94 }
  95
  96 void 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
 142 void 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 // compare with relative error
 157 static 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 bool ProfileVerifierPass::exitReachable(const Function *F) {
 171   if (!F) return false;
 172
 173   if (FisVisited.count(F)) return false;
 174
 175   Function *Exit = F->getParent()->getFunction("exit");
 176   if (Exit == F) {
 177     return true;
 178   }
 179
 180   FisVisited.insert(F);
 181   bool exits = false;
 182   for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
 183     if (const CallInst *CI = dyn_cast<CallInst>(&*I)) {
 184       exits |= exitReachable(CI->getCalledFunction());
 185       if (exits) break;
 186     }
 187   }
 188   return exits;
 189 }
 190
 191 #define ASSERTMESSAGE(M) \
 192     errs() << (M) << "\n"; \
 193     if (!DisableAssertions) assert(0 && (M));
 194
 195 double ProfileVerifierPass::ReadOrAssert(ProfileInfo::Edge E) {
 196   double EdgeWeight = PI->getEdgeWeight(E);
 197   if (EdgeWeight == ProfileInfo::MissingValue) {
 198     errs() << "Edge " << E << " in Function "
 199            << E.first->getParent()->getNameStr() << ": ";
 200     ASSERTMESSAGE("ASSERT:Edge has missing value");
 201     return 0;
 202   } else {
 203     return EdgeWeight;
 204   }
 205 }
 206
 207 void ProfileVerifierPass::CheckValue(bool Error, const char *Message,
 208                                      DetailedBlockInfo *DI) {
 209   if (Error) {
 210     DEBUG(debugEntry(DI));
 211     errs() << "Block " << DI->BB->getNameStr() << " in Function "
 212            << DI->BB->getParent()->getNameStr() << ": ";
 213     ASSERTMESSAGE(Message);
 214   }
 215   return;
 216 }
 217
 218 void ProfileVerifierPass::recurseBasicBlock(const BasicBlock *BB) {
 219
 220   if (BBisVisited.find(BB) != BBisVisited.end()) return;
 221
 222   DetailedBlockInfo DI;
 223   DI.BB = BB;
 224   DI.outCount = DI.inCount = DI.inWeight = DI.outWeight = 0;
 225   std::set<const BasicBlock*> ProcessedPreds;
 226   pred_const_iterator bpi = pred_begin(BB), bpe = pred_end(BB);
 227   if (bpi == bpe) {
 228     DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
 229     DI.inCount++;
 230   }
 231   for (;bpi != bpe; ++bpi) {
 232     if (ProcessedPreds.insert(*bpi).second) {
 233       DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
 234       DI.inCount++;
 235     }
 236   }
 237
 238   std::set<const BasicBlock*> ProcessedSuccs;
 239   succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 240   if (bbi == bbe) {
 241     double w = PI->getEdgeWeight(PI->getEdge(BB,0));
 242     if (w != ProfileInfo::MissingValue) {
 243       DI.outWeight += w;
 244       DI.outCount++;
 245     }
 246   }
 247   for (;bbi != bbe; ++bbi) {
 248     if (ProcessedSuccs.insert(*bbi).second) {
 249       DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
 250       DI.outCount++;
 251     }
 252   }
 253
 254   DI.BBWeight = PI->getExecutionCount(BB);
 255   CheckValue(DI.BBWeight == ProfileInfo::MissingValue,
 256              "ASSERT:BasicBlock has missing value", &DI);
 257
 258   // Check if this block is a setjmp target.
 259   bool isSetJmpTarget = false;
 260   if (DI.outWeight > DI.inWeight) {
 261     for (BasicBlock::const_iterator i = BB->begin(), ie = BB->end();
 262          i != ie; ++i) {
 263       if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
 264         Function *F = CI->getCalledFunction();
 265         if (F && (F->getNameStr() == "_setjmp")) {
 266           isSetJmpTarget = true; break;
 267         }
 268       }
 269     }
 270   }
 271   // Check if this block is eventually reaching exit.
 272   bool isExitReachable = false;
 273   if (DI.inWeight > DI.outWeight) {
 274     for (BasicBlock::const_iterator i = BB->begin(), ie = BB->end();
 275          i != ie; ++i) {
 276       if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
 277         FisVisited.clear();
 278         isExitReachable |= exitReachable(CI->getCalledFunction());
 279         if (isExitReachable) break;
 280       }
 281     }
 282   }
 283
 284   if (DI.inCount > 0 && DI.outCount == 0) {
 285      // If this is a block with no successors.
 286     if (!isSetJmpTarget) {
 287       CheckValue(!Equals(DI.inWeight,DI.BBWeight),
 288                  "ASSERT:inWeight and BBWeight do not match", &DI);
 289     }
 290   } else if (DI.inCount == 0 && DI.outCount > 0) {
 291     // If this is a block with no predecessors.
 292     if (!isExitReachable)
 293       CheckValue(!Equals(DI.BBWeight,DI.outWeight),
 294                  "ASSERT:BBWeight and outWeight do not match", &DI);
 295   } else {
 296     // If this block has successors and predecessors.
 297     if (DI.inWeight > DI.outWeight && !isExitReachable)
 298       CheckValue(!Equals(DI.inWeight,DI.outWeight),
 299                  "ASSERT:inWeight and outWeight do not match", &DI);
 300     if (DI.inWeight < DI.outWeight && !isSetJmpTarget)
 301       CheckValue(!Equals(DI.inWeight,DI.outWeight),
 302                  "ASSERT:inWeight and outWeight do not match", &DI);
 303   }
 304
 305
 306   // mark as visited and recurse into subnodes
 307   BBisVisited.insert(BB);
 308   for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 309         bbi != bbe; ++bbi ) {
 310     recurseBasicBlock(*bbi);
 311   }
 312 }
 313
 314 bool ProfileVerifierPass::runOnFunction(Function &F) {
 315   PI = &getAnalysis<ProfileInfo>();
 316
 317   if (PI->getExecutionCount(&F) == ProfileInfo::MissingValue) {
 318     DEBUG(errs() << "Function " << F.getNameStr() << " has no profile\n");
 319     return false;
 320   }
 321
 322   PrintedDebugTree = false;
 323   BBisVisited.clear();
 324
 325   const BasicBlock *entry = &F.getEntryBlock();
 326   recurseBasicBlock(entry);
 327
 328   if (!DisableAssertions)
 329     assert((PI->getExecutionCount(&F)==PI->getExecutionCount(entry)) &&
 330            "Function count and entry block count do not match");
 331   return false;
 332 }