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