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