1e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter//===- ProfileVerifierPass.cpp - LLVM Pass to estimate profile info -------===// 2e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// 3e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// The LLVM Compiler Infrastructure 4e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// 5e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// This file is distributed under the University of Illinois Open Source 6e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// License. See LICENSE.TXT for details. 7e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// 8e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter//===----------------------------------------------------------------------===// 9e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// 10e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// This file implements a pass that checks profiling information for 11e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// plausibility. 12e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter// 13e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter//===----------------------------------------------------------------------===// 14e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#define DEBUG_TYPE "profile-verifier" 1543b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter#include "llvm/Instructions.h" 1643b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter#include "llvm/Module.h" 17e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#include "llvm/Pass.h" 18e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 19e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#include "llvm/Support/CommandLine.h" 2043b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter#include "llvm/Support/CallSite.h" 21e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#include "llvm/Support/CFG.h" 2243b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter#include "llvm/Support/InstIterator.h" 23e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#include "llvm/Support/raw_ostream.h" 248c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter#include "llvm/Support/Format.h" 25e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#include "llvm/Support/Debug.h" 26e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter#include <set> 27e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifterusing namespace llvm; 28e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 2943b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifterstatic cl::opt<bool,false> 30e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas NeustifterProfileVerifierDisableAssertions("profile-verifier-noassert", 31e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter cl::desc("Disable assertions")); 32e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 330861f5793a1834f02b522fb86fb037cd592c134fBenjamin Kramernamespace { 348c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 358c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter class ProfileVerifierPassT : public FunctionPass { 36e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter 37e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter struct DetailedBlockInfo { 388c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter const BType *BB; 398c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double BBWeight; 408c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double inWeight; 418c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter int inCount; 428c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double outWeight; 438c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter int outCount; 44e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter }; 45e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter 468c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter ProfileInfoT<FType, BType> *PI; 478c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter std::set<const BType*> BBisVisited; 488c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter std::set<const FType*> FisVisited; 49e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter bool DisableAssertions; 50e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter 51e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter // When debugging is enabled, the verifier prints a whole slew of debug 52e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter // information, otherwise its just the assert. These are all the helper 53e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter // functions. 54e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter bool PrintedDebugTree; 558c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter std::set<const BType*> BBisPrinted; 56e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter void debugEntry(DetailedBlockInfo*); 578c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter void printDebugInfo(const BType *BB); 58e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter 59e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter public: 60e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter static char ID; // Class identification, replacement for typeinfo 61e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 6290c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson explicit ProfileVerifierPassT () : FunctionPass(ID) { 63081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry()); 6443b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter DisableAssertions = ProfileVerifierDisableAssertions; 6543b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 6690c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson explicit ProfileVerifierPassT (bool da) : FunctionPass(ID), 678c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DisableAssertions(da) { 68081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry()); 69e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 70e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 71e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter void getAnalysisUsage(AnalysisUsage &AU) const { 72e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter AU.setPreservesAll(); 738c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter AU.addRequired<ProfileInfoT<FType, BType> >(); 74e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 75e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 76e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter const char *getPassName() const { 77e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter return "Profiling information verifier"; 78e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 79e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 80e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter /// run - Verify the profile information. 818c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bool runOnFunction(FType &F); 828c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter void recurseBasicBlock(const BType*); 83e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter 848c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bool exitReachable(const FType*); 858c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge); 86e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter void CheckValue(bool, const char*, DetailedBlockInfo*); 87e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter }; 88e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 898c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass; 908c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 918c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 928c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) { 938c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 948c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (BBisPrinted.find(BB) != BBisPrinted.end()) return; 958c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 968c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double BBWeight = PI->getExecutionCount(BB); 978c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; } 988c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double inWeight = 0; 998c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter int inCount = 0; 1008c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter std::set<const BType*> ProcessedPreds; 10144424646ac9db5c4d3919462bd0831ec22783085Gabor Greif for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); 10244424646ac9db5c4d3919462bd0831ec22783085Gabor Greif bbi != bbe; ++bbi ) { 1038c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (ProcessedPreds.insert(*bbi).second) { 1048c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB); 1058c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double EdgeWeight = PI->getEdgeWeight(E); 1068c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; } 1073b519f62fcf1d38ef9c6478c1d5fce19bcb36282David Greene dbgs() << "calculated in-edge " << E << ": " 1088c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << format("%20.20g",EdgeWeight) << "\n"; 1098c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter inWeight += EdgeWeight; 1108c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter inCount++; 1118c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 112e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 1138c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double outWeight = 0; 1148c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter int outCount = 0; 1158c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter std::set<const BType*> ProcessedSuccs; 1168c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 1178c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bbi != bbe; ++bbi ) { 1188c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (ProcessedSuccs.insert(*bbi).second) { 1198c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi); 1208c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double EdgeWeight = PI->getEdgeWeight(E); 1218c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; } 1223b519f62fcf1d38ef9c6478c1d5fce19bcb36282David Greene dbgs() << "calculated out-edge " << E << ": " 1238c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << format("%20.20g",EdgeWeight) << "\n"; 1248c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter outWeight += EdgeWeight; 1258c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter outCount++; 1268c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 1278c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 128a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer dbgs() << "Block " << BB->getName() << " in " 129a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << BB->getParent()->getName() << ":" 1308c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "BBWeight=" << format("%20.20g",BBWeight) << "," 1318c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "inWeight=" << format("%20.20g",inWeight) << "," 1328c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "inCount=" << inCount << "," 1338c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "outWeight=" << format("%20.20g",outWeight) << "," 1348c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "outCount" << outCount << "\n"; 1358c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 1368c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // mark as visited and recurse into subnodes 1378c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter BBisPrinted.insert(BB); 1388c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 1398c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bbi != bbe; ++bbi ) { 1408c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter printDebugInfo(*bbi); 141e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 142e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 143e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 1448c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 1458c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) { 146a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer dbgs() << "TROUBLE: Block " << DI->BB->getName() << " in " 147a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << DI->BB->getParent()->getName() << ":" 1488c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "BBWeight=" << format("%20.20g",DI->BBWeight) << "," 1498c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "inWeight=" << format("%20.20g",DI->inWeight) << "," 1508c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "inCount=" << DI->inCount << "," 1518c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "outWeight=" << format("%20.20g",DI->outWeight) << "," 1528c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter << "outCount=" << DI->outCount << "\n"; 1538c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (!PrintedDebugTree) { 1548c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter PrintedDebugTree = true; 1558c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter printDebugInfo(&(DI->BB->getParent()->getEntryBlock())); 1568c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 157e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 158e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 1598c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // This compares A and B for equality. 1608c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter static bool Equals(double A, double B) { 1618c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return A == B; 1628c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 163e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 1648c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // This checks if the function "exit" is reachable from an given function 1658c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // via calls, this is necessary to check if a profile is valid despite the 1668c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // counts not fitting exactly. 1678c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 1688c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) { 1698c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (!F) return false; 17043b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter 1718c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (FisVisited.count(F)) return false; 17243b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter 1738c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter FType *Exit = F->getParent()->getFunction("exit"); 1748c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (Exit == F) { 1758c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return true; 1768c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 17743b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter 1788c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter FisVisited.insert(F); 1798c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bool exits = false; 1808c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 1818c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (const CallInst *CI = dyn_cast<CallInst>(&*I)) { 1828c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter FType *F = CI->getCalledFunction(); 1838c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (F) { 1848c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter exits |= exitReachable(F); 1858c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } else { 1868c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // This is a call to a pointer, all bets are off... 1878c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter exits = true; 1888c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 1898c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (exits) break; 1908c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 19143b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 1928c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return exits; 19343b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 19443b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter 1958c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter #define ASSERTMESSAGE(M) \ 1963b519f62fcf1d38ef9c6478c1d5fce19bcb36282David Greene { dbgs() << "ASSERT:" << (M) << "\n"; \ 1978c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (!DisableAssertions) assert(0 && (M)); } 1988c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 1998c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 2008c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) { 2018c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double EdgeWeight = PI->getEdgeWeight(E); 2028c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { 2033b519f62fcf1d38ef9c6478c1d5fce19bcb36282David Greene dbgs() << "Edge " << E << " in Function " 204a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": "; 2058c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter ASSERTMESSAGE("Edge has missing value"); 2068c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return 0; 2078c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } else { 2088c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (EdgeWeight < 0) { 2093b519f62fcf1d38ef9c6478c1d5fce19bcb36282David Greene dbgs() << "Edge " << E << " in Function " 210a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": "; 2118c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter ASSERTMESSAGE("Edge has negative value"); 2128c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 2138c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return EdgeWeight; 2148c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 215e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter } 216e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 2178c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 2188c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error, 2198c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter const char *Message, 2208c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DetailedBlockInfo *DI) { 2218c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (Error) { 2228c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DEBUG(debugEntry(DI)); 223a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer dbgs() << "Block " << DI->BB->getName() << " in Function " 224a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << DI->BB->getParent()->getName() << ": "; 2258c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter ASSERTMESSAGE(Message); 2268c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 2278c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return; 228e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter } 229e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 2308c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // This calculates the Information for a block and then recurses into the 2318c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // successors. 2328c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 2338c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) { 2348c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 2358c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Break the recursion by remembering all visited blocks. 2368c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (BBisVisited.find(BB) != BBisVisited.end()) return; 2378c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 2388c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Use a data structure to store all the information, this can then be handed 2398c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // to debug printers. 2408c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DetailedBlockInfo DI; 2418c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.BB = BB; 2428c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.outCount = DI.inCount = 0; 2438c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.inWeight = DI.outWeight = 0; 2448c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 2458c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Read predecessors. 2468c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter std::set<const BType*> ProcessedPreds; 24744424646ac9db5c4d3919462bd0831ec22783085Gabor Greif const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB); 2488c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // If there are none, check for (0,BB) edge. 2498c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (bpi == bpe) { 2508c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.inWeight += ReadOrAssert(PI->getEdge(0,BB)); 251e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter DI.inCount++; 252e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 2538c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for (;bpi != bpe; ++bpi) { 2548c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (ProcessedPreds.insert(*bpi).second) { 2558c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB)); 2568c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.inCount++; 2578c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 2588c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 259e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 2608c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Read successors. 2618c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter std::set<const BType*> ProcessedSuccs; 2628c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 2638c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // If there is an (0,BB) edge, consider it too. (This is done not only when 2648c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // there are no successors, but every time; not every function contains 2658c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // return blocks with no successors (think loop latch as return block)). 2668c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter double w = PI->getEdgeWeight(PI->getEdge(BB,0)); 2678c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (w != ProfileInfoT<FType, BType>::MissingValue) { 2688c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.outWeight += w; 269e8d372e48d6aff0b79d1d5d707964d1a0b9e12aaAndreas Neustifter DI.outCount++; 270e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 2718c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for (;bbi != bbe; ++bbi) { 2728c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (ProcessedSuccs.insert(*bbi).second) { 2738c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi)); 2748c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.outCount++; 2758c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 2768c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 277e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 2788c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Read block weight. 2798c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter DI.BBWeight = PI->getExecutionCount(BB); 2808c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue, 2818c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter "BasicBlock has missing value", &DI); 2828c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter CheckValue(DI.BBWeight < 0, 2838c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter "BasicBlock has negative value", &DI); 2848c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 2858c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Check if this block is a setjmp target. 2868c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bool isSetJmpTarget = false; 2878c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (DI.outWeight > DI.inWeight) { 2888c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for (typename BType::const_iterator i = BB->begin(), ie = BB->end(); 2898c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter i != ie; ++i) { 2908c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (const CallInst *CI = dyn_cast<CallInst>(&*i)) { 2918c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter FType *F = CI->getCalledFunction(); 292af81235ef96a7a005b7fdfe5a64cce30df3d820dBenjamin Kramer if (F && (F->getName() == "_setjmp")) { 2938c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter isSetJmpTarget = true; break; 2948c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 29543b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 29643b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 29743b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 2988c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Check if this block is eventually reaching exit. 2998c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bool isExitReachable = false; 3008c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (DI.inWeight > DI.outWeight) { 3018c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for (typename BType::const_iterator i = BB->begin(), ie = BB->end(); 3028c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter i != ie; ++i) { 3038c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (const CallInst *CI = dyn_cast<CallInst>(&*i)) { 3048c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter FType *F = CI->getCalledFunction(); 3058c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (F) { 3068c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter FisVisited.clear(); 3078c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter isExitReachable |= exitReachable(F); 3088c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } else { 3098c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // This is a call to a pointer, all bets are off... 3108c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter isExitReachable = true; 3118c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 3128c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (isExitReachable) break; 3138c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 31443b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 31543b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 31643b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter 3178c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (DI.inCount > 0 && DI.outCount == 0) { 3188c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // If this is a block with no successors. 3198c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (!isSetJmpTarget) { 3208c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter CheckValue(!Equals(DI.inWeight,DI.BBWeight), 3218c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter "inWeight and BBWeight do not match", &DI); 3228c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 3238c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } else if (DI.inCount == 0 && DI.outCount > 0) { 3248c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // If this is a block with no predecessors. 3258c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (!isExitReachable) 3268c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter CheckValue(!Equals(DI.BBWeight,DI.outWeight), 3278c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter "BBWeight and outWeight do not match", &DI); 3288c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } else { 3298c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // If this block has successors and predecessors. 3308c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (DI.inWeight > DI.outWeight && !isExitReachable) 3318c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter CheckValue(!Equals(DI.inWeight,DI.outWeight), 3328c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter "inWeight and outWeight do not match", &DI); 3338c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (DI.inWeight < DI.outWeight && !isSetJmpTarget) 3348c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter CheckValue(!Equals(DI.inWeight,DI.outWeight), 3358c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter "inWeight and outWeight do not match", &DI); 33643b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter } 337e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 33843b1b0e4ff5e74acafe104a6954222a0003b3ea1Andreas Neustifter 3398c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Mark this block as visited, rescurse into successors. 3408c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter BBisVisited.insert(BB); 3418c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 3428c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bbi != bbe; ++bbi ) { 3438c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter recurseBasicBlock(*bbi); 3448c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 345e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter } 346e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 3478c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 3488c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) { 3498c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >(); 3508c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (!PI) 3518c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter ASSERTMESSAGE("No ProfileInfo available"); 3528c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 3538c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Prepare global variables. 3548c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter PrintedDebugTree = false; 3558c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter BBisVisited.clear(); 3568c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 3578c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter // Fetch entry block and recurse into it. 3588c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter const BType *entry = &F.getEntryBlock(); 3598c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter recurseBasicBlock(entry); 3608c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 3618c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry)) 3628c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter ASSERTMESSAGE("Function count and entry block count do not match"); 363e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 3648c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return false; 3658c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 3668c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 3678c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter template<class FType, class BType> 3688c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter char ProfileVerifierPassT<FType, BType>::ID = 0; 3698c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter} 370e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 3712ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(ProfileVerifierPass, "profile-verifier", 3722ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Verify profiling information", false, true) 3732ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(ProfileInfo) 3742ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(ProfileVerifierPass, "profile-verifier", 375ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Verify profiling information", false, true) 376e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter 3778c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifternamespace llvm { 3788c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter FunctionPass *createProfileVerifierPass() { 3798c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter return new ProfileVerifierPass(ProfileVerifierDisableAssertions); 3808c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter } 381e7ddcfdebe357b4067f9c7d68d44616e11351a23Andreas Neustifter} 3828c30abec6d53e02c87c50ed7585ccd2ecac752aaAndreas Neustifter 383