lib/Analysis/PathProfileInfo.cpp

   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
  27 using namespace llvm;
  28
  29 // command line option for loading path profiles
  30 static cl::opt<std::string>
  31 PathProfileInfoFilename("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
  35 namespace {
  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
  86 char PathProfileLoaderPass::ID = 0;
  87
  88 INITIALIZE_ANALYSIS_GROUP(PathProfileInfo, "Path Profile Information",
  89                           NoPathProfileInfo)
  90 INITIALIZE_AG_PASS(PathProfileLoaderPass, PathProfileInfo,
  91                    "path-profile-loader",
  92                    "Load path profile information from file",
  93                    false, true, false)
  94
  95 char &llvm::PathProfileLoaderPassID = PathProfileLoaderPass::ID;
  96
  97 // link PathLoader as a pass, and make it available as an optimisation
  98 ModulePass *llvm::createPathProfileLoaderPass() {
  99   return new PathProfileLoaderPass;
 100 }
 101
 102 // ----------------------------------------------------------------------------
 103 // PathEdge implementation
 104 //
 105 ProfilePathEdge::ProfilePathEdge (BasicBlock* source, BasicBlock* target,
 106                                   unsigned duplicateNumber)
 107   : _source(source), _target(target), _duplicateNumber(duplicateNumber) {}
 108
 109 // ----------------------------------------------------------------------------
 110 // Path implementation
 111 //
 112
 113 ProfilePath::ProfilePath (unsigned int number, unsigned int count,
 114                           double countStdDev,   PathProfileInfo* ppi)
 115   : _number(number) , _count(count), _countStdDev(countStdDev), _ppi(ppi) {}
 116
 117 double ProfilePath::getFrequency() const {
 118   return 100 * double(_count) /
 119     double(_ppi->_functionPathCounts[_ppi->_currentFunction]);
 120 }
 121
 122 static 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
 138 ProfilePathEdgeVector* 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
 177 ProfilePathBlockVector* 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
 202 BasicBlock* 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
 218 char llvm::PathProfileInfo::ID = 0;
 219
 220 PathProfileInfo::PathProfileInfo () : _currentDag(0) , _currentFunction(0) {
 221 }
 222
 223 PathProfileInfo::~PathProfileInfo() {
 224   if (_currentDag)
 225     delete _currentDag;
 226 }
 227
 228 // set the function for which paths are currently begin processed
 229 void 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
 243 Function* PathProfileInfo::getCurrentFunction() const {
 244   return _currentFunction;
 245 }
 246
 247 // get the entry block of the function
 248 BasicBlock* PathProfileInfo::getCurrentFunctionEntry() {
 249   return _currentDag->getRoot()->getBlock();
 250 }
 251
 252 // return the path based on its number
 253 ProfilePath* PathProfileInfo::getPath(unsigned int number) {
 254   return _functionPaths[_currentFunction][number];
 255 }
 256
 257 // return the number of paths which a function may potentially execute
 258 unsigned int PathProfileInfo::getPotentialPathCount() {
 259   return _currentDag ? _currentDag->getNumberOfPaths() : 0;
 260 }
 261
 262 // return an iterator for the beginning of a functions executed paths
 263 ProfilePathIterator PathProfileInfo::pathBegin() {
 264   return _functionPaths[_currentFunction].begin();
 265 }
 266
 267 // return an iterator for the end of a functions executed paths
 268 ProfilePathIterator PathProfileInfo::pathEnd() {
 269   return _functionPaths[_currentFunction].end();
 270 }
 271
 272 // returns the total number of paths run in the function
 273 unsigned int PathProfileInfo::pathsRun() {
 274   return _currentFunction ? _functionPaths[_currentFunction].size() : 0;
 275 }
 276
 277 // ----------------------------------------------------------------------------
 278 // PathLoader implementation
 279 //
 280
 281 // remove all generated paths
 282 PathProfileLoaderPass::~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
 291 bool 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
 324 void 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
 335 void 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
 358 void 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
 406 namespace {
 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
 429 char NoPathProfileInfo::ID = 0;
 430 // Register this pass...
 431 INITIALIZE_AG_PASS(NoPathProfileInfo, PathProfileInfo, "no-path-profile",
 432                    "No Path Profile Information", false, true, true)
 433
 434 ImmutablePass *llvm::createNoPathProfileInfoPass() { return new NoPathProfileInfo(); }