lib/Analysis/ProfileEstimatorPass.cpp

   1 //===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===//
   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 file implements a concrete implementation of profiling information that
  11 // estimates the profiling information in a very crude and unimaginative way.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 #define DEBUG_TYPE "profile-estimator"
  15 #include "llvm/Pass.h"
  16 #include "llvm/Analysis/Passes.h"
  17 #include "llvm/Analysis/ProfileInfo.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 using namespace llvm;
  23
  24 static cl::opt<double>
  25 ProfileInfoExecCount(
  26     "profile-estimator-loop-weight", cl::init(10),
  27     cl::value_desc("loop-weight"),
  28     cl::desc("Number of loop executions used for profile-estimator")
  29 );
  30
  31 namespace {
  32   class VISIBILITY_HIDDEN ProfileEstimatorPass :
  33       public FunctionPass, public ProfileInfo {
  34     double ExecCount;
  35     LoopInfo *LI;
  36     std::set<BasicBlock*>  BBisVisited;
  37     std::map<Loop*,double> LoopExitWeights;
  38   public:
  39     static char ID; // Class identification, replacement for typeinfo
  40     explicit ProfileEstimatorPass(const double execcount = 0)
  41       : FunctionPass(&ID), ExecCount(execcount) {
  42       if (execcount == 0) ExecCount = ProfileInfoExecCount;
  43     }
  44
  45     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  46       AU.setPreservesAll();
  47       AU.addRequired<LoopInfo>();
  48     }
  49
  50     virtual const char *getPassName() const {
  51       return "Profiling information estimator";
  52     }
  53
  54     /// run - Estimate the profile information from the specified file.
  55     virtual bool runOnFunction(Function &F);
  56
  57     virtual void recurseBasicBlock(BasicBlock *BB);
  58   };
  59 }  // End of anonymous namespace
  60
  61 char ProfileEstimatorPass::ID = 0;
  62 static RegisterPass<ProfileEstimatorPass>
  63 X("profile-estimator", "Estimate profiling information", false, true);
  64
  65 static RegisterAnalysisGroup<ProfileInfo> Y(X);
  66
  67 namespace llvm {
  68   const PassInfo *ProfileEstimatorPassID = &X;
  69
  70   FunctionPass *createProfileEstimatorPass() {
  71     return new ProfileEstimatorPass();
  72   }
  73
  74   // createProfileEstimatorPass - This function returns a Pass that estimates
  75   // profiling information using the given loop execution count.
  76   Pass *createProfileEstimatorPass(const unsigned execcount) {
  77     return new ProfileEstimatorPass(execcount);
  78   }
  79 }
  80
  81 static double ignoreMissing(double w) {
  82   if (w == ProfileInfo::MissingValue) return 0;
  83   return w;
  84 }
  85
  86 #define EDGE_ERROR(V1,V2) \
  87   DEBUG(errs() << "-- Edge (" <<(V1)->getName() << "," << (V2)->getName() \
  88         << ") is not calculated, returning\n")
  89
  90 #define EDGE_WEIGHT(E) \
  91   DEBUG(errs() << "-- Weight of Edge ("                                 \
  92         << ((E).first ? (E).first->getNameStr() : "0")                  \
  93         << "," << (E).second->getName() << "):"                         \
  94         << getEdgeWeight(E) << "\n")
  95
  96 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
  97 // single block and then recurses into the successors.
  98 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
  99
 100   // break recursion if already visited
 101   if (BBisVisited.find(BB) != BBisVisited.end()) return;
 102
 103   // check if uncalculated incoming edges are calculated already, if BB is
 104   // header allow backedges
 105   bool  BBisHeader = LI->isLoopHeader(BB);
 106   Loop* BBLoop     = LI->getLoopFor(BB);
 107
 108   double BBWeight = 0;
 109   std::set<BasicBlock*> ProcessedPreds;
 110   for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 111         bbi != bbe; ++bbi ) {
 112     if (ProcessedPreds.insert(*bbi).second) {
 113       Edge edge = getEdge(*bbi,BB);
 114       BBWeight += ignoreMissing(getEdgeWeight(edge));
 115     }
 116     if (BBisHeader && BBLoop == LI->getLoopFor(*bbi)) {
 117       EDGE_ERROR(*bbi,BB);
 118       continue;
 119     }
 120     if (BBisVisited.find(*bbi) == BBisVisited.end()) {
 121       EDGE_ERROR(*bbi,BB);
 122       return;
 123     }
 124   }
 125   if (getExecutionCount(BB) != MissingValue) {
 126     BBWeight = getExecutionCount(BB);
 127   }
 128
 129   // fetch all necessary information for current block
 130   SmallVector<Edge, 8> ExitEdges;
 131   SmallVector<Edge, 8> Edges;
 132   if (BBLoop) {
 133     BBLoop->getExitEdges(ExitEdges);
 134   }
 135
 136   // if block is an loop header, first subtract all weigths from edges that
 137   // exit this loop, then distribute remaining weight on to the edges exiting
 138   // this loop. finally the weight of the block is increased, to simulate
 139   // several executions of this loop
 140   if (BBisHeader) {
 141     double incoming = BBWeight;
 142     // subtract the flow leaving the loop
 143     for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
 144          ee = ExitEdges.end(); ei != ee; ++ei) {
 145       double w = getEdgeWeight(*ei);
 146       if (w == MissingValue) {
 147         Edges.push_back(*ei);
 148       } else {
 149         incoming -= w;
 150       }
 151     }
 152     // distribute remaining weight onto the exit edges
 153     for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 154          ei != ee; ++ei) {
 155       EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
 156       EDGE_WEIGHT(*ei);
 157     }
 158     // increase flow into the loop
 159     BBWeight *= (ExecCount+1);
 160   }
 161
 162   // remove from current flow of block all the successor edges that already
 163   // have some flow on them
 164   Edges.clear();
 165   std::set<BasicBlock*> ProcessedSuccs;
 166   for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 167         bbi != bbe; ++bbi ) {
 168     if (ProcessedSuccs.insert(*bbi).second) {
 169       Edge edge = getEdge(BB,*bbi);
 170       double w = getEdgeWeight(edge);
 171       if (w != MissingValue) {
 172         BBWeight -= getEdgeWeight(edge);
 173       } else {
 174         Edges.push_back(edge);
 175       }
 176     }
 177   }
 178
 179   // distribute remaining flow onto the outgoing edges
 180   for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 181        ei != ee; ++ei) {
 182     EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
 183     EDGE_WEIGHT(*ei);
 184   }
 185
 186   // mark as visited and recurse into subnodes
 187   BBisVisited.insert(BB);
 188   for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 189         bbi != bbe;
 190         ++bbi ) {
 191     recurseBasicBlock(*bbi);
 192   }
 193 }
 194
 195 bool ProfileEstimatorPass::runOnFunction(Function &F) {
 196   if (F.isDeclaration()) return false;
 197
 198   LI = &getAnalysis<LoopInfo>();
 199   FunctionInformation.erase(&F);
 200   BlockInformation[&F].clear();
 201   EdgeInformation[&F].clear();
 202   BBisVisited.clear();
 203
 204   DEBUG(errs() << "Working on function " << F.getName() << "\n");
 205
 206   // since the entry block is the first one and has no predecessors, the edge
 207   // (0,entry) is inserted with the starting weight of 1
 208   BasicBlock *entry = &F.getEntryBlock();
 209   BlockInformation[&F][entry] = 1;
 210
 211   Edge edge = getEdge(0,entry);
 212   EdgeInformation[&F][edge] = 1; EDGE_WEIGHT(edge);
 213   recurseBasicBlock(entry);
 214
 215   // in case something went wrong, clear all results, not profiling info
 216   // available
 217   if (BBisVisited.size() != F.size()) {
 218     DEBUG(errs() << "-- could not estimate profile, using default profile\n");
 219     FunctionInformation.erase(&F);
 220     BlockInformation[&F].clear();
 221     for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
 222       for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 223            bbi != bbe; ++bbi) {
 224         Edge e = getEdge(*bbi,BB);
 225         EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);
 226       }
 227       for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 228            bbi != bbe; ++bbi) {
 229         Edge e = getEdge(BB,*bbi);
 230         EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);
 231       }
 232     }
 233   }
 234
 235   return false;
 236 }