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