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