Home | History | Annotate | Download | only in Analysis 
      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 
    384