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/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       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->getNameStr()                << " in "
    129            << BB->getParent()->getNameStr()               << ":"
    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->getNameStr()       << " in "
    147            << DI->BB->getParent()->getNameStr()               << ":"
    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)->getNameStr() << ": ";
    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)->getNameStr() << ": ";
    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->getNameStr() << " in Function "
    224              << DI->BB->getParent()->getNameStr() << ": ";
    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 
    383