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 // This compares A and B but considering maybe small differences.
 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 // This checks if the function "exit" is reachable from an given function
 171 // via calls, this is necessary to check if a profile is valid despite the
 172 // counts not fitting exactly.
 173 bool ProfileVerifierPass::exitReachable(const Function *F) {
 174   if (!F) return false;
 175
 176   if (FisVisited.count(F)) return false;
 177
 178   Function *Exit = F->getParent()->getFunction("exit");
 179   if (Exit == F) {
 180     return true;
 181   }
 182
 183   FisVisited.insert(F);
 184   bool exits = false;
 185   for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
 186     if (const CallInst *CI = dyn_cast<CallInst>(&*I)) {
 187       exits |= exitReachable(CI->getCalledFunction());
 188       if (exits) break;
 189     }
 190   }
 191   return exits;
 192 }
 193
 194 #define ASSERTMESSAGE(M) \
 195     errs() << (M) << "\n"; \
 196     if (!DisableAssertions) assert(0 && (M));
 197
 198 double ProfileVerifierPass::ReadOrAssert(ProfileInfo::Edge E) {
 199   double EdgeWeight = PI->getEdgeWeight(E);
 200   if (EdgeWeight == ProfileInfo::MissingValue) {
 201     errs() << "Edge " << E << " in Function "
 202            << ProfileInfo::getFunction(E)->getNameStr() << ": ";
 203     ASSERTMESSAGE("ASSERT:Edge has missing value");
 204     return 0;
 205   } else {
 206     return EdgeWeight;
 207   }
 208 }
 209
 210 void ProfileVerifierPass::CheckValue(bool Error, const char *Message,
 211                                      DetailedBlockInfo *DI) {
 212   if (Error) {
 213     DEBUG(debugEntry(DI));
 214     errs() << "Block " << DI->BB->getNameStr() << " in Function "
 215            << DI->BB->getParent()->getNameStr() << ": ";
 216     ASSERTMESSAGE(Message);
 217   }
 218   return;
 219 }
 220
 221 // This calculates the Information for a block and then recurses into the
 222 // successors.
 223 void ProfileVerifierPass::recurseBasicBlock(const BasicBlock *BB) {
 224
 225   // Break the recursion by remembering all visited blocks.
 226   if (BBisVisited.find(BB) != BBisVisited.end()) return;
 227
 228   // Use a data structure to store all the information, this can then be handed
 229   // to debug printers.
 230   DetailedBlockInfo DI;
 231   DI.BB = BB;
 232   DI.outCount = DI.inCount = DI.inWeight = DI.outWeight = 0;
 233
 234   // Read predecessors.
 235   std::set<const BasicBlock*> ProcessedPreds;
 236   pred_const_iterator bpi = pred_begin(BB), bpe = pred_end(BB);
 237   // If there are none, check for (0,BB) edge.
 238   if (bpi == bpe) {
 239     DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
 240     DI.inCount++;
 241   }
 242   for (;bpi != bpe; ++bpi) {
 243     if (ProcessedPreds.insert(*bpi).second) {
 244       DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
 245       DI.inCount++;
 246     }
 247   }
 248
 249   // Read successors.
 250   std::set<const BasicBlock*> ProcessedSuccs;
 251   succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 252   // If there is an (0,BB) edge, consider it too. (This is done not only when
 253   // there are no successors, but every time; not every function contains
 254   // return blocks with no successors (think loop latch as return block)).
 255   double w = PI->getEdgeWeight(PI->getEdge(BB,0));
 256   if (w != ProfileInfo::MissingValue) {
 257     DI.outWeight += w;
 258     DI.outCount++;
 259   }
 260   for (;bbi != bbe; ++bbi) {
 261     if (ProcessedSuccs.insert(*bbi).second) {
 262       DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
 263       DI.outCount++;
 264     }
 265   }
 266
 267   // Read block weight.
 268   DI.BBWeight = PI->getExecutionCount(BB);
 269   CheckValue(DI.BBWeight == ProfileInfo::MissingValue,
 270              "ASSERT:BasicBlock has missing value", &DI);
 271
 272   // Check if this block is a setjmp target.
 273   bool isSetJmpTarget = false;
 274   if (DI.outWeight > DI.inWeight) {
 275     for (BasicBlock::const_iterator i = BB->begin(), ie = BB->end();
 276          i != ie; ++i) {
 277       if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
 278         Function *F = CI->getCalledFunction();
 279         if (F && (F->getNameStr() == "_setjmp")) {
 280           isSetJmpTarget = true; break;
 281         }
 282       }
 283     }
 284   }
 285   // Check if this block is eventually reaching exit.
 286   bool isExitReachable = false;
 287   if (DI.inWeight > DI.outWeight) {
 288     for (BasicBlock::const_iterator i = BB->begin(), ie = BB->end();
 289          i != ie; ++i) {
 290       if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
 291         FisVisited.clear();
 292         isExitReachable |= exitReachable(CI->getCalledFunction());
 293         if (isExitReachable) break;
 294       }
 295     }
 296   }
 297
 298   if (DI.inCount > 0 && DI.outCount == 0) {
 299      // If this is a block with no successors.
 300     if (!isSetJmpTarget) {
 301       CheckValue(!Equals(DI.inWeight,DI.BBWeight),
 302                  "ASSERT:inWeight and BBWeight do not match", &DI);
 303     }
 304   } else if (DI.inCount == 0 && DI.outCount > 0) {
 305     // If this is a block with no predecessors.
 306     if (!isExitReachable)
 307       CheckValue(!Equals(DI.BBWeight,DI.outWeight),
 308                  "ASSERT:BBWeight and outWeight do not match", &DI);
 309   } else {
 310     // If this block has successors and predecessors.
 311     if (DI.inWeight > DI.outWeight && !isExitReachable)
 312       CheckValue(!Equals(DI.inWeight,DI.outWeight),
 313                  "ASSERT:inWeight and outWeight do not match", &DI);
 314     if (DI.inWeight < DI.outWeight && !isSetJmpTarget)
 315       CheckValue(!Equals(DI.inWeight,DI.outWeight),
 316                  "ASSERT:inWeight and outWeight do not match", &DI);
 317   }
 318
 319
 320   // Mark this block as visited, rescurse into successors.
 321   BBisVisited.insert(BB);
 322   for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 323         bbi != bbe; ++bbi ) {
 324     recurseBasicBlock(*bbi);
 325   }
 326 }
 327
 328 bool ProfileVerifierPass::runOnFunction(Function &F) {
 329   PI = &getAnalysis<ProfileInfo>();
 330
 331   // Prepare global variables.
 332   PrintedDebugTree = false;
 333   BBisVisited.clear();
 334
 335   // Fetch entry block and recurse into it.
 336   const BasicBlock *entry = &F.getEntryBlock();
 337   recurseBasicBlock(entry);
 338
 339   if (!DisableAssertions)
 340     assert((PI->getExecutionCount(&F)==PI->getExecutionCount(entry)) &&
 341            "Function count and entry block count do not match");
 342   return false;
 343 }