• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
27 using namespace llvm;
28 
29 namespace {
30   class PathProfileVerifier : public ModulePass {
31   private:
32     bool runOnModule(Module &M);
33 
34   public:
35     static char ID; // Pass identification, replacement for typeid
PathProfileVerifier()36     PathProfileVerifier() : ModulePass(ID) {
37       initializePathProfileVerifierPass(*PassRegistry::getPassRegistry());
38     }
39 
40 
getPassName() const41     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 
50 static cl::opt<std::string>
51 EdgeProfileFilename("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 
57 char PathProfileVerifier::ID = 0;
58 INITIALIZE_PASS(PathProfileVerifier, "path-profile-verifier",
59                 "Compare the path profile derived edge profile against the "
60                 "edge profile.", true, true)
61 
createPathProfileVerifierPass()62 ModulePass *llvm::createPathProfileVerifierPass() {
63   return new PathProfileVerifier();
64 }
65 
66 // The verifier requires the path profile and edge profile.
getAnalysisUsage(AnalysisUsage & AU) const67 void PathProfileVerifier::getAnalysisUsage(AnalysisUsage& AU) const {
68   AU.addRequired<PathProfileInfo>();
69   AU.addPreserved<PathProfileInfo>();
70 }
71 
72 typedef std::map<unsigned, unsigned> DuplicateToIndexMap;
73 typedef std::map<BasicBlock*,DuplicateToIndexMap> BlockToDuplicateMap;
74 typedef std::map<BasicBlock*,BlockToDuplicateMap> NestedBlockToIndexMap;
75 
76 // the verifier iterates through each path to gather the total
77 // number of edge frequencies
runOnModule(Module & M)78 bool 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->getNameStr() << " --{" << duplicateNumber
141               << "}--> " << target->getNameStr());
142 
143         // Ensure all the referenced edges exist
144         // TODO: make this a separate function
145         if( !arrayMap.count(source) ) {
146           errs() << "  error [" << F->getNameStr() << "()]: source '"
147                  << source->getNameStr()
148                  << "' does not exist in the array map.\n";
149         } else if( !arrayMap[source].count(target) ) {
150           errs() << "  error [" << F->getNameStr() << "()]: target '"
151                  << target->getNameStr()
152                  << "' does not exist in the array map.\n";
153         } else if( !arrayMap[source][target].count(duplicateNumber) ) {
154           errs() << "  error [" << F->getNameStr() << "()]: edge "
155                  << source->getNameStr() << " -> " << target->getNameStr()
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