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