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. In case the block has no successors
 172   // create a (BB,0) edge.
 173   succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 174   if (bbi == bbe) {
 175     Edge edge = getEdge(BB,0);
 176     EdgeInformation[BB->getParent()][edge] = BBWeight;
 177     printEdgeWeight(edge);
 178   }
 179   for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 180         bbi != bbe; ++bbi ) {
 181     if (ProcessedSuccs.insert(*bbi).second) {
 182       Edge edge = getEdge(BB,*bbi);
 183       double w = getEdgeWeight(edge);
 184       if (w != MissingValue) {
 185         BBWeight -= getEdgeWeight(edge);
 186       } else {
 187         Edges.push_back(edge);
 188       }
 189     }
 190   }
 191
 192   // Distribute remaining flow onto the outgoing edges.
 193   for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 194        ei != ee; ++ei) {
 195     EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
 196     printEdgeWeight(*ei);
 197   }
 198
 199   // Mark this Block visited and recurse into successors.
 200   BBisVisited.insert(BB);
 201   for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 202         bbi != bbe;
 203         ++bbi ) {
 204     recurseBasicBlock(*bbi);
 205   }
 206 }
 207
 208 bool ProfileEstimatorPass::runOnFunction(Function &F) {
 209   if (F.isDeclaration()) return false;
 210
 211   LI = &getAnalysis<LoopInfo>();
 212   FunctionInformation.erase(&F);
 213   BlockInformation[&F].clear();
 214   EdgeInformation[&F].clear();
 215   BBisVisited.clear();
 216
 217   DEBUG(errs() << "Working on function " << F.getNameStr() << "\n");
 218
 219   // Since the entry block is the first one and has no predecessors, the edge
 220   // (0,entry) is inserted with the starting weight of 1.
 221   BasicBlock *entry = &F.getEntryBlock();
 222   BlockInformation[&F][entry] = 1;
 223
 224   Edge edge = getEdge(0,entry);
 225   EdgeInformation[&F][edge] = 1; printEdgeWeight(edge);
 226   recurseBasicBlock(entry);
 227
 228   // In case something went wrong, clear all results, not profiling info is
 229   // available.
 230   if (BBisVisited.size() != F.size()) {
 231     DEBUG(errs() << "-- could not estimate profile, using default profile\n");
 232     FunctionInformation.erase(&F);
 233     BlockInformation[&F].clear();
 234     for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
 235       for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 236            bbi != bbe; ++bbi) {
 237         Edge e = getEdge(*bbi,BB);
 238         EdgeInformation[&F][e] = 1;
 239         printEdgeWeight(e);
 240       }
 241       for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 242            bbi != bbe; ++bbi) {
 243         Edge e = getEdge(BB,*bbi);
 244         EdgeInformation[&F][e] = 1;
 245         printEdgeWeight(e);
 246       }
 247     }
 248   }
 249
 250   return false;
 251 }