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