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