| //===- ProfileVerifierPass.cpp - LLVM Pass to estimate profile info -------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements a pass that checks profiling information for |
| // plausibility. |
| // |
| //===----------------------------------------------------------------------===// |
| #define DEBUG_TYPE "profile-verifier" |
| #include "llvm/Analysis/Passes.h" |
| #include "llvm/Analysis/ProfileInfo.h" |
| #include "llvm/Instructions.h" |
| #include "llvm/Module.h" |
| #include "llvm/Pass.h" |
| #include "llvm/Support/CFG.h" |
| #include "llvm/Support/CallSite.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/Format.h" |
| #include "llvm/Support/InstIterator.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <set> |
| using namespace llvm; |
| |
| static cl::opt<bool,false> |
| ProfileVerifierDisableAssertions("profile-verifier-noassert", |
| cl::desc("Disable assertions")); |
| |
| namespace { |
| template<class FType, class BType> |
| class ProfileVerifierPassT : public FunctionPass { |
| |
| struct DetailedBlockInfo { |
| const BType *BB; |
| double BBWeight; |
| double inWeight; |
| int inCount; |
| double outWeight; |
| int outCount; |
| }; |
| |
| ProfileInfoT<FType, BType> *PI; |
| std::set<const BType*> BBisVisited; |
| std::set<const FType*> FisVisited; |
| bool DisableAssertions; |
| |
| // When debugging is enabled, the verifier prints a whole slew of debug |
| // information, otherwise its just the assert. These are all the helper |
| // functions. |
| bool PrintedDebugTree; |
| std::set<const BType*> BBisPrinted; |
| void debugEntry(DetailedBlockInfo*); |
| void printDebugInfo(const BType *BB); |
| |
| public: |
| static char ID; // Class identification, replacement for typeinfo |
| |
| explicit ProfileVerifierPassT () : FunctionPass(ID) { |
| initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry()); |
| DisableAssertions = ProfileVerifierDisableAssertions; |
| } |
| explicit ProfileVerifierPassT (bool da) : FunctionPass(ID), |
| DisableAssertions(da) { |
| initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.setPreservesAll(); |
| AU.addRequired<ProfileInfoT<FType, BType> >(); |
| } |
| |
| const char *getPassName() const { |
| return "Profiling information verifier"; |
| } |
| |
| /// run - Verify the profile information. |
| bool runOnFunction(FType &F); |
| void recurseBasicBlock(const BType*); |
| |
| bool exitReachable(const FType*); |
| double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge); |
| void CheckValue(bool, const char*, DetailedBlockInfo*); |
| }; |
| |
| typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass; |
| |
| template<class FType, class BType> |
| void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) { |
| |
| if (BBisPrinted.find(BB) != BBisPrinted.end()) return; |
| |
| double BBWeight = PI->getExecutionCount(BB); |
| if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; } |
| double inWeight = 0; |
| int inCount = 0; |
| std::set<const BType*> ProcessedPreds; |
| for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); |
| bbi != bbe; ++bbi ) { |
| if (ProcessedPreds.insert(*bbi).second) { |
| typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB); |
| double EdgeWeight = PI->getEdgeWeight(E); |
| if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; } |
| dbgs() << "calculated in-edge " << E << ": " |
| << format("%20.20g",EdgeWeight) << "\n"; |
| inWeight += EdgeWeight; |
| inCount++; |
| } |
| } |
| double outWeight = 0; |
| int outCount = 0; |
| std::set<const BType*> ProcessedSuccs; |
| for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); |
| bbi != bbe; ++bbi ) { |
| if (ProcessedSuccs.insert(*bbi).second) { |
| typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi); |
| double EdgeWeight = PI->getEdgeWeight(E); |
| if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; } |
| dbgs() << "calculated out-edge " << E << ": " |
| << format("%20.20g",EdgeWeight) << "\n"; |
| outWeight += EdgeWeight; |
| outCount++; |
| } |
| } |
| dbgs() << "Block " << BB->getName() << " in " |
| << BB->getParent()->getName() << ":" |
| << "BBWeight=" << format("%20.20g",BBWeight) << "," |
| << "inWeight=" << format("%20.20g",inWeight) << "," |
| << "inCount=" << inCount << "," |
| << "outWeight=" << format("%20.20g",outWeight) << "," |
| << "outCount" << outCount << "\n"; |
| |
| // mark as visited and recurse into subnodes |
| BBisPrinted.insert(BB); |
| for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); |
| bbi != bbe; ++bbi ) { |
| printDebugInfo(*bbi); |
| } |
| } |
| |
| template<class FType, class BType> |
| void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) { |
| dbgs() << "TROUBLE: Block " << DI->BB->getName() << " in " |
| << DI->BB->getParent()->getName() << ":" |
| << "BBWeight=" << format("%20.20g",DI->BBWeight) << "," |
| << "inWeight=" << format("%20.20g",DI->inWeight) << "," |
| << "inCount=" << DI->inCount << "," |
| << "outWeight=" << format("%20.20g",DI->outWeight) << "," |
| << "outCount=" << DI->outCount << "\n"; |
| if (!PrintedDebugTree) { |
| PrintedDebugTree = true; |
| printDebugInfo(&(DI->BB->getParent()->getEntryBlock())); |
| } |
| } |
| |
| // This compares A and B for equality. |
| static bool Equals(double A, double B) { |
| return A == B; |
| } |
| |
| // This checks if the function "exit" is reachable from an given function |
| // via calls, this is necessary to check if a profile is valid despite the |
| // counts not fitting exactly. |
| template<class FType, class BType> |
| bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) { |
| if (!F) return false; |
| |
| if (FisVisited.count(F)) return false; |
| |
| FType *Exit = F->getParent()->getFunction("exit"); |
| if (Exit == F) { |
| return true; |
| } |
| |
| FisVisited.insert(F); |
| bool exits = false; |
| for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { |
| if (const CallInst *CI = dyn_cast<CallInst>(&*I)) { |
| FType *F = CI->getCalledFunction(); |
| if (F) { |
| exits |= exitReachable(F); |
| } else { |
| // This is a call to a pointer, all bets are off... |
| exits = true; |
| } |
| if (exits) break; |
| } |
| } |
| return exits; |
| } |
| |
| #define ASSERTMESSAGE(M) \ |
| { dbgs() << "ASSERT:" << (M) << "\n"; \ |
| if (!DisableAssertions) assert(0 && (M)); } |
| |
| template<class FType, class BType> |
| double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) { |
| double EdgeWeight = PI->getEdgeWeight(E); |
| if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { |
| dbgs() << "Edge " << E << " in Function " |
| << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": "; |
| ASSERTMESSAGE("Edge has missing value"); |
| return 0; |
| } else { |
| if (EdgeWeight < 0) { |
| dbgs() << "Edge " << E << " in Function " |
| << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": "; |
| ASSERTMESSAGE("Edge has negative value"); |
| } |
| return EdgeWeight; |
| } |
| } |
| |
| template<class FType, class BType> |
| void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error, |
| const char *Message, |
| DetailedBlockInfo *DI) { |
| if (Error) { |
| DEBUG(debugEntry(DI)); |
| dbgs() << "Block " << DI->BB->getName() << " in Function " |
| << DI->BB->getParent()->getName() << ": "; |
| ASSERTMESSAGE(Message); |
| } |
| return; |
| } |
| |
| // This calculates the Information for a block and then recurses into the |
| // successors. |
| template<class FType, class BType> |
| void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) { |
| |
| // Break the recursion by remembering all visited blocks. |
| if (BBisVisited.find(BB) != BBisVisited.end()) return; |
| |
| // Use a data structure to store all the information, this can then be handed |
| // to debug printers. |
| DetailedBlockInfo DI; |
| DI.BB = BB; |
| DI.outCount = DI.inCount = 0; |
| DI.inWeight = DI.outWeight = 0; |
| |
| // Read predecessors. |
| std::set<const BType*> ProcessedPreds; |
| const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB); |
| // If there are none, check for (0,BB) edge. |
| if (bpi == bpe) { |
| DI.inWeight += ReadOrAssert(PI->getEdge(0,BB)); |
| DI.inCount++; |
| } |
| for (;bpi != bpe; ++bpi) { |
| if (ProcessedPreds.insert(*bpi).second) { |
| DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB)); |
| DI.inCount++; |
| } |
| } |
| |
| // Read successors. |
| std::set<const BType*> ProcessedSuccs; |
| succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); |
| // If there is an (0,BB) edge, consider it too. (This is done not only when |
| // there are no successors, but every time; not every function contains |
| // return blocks with no successors (think loop latch as return block)). |
| double w = PI->getEdgeWeight(PI->getEdge(BB,0)); |
| if (w != ProfileInfoT<FType, BType>::MissingValue) { |
| DI.outWeight += w; |
| DI.outCount++; |
| } |
| for (;bbi != bbe; ++bbi) { |
| if (ProcessedSuccs.insert(*bbi).second) { |
| DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi)); |
| DI.outCount++; |
| } |
| } |
| |
| // Read block weight. |
| DI.BBWeight = PI->getExecutionCount(BB); |
| CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue, |
| "BasicBlock has missing value", &DI); |
| CheckValue(DI.BBWeight < 0, |
| "BasicBlock has negative value", &DI); |
| |
| // Check if this block is a setjmp target. |
| bool isSetJmpTarget = false; |
| if (DI.outWeight > DI.inWeight) { |
| for (typename BType::const_iterator i = BB->begin(), ie = BB->end(); |
| i != ie; ++i) { |
| if (const CallInst *CI = dyn_cast<CallInst>(&*i)) { |
| FType *F = CI->getCalledFunction(); |
| if (F && (F->getName() == "_setjmp")) { |
| isSetJmpTarget = true; break; |
| } |
| } |
| } |
| } |
| // Check if this block is eventually reaching exit. |
| bool isExitReachable = false; |
| if (DI.inWeight > DI.outWeight) { |
| for (typename BType::const_iterator i = BB->begin(), ie = BB->end(); |
| i != ie; ++i) { |
| if (const CallInst *CI = dyn_cast<CallInst>(&*i)) { |
| FType *F = CI->getCalledFunction(); |
| if (F) { |
| FisVisited.clear(); |
| isExitReachable |= exitReachable(F); |
| } else { |
| // This is a call to a pointer, all bets are off... |
| isExitReachable = true; |
| } |
| if (isExitReachable) break; |
| } |
| } |
| } |
| |
| if (DI.inCount > 0 && DI.outCount == 0) { |
| // If this is a block with no successors. |
| if (!isSetJmpTarget) { |
| CheckValue(!Equals(DI.inWeight,DI.BBWeight), |
| "inWeight and BBWeight do not match", &DI); |
| } |
| } else if (DI.inCount == 0 && DI.outCount > 0) { |
| // If this is a block with no predecessors. |
| if (!isExitReachable) |
| CheckValue(!Equals(DI.BBWeight,DI.outWeight), |
| "BBWeight and outWeight do not match", &DI); |
| } else { |
| // If this block has successors and predecessors. |
| if (DI.inWeight > DI.outWeight && !isExitReachable) |
| CheckValue(!Equals(DI.inWeight,DI.outWeight), |
| "inWeight and outWeight do not match", &DI); |
| if (DI.inWeight < DI.outWeight && !isSetJmpTarget) |
| CheckValue(!Equals(DI.inWeight,DI.outWeight), |
| "inWeight and outWeight do not match", &DI); |
| } |
| |
| |
| // Mark this block as visited, rescurse into successors. |
| BBisVisited.insert(BB); |
| for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); |
| bbi != bbe; ++bbi ) { |
| recurseBasicBlock(*bbi); |
| } |
| } |
| |
| template<class FType, class BType> |
| bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) { |
| PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >(); |
| if (!PI) |
| ASSERTMESSAGE("No ProfileInfo available"); |
| |
| // Prepare global variables. |
| PrintedDebugTree = false; |
| BBisVisited.clear(); |
| |
| // Fetch entry block and recurse into it. |
| const BType *entry = &F.getEntryBlock(); |
| recurseBasicBlock(entry); |
| |
| if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry)) |
| ASSERTMESSAGE("Function count and entry block count do not match"); |
| |
| return false; |
| } |
| |
| template<class FType, class BType> |
| char ProfileVerifierPassT<FType, BType>::ID = 0; |
| } |
| |
| INITIALIZE_PASS_BEGIN(ProfileVerifierPass, "profile-verifier", |
| "Verify profiling information", false, true) |
| INITIALIZE_AG_DEPENDENCY(ProfileInfo) |
| INITIALIZE_PASS_END(ProfileVerifierPass, "profile-verifier", |
| "Verify profiling information", false, true) |
| |
| namespace llvm { |
| FunctionPass *createProfileVerifierPass() { |
| return new ProfileVerifierPass(ProfileVerifierDisableAssertions); |
| } |
| } |
| |
