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     std::map<Edge,double>  MinimalWeight;
  39   public:
  40     static char ID; // Class identification, replacement for typeinfo
  41     explicit ProfileEstimatorPass(const double execcount = 0)
  42         : FunctionPass(ID), ExecCount(execcount) {
  43       initializeProfileEstimatorPassPass(*PassRegistry::getPassRegistry());
  44       if (execcount == 0) ExecCount = LoopWeight;
  45     }
  46
  47     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  48       AU.setPreservesAll();
  49       AU.addRequired<LoopInfo>();
  50     }
  51
  52     virtual const char *getPassName() const {
  53       return "Profiling information estimator";
  54     }
  55
  56     /// run - Estimate the profile information from the specified file.
  57     virtual bool runOnFunction(Function &F);
  58
  59     /// getAdjustedAnalysisPointer - This method is used when a pass implements
  60     /// an analysis interface through multiple inheritance.  If needed, it
  61     /// should override this to adjust the this pointer as needed for the
  62     /// specified pass info.
  63     virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
  64       if (PI == &ProfileInfo::ID)
  65         return (ProfileInfo*)this;
  66       return this;
  67     }
  68
  69     virtual void recurseBasicBlock(BasicBlock *BB);
  70
  71     void inline printEdgeWeight(Edge);
  72   };
  73 }  // End of anonymous namespace
  74
  75 char ProfileEstimatorPass::ID = 0;
  76 INITIALIZE_AG_PASS_BEGIN(ProfileEstimatorPass, ProfileInfo, "profile-estimator",
  77                 "Estimate profiling information", false, true, false)
  78 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
  79 INITIALIZE_AG_PASS_END(ProfileEstimatorPass, ProfileInfo, "profile-estimator",
  80                 "Estimate profiling information", false, true, false)
  81
  82 namespace llvm {
  83   char &ProfileEstimatorPassID = ProfileEstimatorPass::ID;
  84
  85   FunctionPass *createProfileEstimatorPass() {
  86     return new ProfileEstimatorPass();
  87   }
  88
  89   /// createProfileEstimatorPass - This function returns a Pass that estimates
  90   /// profiling information using the given loop execution count.
  91   Pass *createProfileEstimatorPass(const unsigned execcount) {
  92     return new ProfileEstimatorPass(execcount);
  93   }
  94 }
  95
  96 static double ignoreMissing(double w) {
  97   if (w == ProfileInfo::MissingValue) return 0;
  98   return w;
  99 }
 100
 101 static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
 102   DEBUG(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n");
 103 }
 104
 105 void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
 106   DEBUG(dbgs() << "-- Weight of Edge " << E << ":"
 107                << format("%20.20g", getEdgeWeight(E)) << "\n");
 108 }
 109
 110 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
 111 // single block and then recurses into the successors.
 112 // The algorithm preserves the flow condition, meaning that the sum of the
 113 // weight of the incoming edges must be equal the block weight which must in
 114 // turn be equal to the sume of the weights of the outgoing edges.
 115 // Since the flow of an block is deterimined from the current state of the
 116 // flow, once an edge has a flow assigned this flow is never changed again,
 117 // otherwise it would be possible to violate the flow condition in another
 118 // block.
 119 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
 120
 121   // Break the recursion if this BasicBlock was already visited.
 122   if (BBToVisit.find(BB) == BBToVisit.end()) return;
 123
 124   // Read the LoopInfo for this block.
 125   bool  BBisHeader = LI->isLoopHeader(BB);
 126   Loop* BBLoop     = LI->getLoopFor(BB);
 127
 128   // To get the block weight, read all incoming edges.
 129   double BBWeight = 0;
 130   std::set<BasicBlock*> ProcessedPreds;
 131   for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 132         bbi != bbe; ++bbi ) {
 133     // If this block was not considered already, add weight.
 134     Edge edge = getEdge(*bbi,BB);
 135     double w = getEdgeWeight(edge);
 136     if (ProcessedPreds.insert(*bbi).second) {
 137       BBWeight += ignoreMissing(w);
 138     }
 139     // If this block is a loop header and the predecessor is contained in this
 140     // loop, thus the edge is a backedge, continue and do not check if the
 141     // value is valid.
 142     if (BBisHeader && BBLoop->contains(*bbi)) {
 143       printEdgeError(edge, "but is backedge, continueing");
 144       continue;
 145     }
 146     // If the edges value is missing (and this is no loop header, and this is
 147     // no backedge) return, this block is currently non estimatable.
 148     if (w == MissingValue) {
 149       printEdgeError(edge, "returning");
 150       return;
 151     }
 152   }
 153   if (getExecutionCount(BB) != MissingValue) {
 154     BBWeight = getExecutionCount(BB);
 155   }
 156
 157   // Fetch all necessary information for current block.
 158   SmallVector<Edge, 8> ExitEdges;
 159   SmallVector<Edge, 8> Edges;
 160   if (BBLoop) {
 161     BBLoop->getExitEdges(ExitEdges);
 162   }
 163
 164   // If this is a loop header, consider the following:
 165   // Exactly the flow that is entering this block, must exit this block too. So
 166   // do the following:
 167   // *) get all the exit edges, read the flow that is already leaving this
 168   // loop, remember the edges that do not have any flow on them right now.
 169   // (The edges that have already flow on them are most likely exiting edges of
 170   // other loops, do not touch those flows because the previously caclulated
 171   // loopheaders would not be exact anymore.)
 172   // *) In case there is not a single exiting edge left, create one at the loop
 173   // latch to prevent the flow from building up in the loop.
 174   // *) Take the flow that is not leaving the loop already and distribute it on
 175   // the remaining exiting edges.
 176   // (This ensures that all flow that enters the loop also leaves it.)
 177   // *) Increase the flow into the loop by increasing the weight of this block.
 178   // There is at least one incoming backedge that will bring us this flow later
 179   // on. (So that the flow condition in this node is valid again.)
 180   if (BBisHeader) {
 181     double incoming = BBWeight;
 182     // Subtract the flow leaving the loop.
 183     std::set<Edge> ProcessedExits;
 184     for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
 185          ee = ExitEdges.end(); ei != ee; ++ei) {
 186       if (ProcessedExits.insert(*ei).second) {
 187         double w = getEdgeWeight(*ei);
 188         if (w == MissingValue) {
 189           Edges.push_back(*ei);
 190           // Check if there is a necessary minimal weight, if yes, subtract it
 191           // from weight.
 192           if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
 193             incoming -= MinimalWeight[*ei];
 194             DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
 195           }
 196         } else {
 197           incoming -= w;
 198         }
 199       }
 200     }
 201     // If no exit edges, create one:
 202     if (Edges.size() == 0) {
 203       BasicBlock *Latch = BBLoop->getLoopLatch();
 204       if (Latch) {
 205         Edge edge = getEdge(Latch,0);
 206         EdgeInformation[BB->getParent()][edge] = BBWeight;
 207         printEdgeWeight(edge);
 208         edge = getEdge(Latch, BB);
 209         EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount;
 210         printEdgeWeight(edge);
 211       }
 212     }
 213
 214     // Distribute remaining weight to the exting edges. To prevent fractions
 215     // from building up and provoking precision problems the weight which is to
 216     // be distributed is split and the rounded, the last edge gets a somewhat
 217     // bigger value, but we are close enough for an estimation.
 218     double fraction = floor(incoming/Edges.size());
 219     for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 220          ei != ee; ++ei) {
 221       double w = 0;
 222       if (ei != (ee-1)) {
 223         w = fraction;
 224         incoming -= fraction;
 225       } else {
 226         w = incoming;
 227       }
 228       EdgeInformation[BB->getParent()][*ei] += w;
 229       // Read necessary minimal weight.
 230       if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
 231         EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
 232         DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
 233       }
 234       printEdgeWeight(*ei);
 235
 236       // Add minimal weight to paths to all exit edges, this is used to ensure
 237       // that enough flow is reaching this edges.
 238       Path p;
 239       const BasicBlock *Dest = GetPath(BB, (*ei).first, p, GetPathToDest);
 240       while (Dest != BB) {
 241         const BasicBlock *Parent = p.find(Dest)->second;
 242         Edge e = getEdge(Parent, Dest);
 243         if (MinimalWeight.find(e) == MinimalWeight.end()) {
 244           MinimalWeight[e] = 0;
 245         }
 246         MinimalWeight[e] += w;
 247         DEBUG(dbgs() << "Minimal Weight for " << e << ": " << format("%.20g",MinimalWeight[e]) << "\n");
 248         Dest = Parent;
 249       }
 250     }
 251     // Increase flow into the loop.
 252     BBWeight *= (ExecCount+1);
 253   }
 254
 255   BlockInformation[BB->getParent()][BB] = BBWeight;
 256   // Up until now we considered only the loop exiting edges, now we have a
 257   // definite block weight and must distribute this onto the outgoing edges.
 258   // Since there may be already flow attached to some of the edges, read this
 259   // flow first and remember the edges that have still now flow attached.
 260   Edges.clear();
 261   std::set<BasicBlock*> ProcessedSuccs;
 262
 263   succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 264   // Also check for (BB,0) edges that may already contain some flow. (But only
 265   // in case there are no successors.)
 266   if (bbi == bbe) {
 267     Edge edge = getEdge(BB,0);
 268     EdgeInformation[BB->getParent()][edge] = BBWeight;
 269     printEdgeWeight(edge);
 270   }
 271   for ( ; bbi != bbe; ++bbi ) {
 272     if (ProcessedSuccs.insert(*bbi).second) {
 273       Edge edge = getEdge(BB,*bbi);
 274       double w = getEdgeWeight(edge);
 275       if (w != MissingValue) {
 276         BBWeight -= getEdgeWeight(edge);
 277       } else {
 278         Edges.push_back(edge);
 279         // If minimal weight is necessary, reserve weight by subtracting weight
 280         // from block weight, this is readded later on.
 281         if (MinimalWeight.find(edge) != MinimalWeight.end()) {
 282           BBWeight -= MinimalWeight[edge];
 283           DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[edge]) << " at " << edge << "\n");
 284         }
 285       }
 286     }
 287   }
 288
 289   double fraction = floor(BBWeight/Edges.size());
 290   // Finally we know what flow is still not leaving the block, distribute this
 291   // flow onto the empty edges.
 292   for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 293        ei != ee; ++ei) {
 294     if (ei != (ee-1)) {
 295       EdgeInformation[BB->getParent()][*ei] += fraction;
 296       BBWeight -= fraction;
 297     } else {
 298       EdgeInformation[BB->getParent()][*ei] += BBWeight;
 299     }
 300     // Readd minial necessary weight.
 301     if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
 302       EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
 303       DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
 304     }
 305     printEdgeWeight(*ei);
 306   }
 307
 308   // This block is visited, mark this before the recursion.
 309   BBToVisit.erase(BB);
 310
 311   // Recurse into successors.
 312   for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 313        bbi != bbe; ++bbi) {
 314     recurseBasicBlock(*bbi);
 315   }
 316 }
 317
 318 bool ProfileEstimatorPass::runOnFunction(Function &F) {
 319   if (F.isDeclaration()) return false;
 320
 321   // Fetch LoopInfo and clear ProfileInfo for this function.
 322   LI = &getAnalysis<LoopInfo>();
 323   FunctionInformation.erase(&F);
 324   BlockInformation[&F].clear();
 325   EdgeInformation[&F].clear();
 326
 327   // Mark all blocks as to visit.
 328   for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
 329     BBToVisit.insert(bi);
 330
 331   // Clear Minimal Edges.
 332   MinimalWeight.clear();
 333
 334   DEBUG(dbgs() << "Working on function " << F.getNameStr() << "\n");
 335
 336   // Since the entry block is the first one and has no predecessors, the edge
 337   // (0,entry) is inserted with the starting weight of 1.
 338   BasicBlock *entry = &F.getEntryBlock();
 339   BlockInformation[&F][entry] = pow(2.0, 32.0);
 340   Edge edge = getEdge(0,entry);
 341   EdgeInformation[&F][edge] = BlockInformation[&F][entry];
 342   printEdgeWeight(edge);
 343
 344   // Since recurseBasicBlock() maybe returns with a block which was not fully
 345   // estimated, use recurseBasicBlock() until everything is calculated.
 346   bool cleanup = false;
 347   recurseBasicBlock(entry);
 348   while (BBToVisit.size() > 0 && !cleanup) {
 349     // Remember number of open blocks, this is later used to check if progress
 350     // was made.
 351     unsigned size = BBToVisit.size();
 352
 353     // Try to calculate all blocks in turn.
 354     for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(),
 355          be = BBToVisit.end(); bi != be; ++bi) {
 356       recurseBasicBlock(*bi);
 357       // If at least one block was finished, break because iterator may be
 358       // invalid.
 359       if (BBToVisit.size() < size) break;
 360     }
 361
 362     // If there was not a single block resolved, make some assumptions.
 363     if (BBToVisit.size() == size) {
 364       bool found = false;
 365       for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end();
 366            (BBI != BBE) && (!found); ++BBI) {
 367         BasicBlock *BB = *BBI;
 368         // Try each predecessor if it can be assumend.
 369         for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 370              (bbi != bbe) && (!found); ++bbi) {
 371           Edge e = getEdge(*bbi,BB);
 372           double w = getEdgeWeight(e);
 373           // Check that edge from predecessor is still free.
 374           if (w == MissingValue) {
 375             // Check if there is a circle from this block to predecessor.
 376             Path P;
 377             const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest);
 378             if (Dest != *bbi) {
 379               // If there is no circle, just set edge weight to 0
 380               EdgeInformation[&F][e] = 0;
 381               DEBUG(dbgs() << "Assuming edge weight: ");
 382               printEdgeWeight(e);
 383               found = true;
 384             }
 385           }
 386         }
 387       }
 388       if (!found) {
 389         cleanup = true;
 390         DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n");
 391       }
 392     }
 393   }
 394   // In case there was no safe way to assume edges, set as a last measure,
 395   // set _everything_ to zero.
 396   if (cleanup) {
 397     FunctionInformation[&F] = 0;
 398     BlockInformation[&F].clear();
 399     EdgeInformation[&F].clear();
 400     for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 401       const BasicBlock *BB = &(*FI);
 402       BlockInformation[&F][BB] = 0;
 403       const_pred_iterator predi = pred_begin(BB), prede = pred_end(BB);
 404       if (predi == prede) {
 405         Edge e = getEdge(0,BB);
 406         setEdgeWeight(e,0);
 407       }
 408       for (;predi != prede; ++predi) {
 409         Edge e = getEdge(*predi,BB);
 410         setEdgeWeight(e,0);
 411       }
 412       succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB);
 413       if (succi == succe) {
 414         Edge e = getEdge(BB,0);
 415         setEdgeWeight(e,0);
 416       }
 417       for (;succi != succe; ++succi) {
 418         Edge e = getEdge(*succi,BB);
 419         setEdgeWeight(e,0);
 420       }
 421     }
 422   }
 423
 424   return false;
 425 }