Home | History | Annotate | Download | only in Analysis
      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/Analysis/Passes.h"
     16 #include "llvm/Analysis/LoopInfo.h"
     17 #include "llvm/Analysis/ProfileInfo.h"
     18 #include "llvm/Pass.h"
     19 #include "llvm/Support/CommandLine.h"
     20 #include "llvm/Support/Debug.h"
     21 #include "llvm/Support/Format.h"
     22 #include "llvm/Support/raw_ostream.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, continuing");
    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 (SmallVectorImpl<Edge>::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 (SmallVectorImpl<Edge>::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 = Edges.size() ? floor(BBWeight/Edges.size()) : 0.0;
    290   // Finally we know what flow is still not leaving the block, distribute this
    291   // flow onto the empty edges.
    292   for (SmallVectorImpl<Edge>::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   BBToVisit.clear();
    327 
    328   // Mark all blocks as to visit.
    329   for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
    330     BBToVisit.insert(bi);
    331 
    332   // Clear Minimal Edges.
    333   MinimalWeight.clear();
    334 
    335   DEBUG(dbgs() << "Working on function " << F.getName() << "\n");
    336 
    337   // Since the entry block is the first one and has no predecessors, the edge
    338   // (0,entry) is inserted with the starting weight of 1.
    339   BasicBlock *entry = &F.getEntryBlock();
    340   BlockInformation[&F][entry] = pow(2.0, 32.0);
    341   Edge edge = getEdge(0,entry);
    342   EdgeInformation[&F][edge] = BlockInformation[&F][entry];
    343   printEdgeWeight(edge);
    344 
    345   // Since recurseBasicBlock() maybe returns with a block which was not fully
    346   // estimated, use recurseBasicBlock() until everything is calculated.
    347   bool cleanup = false;
    348   recurseBasicBlock(entry);
    349   while (BBToVisit.size() > 0 && !cleanup) {
    350     // Remember number of open blocks, this is later used to check if progress
    351     // was made.
    352     unsigned size = BBToVisit.size();
    353 
    354     // Try to calculate all blocks in turn.
    355     for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(),
    356          be = BBToVisit.end(); bi != be; ++bi) {
    357       recurseBasicBlock(*bi);
    358       // If at least one block was finished, break because iterator may be
    359       // invalid.
    360       if (BBToVisit.size() < size) break;
    361     }
    362 
    363     // If there was not a single block resolved, make some assumptions.
    364     if (BBToVisit.size() == size) {
    365       bool found = false;
    366       for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end();
    367            (BBI != BBE) && (!found); ++BBI) {
    368         BasicBlock *BB = *BBI;
    369         // Try each predecessor if it can be assumend.
    370         for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
    371              (bbi != bbe) && (!found); ++bbi) {
    372           Edge e = getEdge(*bbi,BB);
    373           double w = getEdgeWeight(e);
    374           // Check that edge from predecessor is still free.
    375           if (w == MissingValue) {
    376             // Check if there is a circle from this block to predecessor.
    377             Path P;
    378             const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest);
    379             if (Dest != *bbi) {
    380               // If there is no circle, just set edge weight to 0
    381               EdgeInformation[&F][e] = 0;
    382               DEBUG(dbgs() << "Assuming edge weight: ");
    383               printEdgeWeight(e);
    384               found = true;
    385             }
    386           }
    387         }
    388       }
    389       if (!found) {
    390         cleanup = true;
    391         DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n");
    392       }
    393     }
    394   }
    395   // In case there was no safe way to assume edges, set as a last measure,
    396   // set _everything_ to zero.
    397   if (cleanup) {
    398     FunctionInformation[&F] = 0;
    399     BlockInformation[&F].clear();
    400     EdgeInformation[&F].clear();
    401     for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
    402       const BasicBlock *BB = &(*FI);
    403       BlockInformation[&F][BB] = 0;
    404       const_pred_iterator predi = pred_begin(BB), prede = pred_end(BB);
    405       if (predi == prede) {
    406         Edge e = getEdge(0,BB);
    407         setEdgeWeight(e,0);
    408       }
    409       for (;predi != prede; ++predi) {
    410         Edge e = getEdge(*predi,BB);
    411         setEdgeWeight(e,0);
    412       }
    413       succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB);
    414       if (succi == succe) {
    415         Edge e = getEdge(BB,0);
    416         setEdgeWeight(e,0);
    417       }
    418       for (;succi != succe; ++succi) {
    419         Edge e = getEdge(*succi,BB);
    420         setEdgeWeight(e,0);
    421       }
    422     }
    423   }
    424 
    425   return false;
    426 }
    427