LLVM API Documentation
00001 //===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a concrete implementation of profiling information that 00011 // estimates the profiling information in a very crude and unimaginative way. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 #define DEBUG_TYPE "profile-estimator" 00015 #include "llvm/Pass.h" 00016 #include "llvm/Analysis/Passes.h" 00017 #include "llvm/Analysis/ProfileInfo.h" 00018 #include "llvm/Analysis/LoopInfo.h" 00019 #include "llvm/Support/CommandLine.h" 00020 #include "llvm/Support/Debug.h" 00021 #include "llvm/Support/raw_ostream.h" 00022 using namespace llvm; 00023 00024 static cl::opt<double> 00025 ProfileInfoExecCount( 00026 "profile-estimator-loop-weight", cl::init(10), 00027 cl::value_desc("loop-weight"), 00028 cl::desc("Number of loop executions used for profile-estimator") 00029 ); 00030 00031 namespace { 00032 class VISIBILITY_HIDDEN ProfileEstimatorPass : 00033 public FunctionPass, public ProfileInfo { 00034 double ExecCount; 00035 LoopInfo *LI; 00036 std::set<BasicBlock*> BBisVisited; 00037 std::map<Loop*,double> LoopExitWeights; 00038 public: 00039 static char ID; // Class identification, replacement for typeinfo 00040 explicit ProfileEstimatorPass(const double execcount = 0) 00041 : FunctionPass(&ID), ExecCount(execcount) { 00042 if (execcount == 0) ExecCount = ProfileInfoExecCount; 00043 } 00044 00045 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00046 AU.setPreservesAll(); 00047 AU.addRequired<LoopInfo>(); 00048 } 00049 00050 virtual const char *getPassName() const { 00051 return "Profiling information estimator"; 00052 } 00053 00054 /// run - Estimate the profile information from the specified file. 00055 virtual bool runOnFunction(Function &F); 00056 00057 virtual void recurseBasicBlock(BasicBlock *BB); 00058 }; 00059 } // End of anonymous namespace 00060 00061 char ProfileEstimatorPass::ID = 0; 00062 static RegisterPass<ProfileEstimatorPass> 00063 X("profile-estimator", "Estimate profiling information", false, true); 00064 00065 static RegisterAnalysisGroup<ProfileInfo> Y(X); 00066 00067 namespace llvm { 00068 const PassInfo *ProfileEstimatorPassID = &X; 00069 00070 FunctionPass *createProfileEstimatorPass() { 00071 return new ProfileEstimatorPass(); 00072 } 00073 00074 // createProfileEstimatorPass - This function returns a Pass that estimates 00075 // profiling information using the given loop execution count. 00076 Pass *createProfileEstimatorPass(const unsigned execcount) { 00077 return new ProfileEstimatorPass(execcount); 00078 } 00079 } 00080 00081 static double ignoreMissing(double w) { 00082 if (w == ProfileInfo::MissingValue) return 0; 00083 return w; 00084 } 00085 00086 #define EDGE_ERROR(V1,V2) \ 00087 DEBUG(errs() << "-- Edge (" <<(V1)->getName() << "," << (V2)->getName() \ 00088 << ") is not calculated, returning\n") 00089 00090 #define EDGE_WEIGHT(E) \ 00091 DEBUG(errs() << "-- Weight of Edge (" \ 00092 << ((E).first ? (E).first->getNameStr() : "0") \ 00093 << "," << (E).second->getName() << "):" \ 00094 << getEdgeWeight(E) << "\n") 00095 00096 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a 00097 // single block and then recurses into the successors. 00098 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { 00099 00100 // break recursion if already visited 00101 if (BBisVisited.find(BB) != BBisVisited.end()) return; 00102 00103 // check if uncalculated incoming edges are calculated already, if BB is 00104 // header allow backedges 00105 bool BBisHeader = LI->isLoopHeader(BB); 00106 Loop* BBLoop = LI->getLoopFor(BB); 00107 00108 double BBWeight = 0; 00109 std::set<BasicBlock*> ProcessedPreds; 00110 for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); 00111 bbi != bbe; ++bbi ) { 00112 if (ProcessedPreds.insert(*bbi).second) { 00113 Edge edge = getEdge(*bbi,BB); 00114 BBWeight += ignoreMissing(getEdgeWeight(edge)); 00115 } 00116 if (BBisHeader && BBLoop == LI->getLoopFor(*bbi)) { 00117 EDGE_ERROR(*bbi,BB); 00118 continue; 00119 } 00120 if (BBisVisited.find(*bbi) == BBisVisited.end()) { 00121 EDGE_ERROR(*bbi,BB); 00122 return; 00123 } 00124 } 00125 if (getExecutionCount(BB) != MissingValue) { 00126 BBWeight = getExecutionCount(BB); 00127 } 00128 00129 // fetch all necessary information for current block 00130 SmallVector<Edge, 8> ExitEdges; 00131 SmallVector<Edge, 8> Edges; 00132 if (BBLoop) { 00133 BBLoop->getExitEdges(ExitEdges); 00134 } 00135 00136 // if block is an loop header, first subtract all weigths from edges that 00137 // exit this loop, then distribute remaining weight on to the edges exiting 00138 // this loop. finally the weight of the block is increased, to simulate 00139 // several executions of this loop 00140 if (BBisHeader) { 00141 double incoming = BBWeight; 00142 // subtract the flow leaving the loop 00143 for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(), 00144 ee = ExitEdges.end(); ei != ee; ++ei) { 00145 double w = getEdgeWeight(*ei); 00146 if (w == MissingValue) { 00147 Edges.push_back(*ei); 00148 } else { 00149 incoming -= w; 00150 } 00151 } 00152 // distribute remaining weight onto the exit edges 00153 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end(); 00154 ei != ee; ++ei) { 00155 EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size(); 00156 EDGE_WEIGHT(*ei); 00157 } 00158 // increase flow into the loop 00159 BBWeight *= (ExecCount+1); 00160 } 00161 00162 // remove from current flow of block all the successor edges that already 00163 // have some flow on them 00164 Edges.clear(); 00165 std::set<BasicBlock*> ProcessedSuccs; 00166 for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 00167 bbi != bbe; ++bbi ) { 00168 if (ProcessedSuccs.insert(*bbi).second) { 00169 Edge edge = getEdge(BB,*bbi); 00170 double w = getEdgeWeight(edge); 00171 if (w != MissingValue) { 00172 BBWeight -= getEdgeWeight(edge); 00173 } else { 00174 Edges.push_back(edge); 00175 } 00176 } 00177 } 00178 00179 // distribute remaining flow onto the outgoing edges 00180 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end(); 00181 ei != ee; ++ei) { 00182 EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size(); 00183 EDGE_WEIGHT(*ei); 00184 } 00185 00186 // mark as visited and recurse into subnodes 00187 BBisVisited.insert(BB); 00188 for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 00189 bbi != bbe; 00190 ++bbi ) { 00191 recurseBasicBlock(*bbi); 00192 } 00193 } 00194 00195 bool ProfileEstimatorPass::runOnFunction(Function &F) { 00196 if (F.isDeclaration()) return false; 00197 00198 LI = &getAnalysis<LoopInfo>(); 00199 FunctionInformation.erase(&F); 00200 BlockInformation[&F].clear(); 00201 EdgeInformation[&F].clear(); 00202 BBisVisited.clear(); 00203 00204 DEBUG(errs() << "Working on function " << F.getName() << "\n"); 00205 00206 // since the entry block is the first one and has no predecessors, the edge 00207 // (0,entry) is inserted with the starting weight of 1 00208 BasicBlock *entry = &F.getEntryBlock(); 00209 BlockInformation[&F][entry] = 1; 00210 00211 Edge edge = getEdge(0,entry); 00212 EdgeInformation[&F][edge] = 1; EDGE_WEIGHT(edge); 00213 recurseBasicBlock(entry); 00214 00215 // in case something went wrong, clear all results, not profiling info 00216 // available 00217 if (BBisVisited.size() != F.size()) { 00218 DEBUG(errs() << "-- could not estimate profile, using default profile\n"); 00219 FunctionInformation.erase(&F); 00220 BlockInformation[&F].clear(); 00221 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) { 00222 for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); 00223 bbi != bbe; ++bbi) { 00224 Edge e = getEdge(*bbi,BB); 00225 EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge); 00226 } 00227 for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 00228 bbi != bbe; ++bbi) { 00229 Edge e = getEdge(BB,*bbi); 00230 EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge); 00231 } 00232 } 00233 } 00234 00235 return false; 00236 }