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