ProfileEstimatorPass.cpp revision 6726b6d75a8b679068a58cb954ba97cf9d1690ba
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" 23using namespace llvm; 24 25static cl::opt<double> 26LoopWeight( 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 32namespace { 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 63char ProfileEstimatorPass::ID = 0; 64static RegisterPass<ProfileEstimatorPass> 65X("profile-estimator", "Estimate profiling information", false, true); 66 67static RegisterAnalysisGroup<ProfileInfo> Y(X); 68 69namespace 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 83static double ignoreMissing(double w) { 84 if (w == ProfileInfo::MissingValue) return 0; 85 return w; 86} 87 88static void inline printEdgeError(ProfileInfo::Edge e, const char *M) { 89 DEBUG(errs() << "-- Edge " << e << " is not calculated, " << M << "\n"); 90} 91 92void 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. 106void 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 250bool 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} 310