lib/Analysis/PathProfileVerifier.cpp

   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
  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
  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
  62 ModulePass *llvm::createPathProfileVerifierPass() {
  63   return new PathProfileVerifier();
  64 }
  65
  66 // The verifier requires the path profile and edge profile.
  67 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
  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 doens'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 }