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 ProfileEstimatorPass : public FunctionPass, public ProfileInfo {
  34     double ExecCount;
  35     LoopInfo *LI;
  36     std::set<BasicBlock*>  BBToVisit;
  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 = LoopWeight;
  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     void inline printEdgeWeight(Edge);
  60   };
  61 }  // End of anonymous namespace
  62
  63 char ProfileEstimatorPass::ID = 0;
  64 static RegisterPass<ProfileEstimatorPass>
  65 X("profile-estimator", "Estimate profiling information", false, true);
  66
  67 static RegisterAnalysisGroup<ProfileInfo> Y(X);
  68
  69 namespace llvm {
  70   const PassInfo *ProfileEstimatorPassID = &X;
  71
  72   FunctionPass *createProfileEstimatorPass() {
  73     return new ProfileEstimatorPass();
  74   }
  75
  76   /// createProfileEstimatorPass - This function returns a Pass that estimates
  77   /// profiling information using the given loop execution count.
  78   Pass *createProfileEstimatorPass(const unsigned execcount) {
  79     return new ProfileEstimatorPass(execcount);
  80   }
  81 }
  82
  83 static double ignoreMissing(double w) {
  84   if (w == ProfileInfo::MissingValue) return 0;
  85   return w;
  86 }
  87
  88 static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
  89   DEBUG(errs() << "-- Edge " << e << " is not calculated, " << M << "\n");
  90 }
  91
  92 void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
  93   DEBUG(errs() << "-- Weight of Edge " << E << ":"
  94                << format("%g", getEdgeWeight(E)) << "\n");
  95 }
  96
  97 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
  98 // single block and then recurses into the successors.
  99 // The algorithm preserves the flow condition, meaning that the sum of the
 100 // weight of the incoming edges must be equal the block weight which must in
 101 // turn be equal to the sume of the weights of the outgoing edges.
 102 // Since the flow of an block is deterimined from the current state of the
 103 // flow, once an edge has a flow assigned this flow is never changed again,
 104 // otherwise it would be possible to violate the flow condition in another
 105 // block.
 106 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
 107
 108   // Break the recursion if this BasicBlock was already visited.
 109   if (BBToVisit.find(BB) == BBToVisit.end()) return;
 110
 111   // Read the LoopInfo for this block.
 112   bool  BBisHeader = LI->isLoopHeader(BB);
 113   Loop* BBLoop     = LI->getLoopFor(BB);
 114
 115   // To get the block weight, read all incoming edges.
 116   double BBWeight = 0;
 117   std::set<BasicBlock*> ProcessedPreds;
 118   for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 119         bbi != bbe; ++bbi ) {
 120     // If this block was not considered already, add weight.
 121     Edge edge = getEdge(*bbi,BB);
 122     double w = getEdgeWeight(edge);
 123     if (ProcessedPreds.insert(*bbi).second) {
 124       BBWeight += ignoreMissing(w);
 125     }
 126     // If this block is a loop header and the predecessor is contained in this
 127     // loop, thus the edge is a backedge, continue and do not check if the
 128     // value is valid.
 129     if (BBisHeader && BBLoop->contains(*bbi)) {
 130       printEdgeError(edge, "but is backedge, continueing");
 131       continue;
 132     }
 133     // If the edges value is missing (and this is no loop header, and this is
 134     // no backedge) return, this block is currently non estimatable.
 135     if (w == MissingValue) {
 136       printEdgeError(edge, "returning");
 137       return;
 138     }
 139   }
 140   if (getExecutionCount(BB) != MissingValue) {
 141     BBWeight = getExecutionCount(BB);
 142   }
 143
 144   // Fetch all necessary information for current block.
 145   SmallVector<Edge, 8> ExitEdges;
 146   SmallVector<Edge, 8> Edges;
 147   if (BBLoop) {
 148     BBLoop->getExitEdges(ExitEdges);
 149   }
 150
 151   // If this is a loop header, consider the following:
 152   // Exactly the flow that is entering this block, must exit this block too. So
 153   // do the following:
 154   // *) get all the exit edges, read the flow that is already leaving this
 155   // loop, remember the edges that do not have any flow on them right now.
 156   // (The edges that have already flow on them are most likely exiting edges of
 157   // other loops, do not touch those flows because the previously caclulated
 158   // loopheaders would not be exact anymore.)
 159   // *) In case there is not a single exiting edge left, create one at the loop
 160   // latch to prevent the flow from building up in the loop.
 161   // *) Take the flow that is not leaving the loop already and distribute it on
 162   // the remaining exiting edges.
 163   // (This ensures that all flow that enters the loop also leaves it.)
 164   // *) Increase the flow into the loop by increasing the weight of this block.
 165   // There is at least one incoming backedge that will bring us this flow later
 166   // on. (So that the flow condition in this node is valid again.)
 167   if (BBisHeader) {
 168     double incoming = BBWeight;
 169     // Subtract the flow leaving the loop.
 170     std::set<Edge> ProcessedExits;
 171     for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
 172          ee = ExitEdges.end(); ei != ee; ++ei) {
 173       if (ProcessedExits.insert(*ei).second) {
 174         double w = getEdgeWeight(*ei);
 175         if (w == MissingValue) {
 176           Edges.push_back(*ei);
 177         } else {
 178           incoming -= w;
 179         }
 180       }
 181     }
 182     // If no exit edges, create one:
 183     if (Edges.size() == 0) {
 184       BasicBlock *Latch = BBLoop->getLoopLatch();
 185       if (Latch) {
 186         Edge edge = getEdge(Latch,0);
 187         EdgeInformation[BB->getParent()][edge] = BBWeight;
 188         printEdgeWeight(edge);
 189         edge = getEdge(Latch, BB);
 190         EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount;
 191         printEdgeWeight(edge);
 192       }
 193     }
 194     // Distribute remaining weight onto the exit edges.
 195     for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 196          ei != ee; ++ei) {
 197       EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
 198       printEdgeWeight(*ei);
 199     }
 200     // Increase flow into the loop.
 201     BBWeight *= (ExecCount+1);
 202   }
 203
 204   BlockInformation[BB->getParent()][BB] = BBWeight;
 205   // Up until now we considered only the loop exiting edges, now we have a
 206   // definite block weight and must ditribute this onto the outgoing edges.
 207   // Since there may be already flow attached to some of the edges, read this
 208   // flow first and remember the edges that have still now flow attached.
 209   Edges.clear();
 210   std::set<BasicBlock*> ProcessedSuccs;
 211
 212   succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 213   // Also check for (BB,0) edges that may already contain some flow. (But only
 214   // in case there are no successors.)
 215   if (bbi == bbe) {
 216     Edge edge = getEdge(BB,0);
 217     EdgeInformation[BB->getParent()][edge] = BBWeight;
 218     printEdgeWeight(edge);
 219   }
 220   for ( ; bbi != bbe; ++bbi ) {
 221     if (ProcessedSuccs.insert(*bbi).second) {
 222       Edge edge = getEdge(BB,*bbi);
 223       double w = getEdgeWeight(edge);
 224       if (w != MissingValue) {
 225         BBWeight -= getEdgeWeight(edge);
 226       } else {
 227         Edges.push_back(edge);
 228       }
 229     }
 230   }
 231
 232   // Finally we know what flow is still not leaving the block, distribute this
 233   // flow onto the empty edges.
 234   for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 235        ei != ee; ++ei) {
 236     EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
 237     printEdgeWeight(*ei);
 238   }
 239
 240   // This block is visited, mark this before the recursion.
 241   BBToVisit.erase(BB);
 242
 243   // Recurse into successors.
 244   for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 245        bbi != bbe; ++bbi) {
 246     recurseBasicBlock(*bbi);
 247   }
 248 }
 249
 250 bool ProfileEstimatorPass::runOnFunction(Function &F) {
 251   if (F.isDeclaration()) return false;
 252
 253   // Fetch LoopInfo and clear ProfileInfo for this function.
 254   LI = &getAnalysis<LoopInfo>();
 255   FunctionInformation.erase(&F);
 256   BlockInformation[&F].clear();
 257   EdgeInformation[&F].clear();
 258
 259   // Mark all blocks as to visit.
 260   for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
 261     BBToVisit.insert(bi);
 262
 263   DEBUG(errs() << "Working on function " << F.getNameStr() << "\n");
 264
 265   // Since the entry block is the first one and has no predecessors, the edge
 266   // (0,entry) is inserted with the starting weight of 1.
 267   BasicBlock *entry = &F.getEntryBlock();
 268   BlockInformation[&F][entry] = 1;
 269   Edge edge = getEdge(0,entry);
 270   EdgeInformation[&F][edge] = 1;
 271   printEdgeWeight(edge);
 272
 273   // Since recurseBasicBlock() maybe returns with a block which was not fully
 274   // estimated, use recurseBasicBlock() until everything is calculated.
 275   recurseBasicBlock(entry);
 276   while (BBToVisit.size() > 0) {
 277     // Remember number of open blocks, this is later used to check if progress
 278     // was made.
 279     unsigned size = BBToVisit.size();
 280
 281     // Try to calculate all blocks in turn.
 282     for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(),
 283          be = BBToVisit.end(); bi != be; ++bi) {
 284       recurseBasicBlock(*bi);
 285       // If at least one block was finished, break because iterator may be
 286       // invalid.
 287       if (BBToVisit.size() < size) break;
 288     }
 289
 290     // If there was not a single block resovled, make some assumptions.
 291     if (BBToVisit.size() == size) {
 292       BasicBlock *BB = *(BBToVisit.begin());
 293       // Since this BB was not calculated because of missing incoming edges,
 294       // set these edges to zero.
 295       for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 296            bbi != bbe; ++bbi) {
 297         Edge e = getEdge(*bbi,BB);
 298         double w = getEdgeWeight(e);
 299         if (w == MissingValue) {
 300           EdgeInformation[&F][e] = 0;
 301           DEBUG(errs() << "Assuming edge weight: ");
 302           printEdgeWeight(e);
 303         }
 304       }
 305     }
 306   }
 307
 308   return false;
 309 }