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/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
  26 using namespace llvm;
  27
  28 namespace {
  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
  49 static cl::opt<std::string>
  50 EdgeProfileFilename("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
  56 char PathProfileVerifier::ID = 0;
  57 INITIALIZE_PASS(PathProfileVerifier, "path-profile-verifier",
  58                 "Compare the path profile derived edge profile against the "
  59                 "edge profile.", true, true)
  60
  61 ModulePass *llvm::createPathProfileVerifierPass() {
  62   return new PathProfileVerifier();
  63 }
  64
  65 // The verifier requires the path profile and edge profile.
  66 void PathProfileVerifier::getAnalysisUsage(AnalysisUsage& AU) const {
  67   AU.addRequired<PathProfileInfo>();
  68   AU.addPreserved<PathProfileInfo>();
  69 }
  70
  71 typedef std::map<unsigned, unsigned> DuplicateToIndexMap;
  72 typedef std::map<BasicBlock*,DuplicateToIndexMap> BlockToDuplicateMap;
  73 typedef std::map<BasicBlock*,BlockToDuplicateMap> NestedBlockToIndexMap;
  74
  75 // the verifier iterates through each path to gather the total
  76 // number of edge frequencies
  77 bool 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 filename = EdgeProfileFilename;
 170
 171   // Open a handle to the file
 172   FILE* edgeFile = fopen(filename.c_str(),"wb");
 173
 174   if (!edgeFile) {
 175     errs() << "error: unable to open file '" << filename << "' for output.\n";
 176     return false;
 177   }
 178
 179   errs() << "Generating edge profile '" << filename << "' ...\n";
 180
 181   // write argument info
 182   unsigned type = ArgumentInfo;
 183   unsigned num = pathProfileInfo.argList.size();
 184   int zeros = 0;
 185
 186   fwrite(&type,sizeof(unsigned),1,edgeFile);
 187   fwrite(&num,sizeof(unsigned),1,edgeFile);
 188   fwrite(pathProfileInfo.argList.c_str(),1,num,edgeFile);
 189   if (num&3)
 190     fwrite(&zeros, 1, 4-(num&3), edgeFile);
 191
 192   type = EdgeInfo;
 193   num = edgeArray.size();
 194   fwrite(&type,sizeof(unsigned),1,edgeFile);
 195   fwrite(&num,sizeof(unsigned),1,edgeFile);
 196
 197   // write each edge to the file
 198   for( std::vector<unsigned>::iterator s = edgeArray.begin(),
 199          e = edgeArray.end(); s != e; s++)
 200     fwrite(&*s, sizeof (unsigned), 1, edgeFile);
 201
 202   fclose (edgeFile);
 203
 204   return true;
 205 }