Home | History | Annotate | Download | only in Analysis
      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 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