1 //===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a concrete implementation of profiling information that
11 // estimates the profiling information in a very crude and unimaginative way.
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"
25 static cl::opt<double>
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")
33 class ProfileEstimatorPass : public FunctionPass, public ProfileInfo {
36 std::set<BasicBlock*> BBToVisit;
37 std::map<Loop*,double> LoopExitWeights;
38 std::map<Edge,double> MinimalWeight;
40 static char ID; // Class identification, replacement for typeinfo
41 explicit ProfileEstimatorPass(const double execcount = 0)
42 : FunctionPass(ID), ExecCount(execcount) {
43 if (execcount == 0) ExecCount = LoopWeight;
46 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
48 AU.addRequired<LoopInfo>();
51 virtual const char *getPassName() const {
52 return "Profiling information estimator";
55 /// run - Estimate the profile information from the specified file.
56 virtual bool runOnFunction(Function &F);
58 /// getAdjustedAnalysisPointer - This method is used when a pass implements
59 /// an analysis interface through multiple inheritance. If needed, it
60 /// should override this to adjust the this pointer as needed for the
61 /// specified pass info.
62 virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
63 if (PI == &ProfileInfo::ID)
64 return (ProfileInfo*)this;
68 virtual void recurseBasicBlock(BasicBlock *BB);
70 void inline printEdgeWeight(Edge);
72 } // End of anonymous namespace
74 char ProfileEstimatorPass::ID = 0;
75 INITIALIZE_AG_PASS(ProfileEstimatorPass, ProfileInfo, "profile-estimator",
76 "Estimate profiling information", false, true, false);
79 char &ProfileEstimatorPassID = ProfileEstimatorPass::ID;
81 FunctionPass *createProfileEstimatorPass() {
82 return new ProfileEstimatorPass();
85 /// createProfileEstimatorPass - This function returns a Pass that estimates
86 /// profiling information using the given loop execution count.
87 Pass *createProfileEstimatorPass(const unsigned execcount) {
88 return new ProfileEstimatorPass(execcount);
92 static double ignoreMissing(double w) {
93 if (w == ProfileInfo::MissingValue) return 0;
97 static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
98 DEBUG(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n");
101 void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
102 DEBUG(dbgs() << "-- Weight of Edge " << E << ":"
103 << format("%20.20g", getEdgeWeight(E)) << "\n");
106 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
107 // single block and then recurses into the successors.
108 // The algorithm preserves the flow condition, meaning that the sum of the
109 // weight of the incoming edges must be equal the block weight which must in
110 // turn be equal to the sume of the weights of the outgoing edges.
111 // Since the flow of an block is deterimined from the current state of the
112 // flow, once an edge has a flow assigned this flow is never changed again,
113 // otherwise it would be possible to violate the flow condition in another
115 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
117 // Break the recursion if this BasicBlock was already visited.
118 if (BBToVisit.find(BB) == BBToVisit.end()) return;
120 // Read the LoopInfo for this block.
121 bool BBisHeader = LI->isLoopHeader(BB);
122 Loop* BBLoop = LI->getLoopFor(BB);
124 // To get the block weight, read all incoming edges.
126 std::set<BasicBlock*> ProcessedPreds;
127 for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
128 bbi != bbe; ++bbi ) {
129 // If this block was not considered already, add weight.
130 Edge edge = getEdge(*bbi,BB);
131 double w = getEdgeWeight(edge);
132 if (ProcessedPreds.insert(*bbi).second) {
133 BBWeight += ignoreMissing(w);
135 // If this block is a loop header and the predecessor is contained in this
136 // loop, thus the edge is a backedge, continue and do not check if the
138 if (BBisHeader && BBLoop->contains(*bbi)) {
139 printEdgeError(edge, "but is backedge, continueing");
142 // If the edges value is missing (and this is no loop header, and this is
143 // no backedge) return, this block is currently non estimatable.
144 if (w == MissingValue) {
145 printEdgeError(edge, "returning");
149 if (getExecutionCount(BB) != MissingValue) {
150 BBWeight = getExecutionCount(BB);
153 // Fetch all necessary information for current block.
154 SmallVector<Edge, 8> ExitEdges;
155 SmallVector<Edge, 8> Edges;
157 BBLoop->getExitEdges(ExitEdges);
160 // If this is a loop header, consider the following:
161 // Exactly the flow that is entering this block, must exit this block too. So
163 // *) get all the exit edges, read the flow that is already leaving this
164 // loop, remember the edges that do not have any flow on them right now.
165 // (The edges that have already flow on them are most likely exiting edges of
166 // other loops, do not touch those flows because the previously caclulated
167 // loopheaders would not be exact anymore.)
168 // *) In case there is not a single exiting edge left, create one at the loop
169 // latch to prevent the flow from building up in the loop.
170 // *) Take the flow that is not leaving the loop already and distribute it on
171 // the remaining exiting edges.
172 // (This ensures that all flow that enters the loop also leaves it.)
173 // *) Increase the flow into the loop by increasing the weight of this block.
174 // There is at least one incoming backedge that will bring us this flow later
175 // on. (So that the flow condition in this node is valid again.)
177 double incoming = BBWeight;
178 // Subtract the flow leaving the loop.
179 std::set<Edge> ProcessedExits;
180 for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
181 ee = ExitEdges.end(); ei != ee; ++ei) {
182 if (ProcessedExits.insert(*ei).second) {
183 double w = getEdgeWeight(*ei);
184 if (w == MissingValue) {
185 Edges.push_back(*ei);
186 // Check if there is a necessary minimal weight, if yes, subtract it
188 if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
189 incoming -= MinimalWeight[*ei];
190 DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
197 // If no exit edges, create one:
198 if (Edges.size() == 0) {
199 BasicBlock *Latch = BBLoop->getLoopLatch();
201 Edge edge = getEdge(Latch,0);
202 EdgeInformation[BB->getParent()][edge] = BBWeight;
203 printEdgeWeight(edge);
204 edge = getEdge(Latch, BB);
205 EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount;
206 printEdgeWeight(edge);
210 // Distribute remaining weight to the exting edges. To prevent fractions
211 // from building up and provoking precision problems the weight which is to
212 // be distributed is split and the rounded, the last edge gets a somewhat
213 // bigger value, but we are close enough for an estimation.
214 double fraction = floor(incoming/Edges.size());
215 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
220 incoming -= fraction;
224 EdgeInformation[BB->getParent()][*ei] += w;
225 // Read necessary minimal weight.
226 if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
227 EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
228 DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
230 printEdgeWeight(*ei);
232 // Add minimal weight to paths to all exit edges, this is used to ensure
233 // that enough flow is reaching this edges.
235 const BasicBlock *Dest = GetPath(BB, (*ei).first, p, GetPathToDest);
237 const BasicBlock *Parent = p.find(Dest)->second;
238 Edge e = getEdge(Parent, Dest);
239 if (MinimalWeight.find(e) == MinimalWeight.end()) {
240 MinimalWeight[e] = 0;
242 MinimalWeight[e] += w;
243 DEBUG(dbgs() << "Minimal Weight for " << e << ": " << format("%.20g",MinimalWeight[e]) << "\n");
247 // Increase flow into the loop.
248 BBWeight *= (ExecCount+1);
251 BlockInformation[BB->getParent()][BB] = BBWeight;
252 // Up until now we considered only the loop exiting edges, now we have a
253 // definite block weight and must distribute this onto the outgoing edges.
254 // Since there may be already flow attached to some of the edges, read this
255 // flow first and remember the edges that have still now flow attached.
257 std::set<BasicBlock*> ProcessedSuccs;
259 succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
260 // Also check for (BB,0) edges that may already contain some flow. (But only
261 // in case there are no successors.)
263 Edge edge = getEdge(BB,0);
264 EdgeInformation[BB->getParent()][edge] = BBWeight;
265 printEdgeWeight(edge);
267 for ( ; bbi != bbe; ++bbi ) {
268 if (ProcessedSuccs.insert(*bbi).second) {
269 Edge edge = getEdge(BB,*bbi);
270 double w = getEdgeWeight(edge);
271 if (w != MissingValue) {
272 BBWeight -= getEdgeWeight(edge);
274 Edges.push_back(edge);
275 // If minimal weight is necessary, reserve weight by subtracting weight
276 // from block weight, this is readded later on.
277 if (MinimalWeight.find(edge) != MinimalWeight.end()) {
278 BBWeight -= MinimalWeight[edge];
279 DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[edge]) << " at " << edge << "\n");
285 double fraction = floor(BBWeight/Edges.size());
286 // Finally we know what flow is still not leaving the block, distribute this
287 // flow onto the empty edges.
288 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
291 EdgeInformation[BB->getParent()][*ei] += fraction;
292 BBWeight -= fraction;
294 EdgeInformation[BB->getParent()][*ei] += BBWeight;
296 // Readd minial necessary weight.
297 if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
298 EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
299 DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
301 printEdgeWeight(*ei);
304 // This block is visited, mark this before the recursion.
307 // Recurse into successors.
308 for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
310 recurseBasicBlock(*bbi);
314 bool ProfileEstimatorPass::runOnFunction(Function &F) {
315 if (F.isDeclaration()) return false;
317 // Fetch LoopInfo and clear ProfileInfo for this function.
318 LI = &getAnalysis<LoopInfo>();
319 FunctionInformation.erase(&F);
320 BlockInformation[&F].clear();
321 EdgeInformation[&F].clear();
323 // Mark all blocks as to visit.
324 for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
325 BBToVisit.insert(bi);
327 // Clear Minimal Edges.
328 MinimalWeight.clear();
330 DEBUG(dbgs() << "Working on function " << F.getNameStr() << "\n");
332 // Since the entry block is the first one and has no predecessors, the edge
333 // (0,entry) is inserted with the starting weight of 1.
334 BasicBlock *entry = &F.getEntryBlock();
335 BlockInformation[&F][entry] = pow(2.0, 32.0);
336 Edge edge = getEdge(0,entry);
337 EdgeInformation[&F][edge] = BlockInformation[&F][entry];
338 printEdgeWeight(edge);
340 // Since recurseBasicBlock() maybe returns with a block which was not fully
341 // estimated, use recurseBasicBlock() until everything is calculated.
342 bool cleanup = false;
343 recurseBasicBlock(entry);
344 while (BBToVisit.size() > 0 && !cleanup) {
345 // Remember number of open blocks, this is later used to check if progress
347 unsigned size = BBToVisit.size();
349 // Try to calculate all blocks in turn.
350 for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(),
351 be = BBToVisit.end(); bi != be; ++bi) {
352 recurseBasicBlock(*bi);
353 // If at least one block was finished, break because iterator may be
355 if (BBToVisit.size() < size) break;
358 // If there was not a single block resolved, make some assumptions.
359 if (BBToVisit.size() == size) {
361 for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end();
362 (BBI != BBE) && (!found); ++BBI) {
363 BasicBlock *BB = *BBI;
364 // Try each predecessor if it can be assumend.
365 for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
366 (bbi != bbe) && (!found); ++bbi) {
367 Edge e = getEdge(*bbi,BB);
368 double w = getEdgeWeight(e);
369 // Check that edge from predecessor is still free.
370 if (w == MissingValue) {
371 // Check if there is a circle from this block to predecessor.
373 const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest);
375 // If there is no circle, just set edge weight to 0
376 EdgeInformation[&F][e] = 0;
377 DEBUG(dbgs() << "Assuming edge weight: ");
386 DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n");
390 // In case there was no safe way to assume edges, set as a last measure,
391 // set _everything_ to zero.
393 FunctionInformation[&F] = 0;
394 BlockInformation[&F].clear();
395 EdgeInformation[&F].clear();
396 for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
397 const BasicBlock *BB = &(*FI);
398 BlockInformation[&F][BB] = 0;
399 const_pred_iterator predi = pred_begin(BB), prede = pred_end(BB);
400 if (predi == prede) {
401 Edge e = getEdge(0,BB);
404 for (;predi != prede; ++predi) {
405 Edge e = getEdge(*predi,BB);
408 succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB);
409 if (succi == succe) {
410 Edge e = getEdge(BB,0);
413 for (;succi != succe; ++succi) {
414 Edge e = getEdge(*succi,BB);