1//===- PathProfileInfo.cpp ------------------------------------*- C++ -*---===// 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 defines the interface used by optimizers to load path profiles, 11// and provides a loader pass which reads a path profile file. 12// 13//===----------------------------------------------------------------------===// 14#define DEBUG_TYPE "path-profile-info" 15 16#include "llvm/Module.h" 17#include "llvm/Pass.h" 18#include "llvm/Analysis/Passes.h" 19#include "llvm/Analysis/ProfileInfoTypes.h" 20#include "llvm/Analysis/PathProfileInfo.h" 21#include "llvm/Support/CommandLine.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/Support/raw_ostream.h" 24 25#include <cstdio> 26 27using namespace llvm; 28 29// command line option for loading path profiles 30static cl::opt<std::string> 31PathProfileInfoFilename("path-profile-loader-file", cl::init("llvmprof.out"), 32 cl::value_desc("filename"), 33 cl::desc("Path profile file loaded by -path-profile-loader"), cl::Hidden); 34 35namespace { 36 class PathProfileLoaderPass : public ModulePass, public PathProfileInfo { 37 public: 38 PathProfileLoaderPass() : ModulePass(ID) { } 39 ~PathProfileLoaderPass(); 40 41 // this pass doesn't change anything (only loads information) 42 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 43 AU.setPreservesAll(); 44 } 45 46 // the full name of the loader pass 47 virtual const char* getPassName() const { 48 return "Path Profiling Information Loader"; 49 } 50 51 // required since this pass implements multiple inheritance 52 virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 53 if (PI == &PathProfileInfo::ID) 54 return (PathProfileInfo*)this; 55 return this; 56 } 57 58 // entry point to run the pass 59 bool runOnModule(Module &M); 60 61 // pass identification 62 static char ID; 63 64 private: 65 // make a reference table to refer to function by number 66 void buildFunctionRefs(Module &M); 67 68 // process argument info of a program from the input file 69 void handleArgumentInfo(); 70 71 // process path number information from the input file 72 void handlePathInfo(); 73 74 // array of references to the functions in the module 75 std::vector<Function*> _functions; 76 77 // path profile file handle 78 FILE* _file; 79 80 // path profile file name 81 std::string _filename; 82 }; 83} 84 85// register PathLoader 86char PathProfileLoaderPass::ID = 0; 87 88INITIALIZE_ANALYSIS_GROUP(PathProfileInfo, "Path Profile Information", 89 NoPathProfileInfo) 90INITIALIZE_AG_PASS(PathProfileLoaderPass, PathProfileInfo, 91 "path-profile-loader", 92 "Load path profile information from file", 93 false, true, false) 94 95char &llvm::PathProfileLoaderPassID = PathProfileLoaderPass::ID; 96 97// link PathLoader as a pass, and make it available as an optimisation 98ModulePass *llvm::createPathProfileLoaderPass() { 99 return new PathProfileLoaderPass; 100} 101 102// ---------------------------------------------------------------------------- 103// PathEdge implementation 104// 105ProfilePathEdge::ProfilePathEdge (BasicBlock* source, BasicBlock* target, 106 unsigned duplicateNumber) 107 : _source(source), _target(target), _duplicateNumber(duplicateNumber) {} 108 109// ---------------------------------------------------------------------------- 110// Path implementation 111// 112 113ProfilePath::ProfilePath (unsigned int number, unsigned int count, 114 double countStdDev, PathProfileInfo* ppi) 115 : _number(number) , _count(count), _countStdDev(countStdDev), _ppi(ppi) {} 116 117double ProfilePath::getFrequency() const { 118 return 100 * double(_count) / 119 double(_ppi->_functionPathCounts[_ppi->_currentFunction]); 120} 121 122static BallLarusEdge* getNextEdge (BallLarusNode* node, 123 unsigned int pathNumber) { 124 BallLarusEdge* best = 0; 125 126 for( BLEdgeIterator next = node->succBegin(), 127 end = node->succEnd(); next != end; next++ ) { 128 if( (*next)->getType() != BallLarusEdge::BACKEDGE && // no backedges 129 (*next)->getType() != BallLarusEdge::SPLITEDGE && // no split edges 130 (*next)->getWeight() <= pathNumber && // weight must be <= pathNumber 131 (!best || (best->getWeight() < (*next)->getWeight())) ) // best one? 132 best = *next; 133 } 134 135 return best; 136} 137 138ProfilePathEdgeVector* ProfilePath::getPathEdges() const { 139 BallLarusNode* currentNode = _ppi->_currentDag->getRoot (); 140 unsigned int increment = _number; 141 ProfilePathEdgeVector* pev = new ProfilePathEdgeVector; 142 143 while (currentNode != _ppi->_currentDag->getExit()) { 144 BallLarusEdge* next = getNextEdge(currentNode, increment); 145 146 increment -= next->getWeight(); 147 148 if( next->getType() != BallLarusEdge::BACKEDGE_PHONY && 149 next->getType() != BallLarusEdge::SPLITEDGE_PHONY && 150 next->getTarget() != _ppi->_currentDag->getExit() ) 151 pev->push_back(ProfilePathEdge( 152 next->getSource()->getBlock(), 153 next->getTarget()->getBlock(), 154 next->getDuplicateNumber())); 155 156 if( next->getType() == BallLarusEdge::BACKEDGE_PHONY && 157 next->getTarget() == _ppi->_currentDag->getExit() ) 158 pev->push_back(ProfilePathEdge( 159 next->getRealEdge()->getSource()->getBlock(), 160 next->getRealEdge()->getTarget()->getBlock(), 161 next->getDuplicateNumber())); 162 163 if( next->getType() == BallLarusEdge::SPLITEDGE_PHONY && 164 next->getSource() == _ppi->_currentDag->getRoot() ) 165 pev->push_back(ProfilePathEdge( 166 next->getRealEdge()->getSource()->getBlock(), 167 next->getRealEdge()->getTarget()->getBlock(), 168 next->getDuplicateNumber())); 169 170 // set the new node 171 currentNode = next->getTarget(); 172 } 173 174 return pev; 175} 176 177ProfilePathBlockVector* ProfilePath::getPathBlocks() const { 178 BallLarusNode* currentNode = _ppi->_currentDag->getRoot (); 179 unsigned int increment = _number; 180 ProfilePathBlockVector* pbv = new ProfilePathBlockVector; 181 182 while (currentNode != _ppi->_currentDag->getExit()) { 183 BallLarusEdge* next = getNextEdge(currentNode, increment); 184 increment -= next->getWeight(); 185 186 // add block to the block list if it is a real edge 187 if( next->getType() == BallLarusEdge::NORMAL) 188 pbv->push_back (currentNode->getBlock()); 189 // make the back edge the last edge since we are at the end 190 else if( next->getTarget() == _ppi->_currentDag->getExit() ) { 191 pbv->push_back (currentNode->getBlock()); 192 pbv->push_back (next->getRealEdge()->getTarget()->getBlock()); 193 } 194 195 // set the new node 196 currentNode = next->getTarget(); 197 } 198 199 return pbv; 200} 201 202BasicBlock* ProfilePath::getFirstBlockInPath() const { 203 BallLarusNode* root = _ppi->_currentDag->getRoot(); 204 BallLarusEdge* edge = getNextEdge(root, _number); 205 206 if( edge && (edge->getType() == BallLarusEdge::BACKEDGE_PHONY || 207 edge->getType() == BallLarusEdge::SPLITEDGE_PHONY) ) 208 return edge->getTarget()->getBlock(); 209 210 return root->getBlock(); 211} 212 213// ---------------------------------------------------------------------------- 214// PathProfileInfo implementation 215// 216 217// Pass identification 218char llvm::PathProfileInfo::ID = 0; 219 220PathProfileInfo::PathProfileInfo () : _currentDag(0) , _currentFunction(0) { 221} 222 223PathProfileInfo::~PathProfileInfo() { 224 if (_currentDag) 225 delete _currentDag; 226} 227 228// set the function for which paths are currently begin processed 229void PathProfileInfo::setCurrentFunction(Function* F) { 230 // Make sure it exists 231 if (!F) return; 232 233 if (_currentDag) 234 delete _currentDag; 235 236 _currentFunction = F; 237 _currentDag = new BallLarusDag(*F); 238 _currentDag->init(); 239 _currentDag->calculatePathNumbers(); 240} 241 242// get the function for which paths are currently being processed 243Function* PathProfileInfo::getCurrentFunction() const { 244 return _currentFunction; 245} 246 247// get the entry block of the function 248BasicBlock* PathProfileInfo::getCurrentFunctionEntry() { 249 return _currentDag->getRoot()->getBlock(); 250} 251 252// return the path based on its number 253ProfilePath* PathProfileInfo::getPath(unsigned int number) { 254 return _functionPaths[_currentFunction][number]; 255} 256 257// return the number of paths which a function may potentially execute 258unsigned int PathProfileInfo::getPotentialPathCount() { 259 return _currentDag ? _currentDag->getNumberOfPaths() : 0; 260} 261 262// return an iterator for the beginning of a functions executed paths 263ProfilePathIterator PathProfileInfo::pathBegin() { 264 return _functionPaths[_currentFunction].begin(); 265} 266 267// return an iterator for the end of a functions executed paths 268ProfilePathIterator PathProfileInfo::pathEnd() { 269 return _functionPaths[_currentFunction].end(); 270} 271 272// returns the total number of paths run in the function 273unsigned int PathProfileInfo::pathsRun() { 274 return _currentFunction ? _functionPaths[_currentFunction].size() : 0; 275} 276 277// ---------------------------------------------------------------------------- 278// PathLoader implementation 279// 280 281// remove all generated paths 282PathProfileLoaderPass::~PathProfileLoaderPass() { 283 for( FunctionPathIterator funcNext = _functionPaths.begin(), 284 funcEnd = _functionPaths.end(); funcNext != funcEnd; funcNext++) 285 for( ProfilePathIterator pathNext = funcNext->second.begin(), 286 pathEnd = funcNext->second.end(); pathNext != pathEnd; pathNext++) 287 delete pathNext->second; 288} 289 290// entry point of the pass; this loads and parses a file 291bool PathProfileLoaderPass::runOnModule(Module &M) { 292 // get the filename and setup the module's function references 293 _filename = PathProfileInfoFilename; 294 buildFunctionRefs (M); 295 296 if (!(_file = fopen(_filename.c_str(), "rb"))) { 297 errs () << "error: input '" << _filename << "' file does not exist.\n"; 298 return false; 299 } 300 301 ProfilingType profType; 302 303 while( fread(&profType, sizeof(ProfilingType), 1, _file) ) { 304 switch (profType) { 305 case ArgumentInfo: 306 handleArgumentInfo (); 307 break; 308 case PathInfo: 309 handlePathInfo (); 310 break; 311 default: 312 errs () << "error: bad path profiling file syntax, " << profType << "\n"; 313 fclose (_file); 314 return false; 315 } 316 } 317 318 fclose (_file); 319 320 return true; 321} 322 323// create a reference table for functions defined in the path profile file 324void PathProfileLoaderPass::buildFunctionRefs (Module &M) { 325 _functions.push_back(0); // make the 0 index a null pointer 326 327 for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) { 328 if (F->isDeclaration()) 329 continue; 330 _functions.push_back(F); 331 } 332} 333 334// handle command like argument infor in the output file 335void PathProfileLoaderPass::handleArgumentInfo() { 336 // get the argument list's length 337 unsigned savedArgsLength; 338 if( fread(&savedArgsLength, sizeof(unsigned), 1, _file) != 1 ) { 339 errs() << "warning: argument info header/data mismatch\n"; 340 return; 341 } 342 343 // allocate a buffer, and get the arguments 344 char* args = new char[savedArgsLength+1]; 345 if( fread(args, 1, savedArgsLength, _file) != savedArgsLength ) 346 errs() << "warning: argument info header/data mismatch\n"; 347 348 args[savedArgsLength] = '\0'; 349 argList = std::string(args); 350 delete [] args; // cleanup dynamic string 351 352 // byte alignment 353 if (savedArgsLength & 3) 354 fseek(_file, 4-(savedArgsLength&3), SEEK_CUR); 355} 356 357// Handle path profile information in the output file 358void PathProfileLoaderPass::handlePathInfo () { 359 // get the number of functions in this profile 360 unsigned functionCount; 361 if( fread(&functionCount, sizeof(functionCount), 1, _file) != 1 ) { 362 errs() << "warning: path info header/data mismatch\n"; 363 return; 364 } 365 366 // gather path information for each function 367 for (unsigned i = 0; i < functionCount; i++) { 368 PathProfileHeader pathHeader; 369 if( fread(&pathHeader, sizeof(pathHeader), 1, _file) != 1 ) { 370 errs() << "warning: bad header for path function info\n"; 371 break; 372 } 373 374 Function* f = _functions[pathHeader.fnNumber]; 375 376 // dynamically allocate a table to store path numbers 377 PathProfileTableEntry* pathTable = 378 new PathProfileTableEntry[pathHeader.numEntries]; 379 380 if( fread(pathTable, sizeof(PathProfileTableEntry), 381 pathHeader.numEntries, _file) != pathHeader.numEntries) { 382 delete [] pathTable; 383 errs() << "warning: path function info header/data mismatch\n"; 384 return; 385 } 386 387 // Build a new path for the current function 388 unsigned int totalPaths = 0; 389 for (unsigned int j = 0; j < pathHeader.numEntries; j++) { 390 totalPaths += pathTable[j].pathCounter; 391 _functionPaths[f][pathTable[j].pathNumber] 392 = new ProfilePath(pathTable[j].pathNumber, pathTable[j].pathCounter, 393 0, this); 394 } 395 396 _functionPathCounts[f] = totalPaths; 397 398 delete [] pathTable; 399 } 400} 401 402//===----------------------------------------------------------------------===// 403// NoProfile PathProfileInfo implementation 404// 405 406namespace { 407 struct NoPathProfileInfo : public ImmutablePass, public PathProfileInfo { 408 static char ID; // Class identification, replacement for typeinfo 409 NoPathProfileInfo() : ImmutablePass(ID) { 410 initializeNoPathProfileInfoPass(*PassRegistry::getPassRegistry()); 411 } 412 413 /// getAdjustedAnalysisPointer - This method is used when a pass implements 414 /// an analysis interface through multiple inheritance. If needed, it 415 /// should override this to adjust the this pointer as needed for the 416 /// specified pass info. 417 virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 418 if (PI == &PathProfileInfo::ID) 419 return (PathProfileInfo*)this; 420 return this; 421 } 422 423 virtual const char *getPassName() const { 424 return "NoPathProfileInfo"; 425 } 426 }; 427} // End of anonymous namespace 428 429char NoPathProfileInfo::ID = 0; 430// Register this pass... 431INITIALIZE_AG_PASS(NoPathProfileInfo, PathProfileInfo, "no-path-profile", 432 "No Path Profile Information", false, true, true) 433 434ImmutablePass *llvm::createNoPathProfileInfoPass() { return new NoPathProfileInfo(); } 435