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/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 errorInfo;
    170   std::string filename = EdgeProfileFilename;
    171 
    172   // Open a handle to the file
    173   FILE* edgeFile = fopen(filename.c_str(),"wb");
    174 
    175   if (!edgeFile) {
    176     errs() << "error: unable to open file '" << filename << "' for output.\n";
    177     return false;
    178   }
    179 
    180   errs() << "Generating edge profile '" << filename << "' ...\n";
    181 
    182   // write argument info
    183   unsigned type = ArgumentInfo;
    184   unsigned num = pathProfileInfo.argList.size();
    185   int zeros = 0;
    186 
    187   fwrite(&type,sizeof(unsigned),1,edgeFile);
    188   fwrite(&num,sizeof(unsigned),1,edgeFile);
    189   fwrite(pathProfileInfo.argList.c_str(),1,num,edgeFile);
    190   if (num&3)
    191     fwrite(&zeros, 1, 4-(num&3), edgeFile);
    192 
    193   type = EdgeInfo;
    194   num = edgeArray.size();
    195   fwrite(&type,sizeof(unsigned),1,edgeFile);
    196   fwrite(&num,sizeof(unsigned),1,edgeFile);
    197 
    198   // write each edge to the file
    199   for( std::vector<unsigned>::iterator s = edgeArray.begin(),
    200          e = edgeArray.end(); s != e; s++)
    201     fwrite(&*s, sizeof (unsigned), 1, edgeFile);
    202 
    203   fclose (edgeFile);
    204 
    205   return true;
    206 }
    207