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/Format.h"
  25 #include "llvm/Support/Debug.h"
  26 #include <set>
  27 using namespace llvm;
  28
  29 static cl::opt<bool,false>
  30 ProfileVerifierDisableAssertions("profile-verifier-noassert",
  31      cl::desc("Disable assertions"));
  32
  33 namespace llvm {
  34   template<class FType, class BType>
  35   class ProfileVerifierPassT : public FunctionPass {
  36
  37     struct DetailedBlockInfo {
  38       const BType *BB;
  39       double      BBWeight;
  40       double      inWeight;
  41       int         inCount;
  42       double      outWeight;
  43       int         outCount;
  44     };
  45
  46     ProfileInfoT<FType, BType> *PI;
  47     std::set<const BType*> BBisVisited;
  48     std::set<const FType*>   FisVisited;
  49     bool DisableAssertions;
  50
  51     // When debugging is enabled, the verifier prints a whole slew of debug
  52     // information, otherwise its just the assert. These are all the helper
  53     // functions.
  54     bool PrintedDebugTree;
  55     std::set<const BType*> BBisPrinted;
  56     void debugEntry(DetailedBlockInfo*);
  57     void printDebugInfo(const BType *BB);
  58
  59   public:
  60     static char ID; // Class identification, replacement for typeinfo
  61
  62     explicit ProfileVerifierPassT () : FunctionPass(&ID) {
  63       DisableAssertions = ProfileVerifierDisableAssertions;
  64     }
  65     explicit ProfileVerifierPassT (bool da) : FunctionPass(&ID),
  66                                               DisableAssertions(da) {
  67     }
  68
  69     void getAnalysisUsage(AnalysisUsage &AU) const {
  70       AU.setPreservesAll();
  71       AU.addRequired<ProfileInfoT<FType, BType> >();
  72     }
  73
  74     const char *getPassName() const {
  75       return "Profiling information verifier";
  76     }
  77
  78     /// run - Verify the profile information.
  79     bool runOnFunction(FType &F);
  80     void recurseBasicBlock(const BType*);
  81
  82     bool   exitReachable(const FType*);
  83     double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge);
  84     void   CheckValue(bool, const char*, DetailedBlockInfo*);
  85   };
  86
  87   typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass;
  88
  89   template<class FType, class BType>
  90   void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) {
  91
  92     if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
  93
  94     double BBWeight = PI->getExecutionCount(BB);
  95     if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; }
  96     double inWeight = 0;
  97     int inCount = 0;
  98     std::set<const BType*> ProcessedPreds;
  99     for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 100          bbi != bbe; ++bbi ) {
 101       if (ProcessedPreds.insert(*bbi).second) {
 102         typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB);
 103         double EdgeWeight = PI->getEdgeWeight(E);
 104         if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
 105         dbgs() << "calculated in-edge " << E << ": "
 106                << format("%20.20g",EdgeWeight) << "\n";
 107         inWeight += EdgeWeight;
 108         inCount++;
 109       }
 110     }
 111     double outWeight = 0;
 112     int outCount = 0;
 113     std::set<const BType*> ProcessedSuccs;
 114     for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 115           bbi != bbe; ++bbi ) {
 116       if (ProcessedSuccs.insert(*bbi).second) {
 117         typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi);
 118         double EdgeWeight = PI->getEdgeWeight(E);
 119         if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
 120         dbgs() << "calculated out-edge " << E << ": "
 121                << format("%20.20g",EdgeWeight) << "\n";
 122         outWeight += EdgeWeight;
 123         outCount++;
 124       }
 125     }
 126     dbgs() << "Block " << BB->getNameStr()                << " in "
 127            << BB->getParent()->getNameStr()               << ":"
 128            << "BBWeight="  << format("%20.20g",BBWeight)  << ","
 129            << "inWeight="  << format("%20.20g",inWeight)  << ","
 130            << "inCount="   << inCount                     << ","
 131            << "outWeight=" << format("%20.20g",outWeight) << ","
 132            << "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   template<class FType, class BType>
 143   void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) {
 144     dbgs() << "TROUBLE: Block " << DI->BB->getNameStr()       << " in "
 145            << DI->BB->getParent()->getNameStr()               << ":"
 146            << "BBWeight="  << format("%20.20g",DI->BBWeight)  << ","
 147            << "inWeight="  << format("%20.20g",DI->inWeight)  << ","
 148            << "inCount="   << DI->inCount                     << ","
 149            << "outWeight=" << format("%20.20g",DI->outWeight) << ","
 150            << "outCount="  << DI->outCount                    << "\n";
 151     if (!PrintedDebugTree) {
 152       PrintedDebugTree = true;
 153       printDebugInfo(&(DI->BB->getParent()->getEntryBlock()));
 154     }
 155   }
 156
 157   // This compares A and B for equality.
 158   static bool Equals(double A, double B) {
 159     return A == B;
 160   }
 161
 162   // This checks if the function "exit" is reachable from an given function
 163   // via calls, this is necessary to check if a profile is valid despite the
 164   // counts not fitting exactly.
 165   template<class FType, class BType>
 166   bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) {
 167     if (!F) return false;
 168
 169     if (FisVisited.count(F)) return false;
 170
 171     FType *Exit = F->getParent()->getFunction("exit");
 172     if (Exit == F) {
 173       return true;
 174     }
 175
 176     FisVisited.insert(F);
 177     bool exits = false;
 178     for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
 179       if (const CallInst *CI = dyn_cast<CallInst>(&*I)) {
 180         FType *F = CI->getCalledFunction();
 181         if (F) {
 182           exits |= exitReachable(F);
 183         } else {
 184           // This is a call to a pointer, all bets are off...
 185           exits = true;
 186         }
 187         if (exits) break;
 188       }
 189     }
 190     return exits;
 191   }
 192
 193   #define ASSERTMESSAGE(M) \
 194     { dbgs() << "ASSERT:" << (M) << "\n"; \
 195       if (!DisableAssertions) assert(0 && (M)); }
 196
 197   template<class FType, class BType>
 198   double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) {
 199     double EdgeWeight = PI->getEdgeWeight(E);
 200     if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) {
 201       dbgs() << "Edge " << E << " in Function "
 202              << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
 203       ASSERTMESSAGE("Edge has missing value");
 204       return 0;
 205     } else {
 206       if (EdgeWeight < 0) {
 207         dbgs() << "Edge " << E << " in Function "
 208                << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
 209         ASSERTMESSAGE("Edge has negative value");
 210       }
 211       return EdgeWeight;
 212     }
 213   }
 214
 215   template<class FType, class BType>
 216   void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error,
 217                                                       const char *Message,
 218                                                       DetailedBlockInfo *DI) {
 219     if (Error) {
 220       DEBUG(debugEntry(DI));
 221       dbgs() << "Block " << DI->BB->getNameStr() << " in Function "
 222              << DI->BB->getParent()->getNameStr() << ": ";
 223       ASSERTMESSAGE(Message);
 224     }
 225     return;
 226   }
 227
 228   // This calculates the Information for a block and then recurses into the
 229   // successors.
 230   template<class FType, class BType>
 231   void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) {
 232
 233     // Break the recursion by remembering all visited blocks.
 234     if (BBisVisited.find(BB) != BBisVisited.end()) return;
 235
 236     // Use a data structure to store all the information, this can then be handed
 237     // to debug printers.
 238     DetailedBlockInfo DI;
 239     DI.BB = BB;
 240     DI.outCount = DI.inCount = 0;
 241     DI.inWeight = DI.outWeight = 0;
 242
 243     // Read predecessors.
 244     std::set<const BType*> ProcessedPreds;
 245     const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB);
 246     // If there are none, check for (0,BB) edge.
 247     if (bpi == bpe) {
 248       DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
 249       DI.inCount++;
 250     }
 251     for (;bpi != bpe; ++bpi) {
 252       if (ProcessedPreds.insert(*bpi).second) {
 253         DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
 254         DI.inCount++;
 255       }
 256     }
 257
 258     // Read successors.
 259     std::set<const BType*> ProcessedSuccs;
 260     succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 261     // If there is an (0,BB) edge, consider it too. (This is done not only when
 262     // there are no successors, but every time; not every function contains
 263     // return blocks with no successors (think loop latch as return block)).
 264     double w = PI->getEdgeWeight(PI->getEdge(BB,0));
 265     if (w != ProfileInfoT<FType, BType>::MissingValue) {
 266       DI.outWeight += w;
 267       DI.outCount++;
 268     }
 269     for (;bbi != bbe; ++bbi) {
 270       if (ProcessedSuccs.insert(*bbi).second) {
 271         DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
 272         DI.outCount++;
 273       }
 274     }
 275
 276     // Read block weight.
 277     DI.BBWeight = PI->getExecutionCount(BB);
 278     CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue,
 279                "BasicBlock has missing value", &DI);
 280     CheckValue(DI.BBWeight < 0,
 281                "BasicBlock has negative value", &DI);
 282
 283     // Check if this block is a setjmp target.
 284     bool isSetJmpTarget = false;
 285     if (DI.outWeight > DI.inWeight) {
 286       for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
 287            i != ie; ++i) {
 288         if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
 289           FType *F = CI->getCalledFunction();
 290           if (F && (F->getNameStr() == "_setjmp")) {
 291             isSetJmpTarget = true; break;
 292           }
 293         }
 294       }
 295     }
 296     // Check if this block is eventually reaching exit.
 297     bool isExitReachable = false;
 298     if (DI.inWeight > DI.outWeight) {
 299       for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
 300            i != ie; ++i) {
 301         if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
 302           FType *F = CI->getCalledFunction();
 303           if (F) {
 304             FisVisited.clear();
 305             isExitReachable |= exitReachable(F);
 306           } else {
 307             // This is a call to a pointer, all bets are off...
 308             isExitReachable = true;
 309           }
 310           if (isExitReachable) break;
 311         }
 312       }
 313     }
 314
 315     if (DI.inCount > 0 && DI.outCount == 0) {
 316        // If this is a block with no successors.
 317       if (!isSetJmpTarget) {
 318         CheckValue(!Equals(DI.inWeight,DI.BBWeight),
 319                    "inWeight and BBWeight do not match", &DI);
 320       }
 321     } else if (DI.inCount == 0 && DI.outCount > 0) {
 322       // If this is a block with no predecessors.
 323       if (!isExitReachable)
 324         CheckValue(!Equals(DI.BBWeight,DI.outWeight),
 325                    "BBWeight and outWeight do not match", &DI);
 326     } else {
 327       // If this block has successors and predecessors.
 328       if (DI.inWeight > DI.outWeight && !isExitReachable)
 329         CheckValue(!Equals(DI.inWeight,DI.outWeight),
 330                    "inWeight and outWeight do not match", &DI);
 331       if (DI.inWeight < DI.outWeight && !isSetJmpTarget)
 332         CheckValue(!Equals(DI.inWeight,DI.outWeight),
 333                    "inWeight and outWeight do not match", &DI);
 334     }
 335
 336
 337     // Mark this block as visited, rescurse into successors.
 338     BBisVisited.insert(BB);
 339     for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 340           bbi != bbe; ++bbi ) {
 341       recurseBasicBlock(*bbi);
 342     }
 343   }
 344
 345   template<class FType, class BType>
 346   bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) {
 347     PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >();
 348     if (!PI)
 349       ASSERTMESSAGE("No ProfileInfo available");
 350
 351     // Prepare global variables.
 352     PrintedDebugTree = false;
 353     BBisVisited.clear();
 354
 355     // Fetch entry block and recurse into it.
 356     const BType *entry = &F.getEntryBlock();
 357     recurseBasicBlock(entry);
 358
 359     if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry))
 360       ASSERTMESSAGE("Function count and entry block count do not match");
 361
 362     return false;
 363   }
 364
 365   template<class FType, class BType>
 366   char ProfileVerifierPassT<FType, BType>::ID = 0;
 367 }
 368
 369 static RegisterPass<ProfileVerifierPass>
 370 X("profile-verifier", "Verify profiling information", false, true);
 371
 372 namespace llvm {
 373   FunctionPass *createProfileVerifierPass() {
 374     return new ProfileVerifierPass(ProfileVerifierDisableAssertions);
 375   }
 376 }
 377