LLVM API Documentation

ProfileEstimatorPass.cpp

Go to the documentation of this file.
00001 //===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a concrete implementation of profiling information that
00011 // estimates the profiling information in a very crude and unimaginative way.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 #define DEBUG_TYPE "profile-estimator"
00015 #include "llvm/Pass.h"
00016 #include "llvm/Analysis/Passes.h"
00017 #include "llvm/Analysis/ProfileInfo.h"
00018 #include "llvm/Analysis/LoopInfo.h"
00019 #include "llvm/Support/CommandLine.h"
00020 #include "llvm/Support/Debug.h"
00021 #include "llvm/Support/raw_ostream.h"
00022 using namespace llvm;
00023 
00024 static cl::opt<double>
00025 ProfileInfoExecCount(
00026     "profile-estimator-loop-weight", cl::init(10),
00027     cl::value_desc("loop-weight"),
00028     cl::desc("Number of loop executions used for profile-estimator")
00029 );
00030 
00031 namespace {
00032   class VISIBILITY_HIDDEN ProfileEstimatorPass :
00033       public FunctionPass, public ProfileInfo {
00034     double ExecCount;
00035     LoopInfo *LI;
00036     std::set<BasicBlock*>  BBisVisited;
00037     std::map<Loop*,double> LoopExitWeights;
00038   public:
00039     static char ID; // Class identification, replacement for typeinfo
00040     explicit ProfileEstimatorPass(const double execcount = 0)
00041       : FunctionPass(&ID), ExecCount(execcount) {
00042       if (execcount == 0) ExecCount = ProfileInfoExecCount;
00043     }
00044 
00045     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00046       AU.setPreservesAll();
00047       AU.addRequired<LoopInfo>();
00048     }
00049 
00050     virtual const char *getPassName() const {
00051       return "Profiling information estimator";
00052     }
00053 
00054     /// run - Estimate the profile information from the specified file.
00055     virtual bool runOnFunction(Function &F);
00056 
00057     virtual void recurseBasicBlock(BasicBlock *BB);
00058   };
00059 }  // End of anonymous namespace
00060 
00061 char ProfileEstimatorPass::ID = 0;
00062 static RegisterPass<ProfileEstimatorPass>
00063 X("profile-estimator", "Estimate profiling information", false, true);
00064 
00065 static RegisterAnalysisGroup<ProfileInfo> Y(X);
00066 
00067 namespace llvm {
00068   const PassInfo *ProfileEstimatorPassID = &X;
00069 
00070   FunctionPass *createProfileEstimatorPass() {
00071     return new ProfileEstimatorPass();
00072   }
00073 
00074   // createProfileEstimatorPass - This function returns a Pass that estimates
00075   // profiling information using the given loop execution count.
00076   Pass *createProfileEstimatorPass(const unsigned execcount) {
00077     return new ProfileEstimatorPass(execcount);
00078   }
00079 }
00080 
00081 static double ignoreMissing(double w) {
00082   if (w == ProfileInfo::MissingValue) return 0;
00083   return w;
00084 }
00085 
00086 #define EDGE_ERROR(V1,V2) \
00087   DEBUG(errs() << "-- Edge (" <<(V1)->getName() << "," << (V2)->getName() \
00088         << ") is not calculated, returning\n")
00089 
00090 #define EDGE_WEIGHT(E) \
00091   DEBUG(errs() << "-- Weight of Edge ("                                 \
00092         << ((E).first ? (E).first->getNameStr() : "0")                  \
00093         << "," << (E).second->getName() << "):"                         \
00094         << getEdgeWeight(E) << "\n")
00095 
00096 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
00097 // single block and then recurses into the successors.
00098 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
00099 
00100   // break recursion if already visited
00101   if (BBisVisited.find(BB) != BBisVisited.end()) return;
00102 
00103   // check if uncalculated incoming edges are calculated already, if BB is
00104   // header allow backedges
00105   bool  BBisHeader = LI->isLoopHeader(BB);
00106   Loop* BBLoop     = LI->getLoopFor(BB);
00107 
00108   double BBWeight = 0;
00109   std::set<BasicBlock*> ProcessedPreds;
00110   for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
00111         bbi != bbe; ++bbi ) {
00112     if (ProcessedPreds.insert(*bbi).second) {
00113       Edge edge = getEdge(*bbi,BB);
00114       BBWeight += ignoreMissing(getEdgeWeight(edge));
00115     }
00116     if (BBisHeader && BBLoop == LI->getLoopFor(*bbi)) {
00117       EDGE_ERROR(*bbi,BB);
00118       continue;
00119     }
00120     if (BBisVisited.find(*bbi) == BBisVisited.end()) {
00121       EDGE_ERROR(*bbi,BB);
00122       return;
00123     }
00124   }
00125   if (getExecutionCount(BB) != MissingValue) {
00126     BBWeight = getExecutionCount(BB);
00127   }
00128 
00129   // fetch all necessary information for current block
00130   SmallVector<Edge, 8> ExitEdges;
00131   SmallVector<Edge, 8> Edges;
00132   if (BBLoop) {
00133     BBLoop->getExitEdges(ExitEdges);
00134   }
00135 
00136   // if block is an loop header, first subtract all weigths from edges that
00137   // exit this loop, then distribute remaining weight on to the edges exiting
00138   // this loop. finally the weight of the block is increased, to simulate
00139   // several executions of this loop
00140   if (BBisHeader) {
00141     double incoming = BBWeight;
00142     // subtract the flow leaving the loop
00143     for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
00144          ee = ExitEdges.end(); ei != ee; ++ei) {
00145       double w = getEdgeWeight(*ei);
00146       if (w == MissingValue) {
00147         Edges.push_back(*ei);
00148       } else {
00149         incoming -= w;
00150       }
00151     }
00152     // distribute remaining weight onto the exit edges
00153     for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
00154          ei != ee; ++ei) {
00155       EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
00156       EDGE_WEIGHT(*ei);
00157     }
00158     // increase flow into the loop
00159     BBWeight *= (ExecCount+1);
00160   }
00161 
00162   // remove from current flow of block all the successor edges that already
00163   // have some flow on them
00164   Edges.clear();
00165   std::set<BasicBlock*> ProcessedSuccs;
00166   for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
00167         bbi != bbe; ++bbi ) {
00168     if (ProcessedSuccs.insert(*bbi).second) {
00169       Edge edge = getEdge(BB,*bbi);
00170       double w = getEdgeWeight(edge);
00171       if (w != MissingValue) {
00172         BBWeight -= getEdgeWeight(edge);
00173       } else {
00174         Edges.push_back(edge);
00175       }
00176     }
00177   }
00178 
00179   // distribute remaining flow onto the outgoing edges
00180   for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
00181        ei != ee; ++ei) {
00182     EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
00183     EDGE_WEIGHT(*ei);
00184   }
00185 
00186   // mark as visited and recurse into subnodes
00187   BBisVisited.insert(BB);
00188   for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
00189         bbi != bbe;
00190         ++bbi ) {
00191     recurseBasicBlock(*bbi);
00192   }
00193 }
00194 
00195 bool ProfileEstimatorPass::runOnFunction(Function &F) {
00196   if (F.isDeclaration()) return false;
00197 
00198   LI = &getAnalysis<LoopInfo>();
00199   FunctionInformation.erase(&F);
00200   BlockInformation[&F].clear();
00201   EdgeInformation[&F].clear();
00202   BBisVisited.clear();
00203 
00204   DEBUG(errs() << "Working on function " << F.getName() << "\n");
00205 
00206   // since the entry block is the first one and has no predecessors, the edge
00207   // (0,entry) is inserted with the starting weight of 1
00208   BasicBlock *entry = &F.getEntryBlock();
00209   BlockInformation[&F][entry] = 1;
00210 
00211   Edge edge = getEdge(0,entry);
00212   EdgeInformation[&F][edge] = 1; EDGE_WEIGHT(edge);
00213   recurseBasicBlock(entry);
00214 
00215   // in case something went wrong, clear all results, not profiling info
00216   // available
00217   if (BBisVisited.size() != F.size()) {
00218     DEBUG(errs() << "-- could not estimate profile, using default profile\n");
00219     FunctionInformation.erase(&F);
00220     BlockInformation[&F].clear();
00221     for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
00222       for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
00223            bbi != bbe; ++bbi) {
00224         Edge e = getEdge(*bbi,BB);
00225         EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);
00226       }
00227       for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
00228            bbi != bbe; ++bbi) {
00229         Edge e = getEdge(BB,*bbi);
00230         EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);
00231       }
00232     }
00233   }
00234 
00235   return false;
00236 }