PathProfileVerifier.cpp revision 249423 
1//===- PathProfileVerifier.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 verifier derives an edge profile file from current path profile
11// information
12//
13//===----------------------------------------------------------------------===//
14#define DEBUG_TYPE "path-profile-verifier"
15
16#include "llvm/Analysis/Passes.h"
17#include "llvm/Analysis/PathProfileInfo.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 <stdio.h>
25
26using namespace llvm;
27
28namespace {
29  class PathProfileVerifier : public ModulePass {
30  private:
31    bool runOnModule(Module &M);
32
33  public:
34    static char ID; // Pass identification, replacement for typeid
35    PathProfileVerifier() : ModulePass(ID) {
36      initializePathProfileVerifierPass(*PassRegistry::getPassRegistry());
37    }
38
39
40    virtual const char *getPassName() const {
41      return "Path Profiler Verifier";
42    }
43
44    // The verifier requires the path profile and edge profile.
45    virtual void getAnalysisUsage(AnalysisUsage& AU) const;
46  };
47}
48
49static cl::opt<std::string>
50EdgeProfileFilename("path-profile-verifier-file",
51  cl::init("edgefrompath.llvmprof.out"),
52  cl::value_desc("filename"),
53  cl::desc("Edge profile file generated by -path-profile-verifier"),
54  cl::Hidden);
55
56char PathProfileVerifier::ID = 0;
57INITIALIZE_PASS(PathProfileVerifier, "path-profile-verifier",
58                "Compare the path profile derived edge profile against the "
59                "edge profile.", true, true)
60
61ModulePass *llvm::createPathProfileVerifierPass() {
62  return new PathProfileVerifier();
63}
64
65// The verifier requires the path profile and edge profile.
66void PathProfileVerifier::getAnalysisUsage(AnalysisUsage& AU) const {
67  AU.addRequired<PathProfileInfo>();
68  AU.addPreserved<PathProfileInfo>();
69}
70
71typedef std::map<unsigned, unsigned> DuplicateToIndexMap;
72typedef std::map<BasicBlock*,DuplicateToIndexMap> BlockToDuplicateMap;
73typedef std::map<BasicBlock*,BlockToDuplicateMap> NestedBlockToIndexMap;
74
75// the verifier iterates through each path to gather the total
76// number of edge frequencies
77bool PathProfileVerifier::runOnModule (Module &M) {
78  PathProfileInfo& pathProfileInfo = getAnalysis<PathProfileInfo>();
79
80  // setup a data structure to map path edges which index an
81  // array of edge counters
82  NestedBlockToIndexMap arrayMap;
83  unsigned i = 0;
84  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
85    if (F->isDeclaration()) continue;
86
87    arrayMap[(BasicBlock*)0][F->begin()][0] = i++;
88
89    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
90      TerminatorInst *TI = BB->getTerminator();
91
92      unsigned duplicate = 0;
93      BasicBlock* prev = 0;
94      for (unsigned s = 0, e = TI->getNumSuccessors(); s != e;
95           prev = TI->getSuccessor(s), ++s) {
96        if (prev == TI->getSuccessor(s))
97          duplicate++;
98        else duplicate = 0;
99
100        arrayMap[BB][TI->getSuccessor(s)][duplicate] = i++;
101      }
102    }
103  }
104
105  std::vector<unsigned> edgeArray(i);
106
107  // iterate through each path and increment the edge counters as needed
108  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
109    if (F->isDeclaration()) continue;
110
111    pathProfileInfo.setCurrentFunction(F);
112
113    DEBUG(dbgs() << "function '" << F->getName() << "' ran "
114          << pathProfileInfo.pathsRun()
115          << "/" << pathProfileInfo.getPotentialPathCount()
116          << " potential paths\n");
117
118    for( ProfilePathIterator nextPath = pathProfileInfo.pathBegin(),
119           endPath = pathProfileInfo.pathEnd();
120         nextPath != endPath; nextPath++ ) {
121      ProfilePath* currentPath = nextPath->second;
122
123      ProfilePathEdgeVector* pev = currentPath->getPathEdges();
124      DEBUG(dbgs () << "path #" << currentPath->getNumber() << ": "
125            << currentPath->getCount() << "\n");
126      // setup the entry edge (normally path profiling doesn't care about this)
127      if (currentPath->getFirstBlockInPath() == &F->getEntryBlock())
128        edgeArray[arrayMap[(BasicBlock*)0][currentPath->getFirstBlockInPath()][0]]
129          += currentPath->getCount();
130
131      for( ProfilePathEdgeIterator nextEdge = pev->begin(),
132             endEdge = pev->end(); nextEdge != endEdge; nextEdge++ ) {
133        if (nextEdge != pev->begin())
134          DEBUG(dbgs() << " :: ");
135
136        BasicBlock* source = nextEdge->getSource();
137        BasicBlock* target = nextEdge->getTarget();
138        unsigned duplicateNumber = nextEdge->getDuplicateNumber();
139        DEBUG(dbgs() << source->getName() << " --{" << duplicateNumber
140                     << "}--> " << target->getName());
141
142        // Ensure all the referenced edges exist
143        // TODO: make this a separate function
144        if( !arrayMap.count(source) ) {
145          errs() << "  error [" << F->getName() << "()]: source '"
146                 << source->getName()
147                 << "' does not exist in the array map.\n";
148        } else if( !arrayMap[source].count(target) ) {
149          errs() << "  error [" << F->getName() << "()]: target '"
150                 << target->getName()
151                 << "' does not exist in the array map.\n";
152        } else if( !arrayMap[source][target].count(duplicateNumber) ) {
153          errs() << "  error [" << F->getName() << "()]: edge "
154                 << source->getName() << " -> " << target->getName()
155                 << " duplicate number " << duplicateNumber
156                 << " does not exist in the array map.\n";
157        } else {
158          edgeArray[arrayMap[source][target][duplicateNumber]]
159            += currentPath->getCount();
160        }
161      }
162
163      DEBUG(errs() << "\n");
164
165      delete pev;
166    }
167  }
168
169  std::string errorInfo;
170  std::string filename = EdgeProfileFilename;
171
172  // Open a handle to the file
173  FILE* edgeFile = fopen(filename.c_str(),"wb");
174
175  if (!edgeFile) {
176    errs() << "error: unable to open file '" << filename << "' for output.\n";
177    return false;
178  }
179
180  errs() << "Generating edge profile '" << filename << "' ...\n";
181
182  // write argument info
183  unsigned type = ArgumentInfo;
184  unsigned num = pathProfileInfo.argList.size();
185  int zeros = 0;
186
187  fwrite(&type,sizeof(unsigned),1,edgeFile);
188  fwrite(&num,sizeof(unsigned),1,edgeFile);
189  fwrite(pathProfileInfo.argList.c_str(),1,num,edgeFile);
190  if (num&3)
191    fwrite(&zeros, 1, 4-(num&3), edgeFile);
192
193  type = EdgeInfo;
194  num = edgeArray.size();
195  fwrite(&type,sizeof(unsigned),1,edgeFile);
196  fwrite(&num,sizeof(unsigned),1,edgeFile);
197
198  // write each edge to the file
199  for( std::vector<unsigned>::iterator s = edgeArray.begin(),
200         e = edgeArray.end(); s != e; s++)
201    fwrite(&*s, sizeof (unsigned), 1, edgeFile);
202
203  fclose (edgeFile);
204
205  return true;
206}
207