1 //===- PathProfileInfo.cpp ------------------------------------*- C++ -*---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "path-profile-info"
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"
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);
35 class PathProfileLoaderPass : public ModulePass, public PathProfileInfo {
37 PathProfileLoaderPass() : ModulePass(ID) { }
38 ~PathProfileLoaderPass();
40 // this pass doesn't change anything (only loads information)
41 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
45 // the full name of the loader pass
46 virtual const char* getPassName() const {
47 return "Path Profiling Information Loader";
50 // required since this pass implements multiple inheritance
51 virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
52 if (PI == &PathProfileInfo::ID)
53 return (PathProfileInfo*)this;
57 // entry point to run the pass
58 bool runOnModule(Module &M);
60 // pass identification
64 // make a reference table to refer to function by number
65 void buildFunctionRefs(Module &M);
67 // process argument info of a program from the input file
68 void handleArgumentInfo();
70 // process path number information from the input file
71 void handlePathInfo();
73 // array of references to the functions in the module
74 std::vector<Function*> _functions;
76 // path profile file handle
79 // path profile file name
80 std::string _filename;
84 // register PathLoader
85 char PathProfileLoaderPass::ID = 0;
87 INITIALIZE_ANALYSIS_GROUP(PathProfileInfo, "Path Profile Information",
89 INITIALIZE_AG_PASS(PathProfileLoaderPass, PathProfileInfo,
90 "path-profile-loader",
91 "Load path profile information from file",
94 char &llvm::PathProfileLoaderPassID = PathProfileLoaderPass::ID;
96 // link PathLoader as a pass, and make it available as an optimisation
97 ModulePass *llvm::createPathProfileLoaderPass() {
98 return new PathProfileLoaderPass;
101 // ----------------------------------------------------------------------------
102 // PathEdge implementation
104 ProfilePathEdge::ProfilePathEdge (BasicBlock* source, BasicBlock* target,
105 unsigned duplicateNumber)
106 : _source(source), _target(target), _duplicateNumber(duplicateNumber) {}
108 // ----------------------------------------------------------------------------
109 // Path implementation
112 ProfilePath::ProfilePath (unsigned int number, unsigned int count,
113 double countStdDev, PathProfileInfo* ppi)
114 : _number(number) , _count(count), _countStdDev(countStdDev), _ppi(ppi) {}
116 double ProfilePath::getFrequency() const {
117 return 100 * double(_count) /
118 double(_ppi->_functionPathCounts[_ppi->_currentFunction]);
121 static BallLarusEdge* getNextEdge (BallLarusNode* node,
122 unsigned int pathNumber) {
123 BallLarusEdge* best = 0;
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?
137 ProfilePathEdgeVector* ProfilePath::getPathEdges() const {
138 BallLarusNode* currentNode = _ppi->_currentDag->getRoot ();
139 unsigned int increment = _number;
140 ProfilePathEdgeVector* pev = new ProfilePathEdgeVector;
142 while (currentNode != _ppi->_currentDag->getExit()) {
143 BallLarusEdge* next = getNextEdge(currentNode, increment);
145 increment -= next->getWeight();
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()));
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()));
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()));
170 currentNode = next->getTarget();
176 ProfilePathBlockVector* ProfilePath::getPathBlocks() const {
177 BallLarusNode* currentNode = _ppi->_currentDag->getRoot ();
178 unsigned int increment = _number;
179 ProfilePathBlockVector* pbv = new ProfilePathBlockVector;
181 while (currentNode != _ppi->_currentDag->getExit()) {
182 BallLarusEdge* next = getNextEdge(currentNode, increment);
183 increment -= next->getWeight();
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());
195 currentNode = next->getTarget();
201 BasicBlock* ProfilePath::getFirstBlockInPath() const {
202 BallLarusNode* root = _ppi->_currentDag->getRoot();
203 BallLarusEdge* edge = getNextEdge(root, _number);
205 if( edge && (edge->getType() == BallLarusEdge::BACKEDGE_PHONY ||
206 edge->getType() == BallLarusEdge::SPLITEDGE_PHONY) )
207 return edge->getTarget()->getBlock();
209 return root->getBlock();
212 // ----------------------------------------------------------------------------
213 // PathProfileInfo implementation
216 // Pass identification
217 char llvm::PathProfileInfo::ID = 0;
219 PathProfileInfo::PathProfileInfo () : _currentDag(0) , _currentFunction(0) {
222 PathProfileInfo::~PathProfileInfo() {
227 // set the function for which paths are currently begin processed
228 void PathProfileInfo::setCurrentFunction(Function* F) {
229 // Make sure it exists
235 _currentFunction = F;
236 _currentDag = new BallLarusDag(*F);
238 _currentDag->calculatePathNumbers();
241 // get the function for which paths are currently being processed
242 Function* PathProfileInfo::getCurrentFunction() const {
243 return _currentFunction;
246 // get the entry block of the function
247 BasicBlock* PathProfileInfo::getCurrentFunctionEntry() {
248 return _currentDag->getRoot()->getBlock();
251 // return the path based on its number
252 ProfilePath* PathProfileInfo::getPath(unsigned int number) {
253 return _functionPaths[_currentFunction][number];
256 // return the number of paths which a function may potentially execute
257 unsigned int PathProfileInfo::getPotentialPathCount() {
258 return _currentDag ? _currentDag->getNumberOfPaths() : 0;
261 // return an iterator for the beginning of a functions executed paths
262 ProfilePathIterator PathProfileInfo::pathBegin() {
263 return _functionPaths[_currentFunction].begin();
266 // return an iterator for the end of a functions executed paths
267 ProfilePathIterator PathProfileInfo::pathEnd() {
268 return _functionPaths[_currentFunction].end();
271 // returns the total number of paths run in the function
272 unsigned int PathProfileInfo::pathsRun() {
273 return _currentFunction ? _functionPaths[_currentFunction].size() : 0;
276 // ----------------------------------------------------------------------------
277 // PathLoader implementation
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;
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);
295 if (!(_file = fopen(_filename.c_str(), "rb"))) {
296 errs () << "error: input '" << _filename << "' file does not exist.\n";
300 ProfilingType profType;
302 while( fread(&profType, sizeof(ProfilingType), 1, _file) ) {
305 handleArgumentInfo ();
311 errs () << "error: bad path profiling file syntax, " << profType << "\n";
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
326 for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) {
327 if (F->isDeclaration())
329 _functions.push_back(F);
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";
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";
347 args[savedArgsLength] = '\0';
348 argList = std::string(args);
349 delete [] args; // cleanup dynamic string
352 if (savedArgsLength & 3)
353 fseek(_file, 4-(savedArgsLength&3), SEEK_CUR);
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";
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";
373 Function* f = _functions[pathHeader.fnNumber];
375 // dynamically allocate a table to store path numbers
376 PathProfileTableEntry* pathTable =
377 new PathProfileTableEntry[pathHeader.numEntries];
379 if( fread(pathTable, sizeof(PathProfileTableEntry),
380 pathHeader.numEntries, _file) != pathHeader.numEntries) {
382 errs() << "warning: path function info header/data mismatch\n";
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,
395 _functionPathCounts[f] = totalPaths;
401 //===----------------------------------------------------------------------===//
402 // NoProfile PathProfileInfo implementation
406 struct NoPathProfileInfo : public ImmutablePass, public PathProfileInfo {
407 static char ID; // Class identification, replacement for typeinfo
408 NoPathProfileInfo() : ImmutablePass(ID) {
409 initializeNoPathProfileInfoPass(*PassRegistry::getPassRegistry());
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;
422 virtual const char *getPassName() const {
423 return "NoPathProfileInfo";
426 } // End of anonymous namespace
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)
433 ImmutablePass *llvm::createNoPathProfileInfoPass() { return new NoPathProfileInfo(); }