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;
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;
45 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
47 AU.addRequired<LoopInfo>();
50 virtual const char *getPassName() const {
51 return "Profiling information estimator";
54 /// run - Estimate the profile information from the specified file.
55 virtual bool runOnFunction(Function &F);
57 virtual void recurseBasicBlock(BasicBlock *BB);
59 void inline printEdgeWeight(Edge);
61 } // End of anonymous namespace
63 char ProfileEstimatorPass::ID = 0;
64 static RegisterPass<ProfileEstimatorPass>
65 X("profile-estimator", "Estimate profiling information", false, true);
67 static RegisterAnalysisGroup<ProfileInfo> Y(X);
70 const PassInfo *ProfileEstimatorPassID = &X;
72 FunctionPass *createProfileEstimatorPass() {
73 return new ProfileEstimatorPass();
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);
83 static double ignoreMissing(double w) {
84 if (w == ProfileInfo::MissingValue) return 0;
88 static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
89 DEBUG(errs() << "-- Edge " << e << " is not calculated, " << M << "\n");
92 void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
93 DEBUG(errs() << "-- Weight of Edge " << E << ":"
94 << format("%g", getEdgeWeight(E)) << "\n");
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
106 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
108 // Break the recursion if this BasicBlock was already visited.
109 if (BBToVisit.find(BB) == BBToVisit.end()) return;
111 // Read the LoopInfo for this block.
112 bool BBisHeader = LI->isLoopHeader(BB);
113 Loop* BBLoop = LI->getLoopFor(BB);
115 // To get the block weight, read all incoming edges.
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);
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
129 if (BBisHeader && BBLoop->contains(*bbi)) {
130 printEdgeError(edge, "but is backedge, continueing");
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");
140 if (getExecutionCount(BB) != MissingValue) {
141 BBWeight = getExecutionCount(BB);
144 // Fetch all necessary information for current block.
145 SmallVector<Edge, 8> ExitEdges;
146 SmallVector<Edge, 8> Edges;
148 BBLoop->getExitEdges(ExitEdges);
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
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.)
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);
182 // If no exit edges, create one:
183 if (Edges.size() == 0) {
184 BasicBlock *Latch = BBLoop->getLoopLatch();
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);
194 // Distribute remaining weight onto the exit edges.
195 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
197 EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
198 printEdgeWeight(*ei);
200 // Increase flow into the loop.
201 BBWeight *= (ExecCount+1);
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.
210 std::set<BasicBlock*> ProcessedSuccs;
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.)
216 Edge edge = getEdge(BB,0);
217 EdgeInformation[BB->getParent()][edge] = BBWeight;
218 printEdgeWeight(edge);
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);
227 Edges.push_back(edge);
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();
236 EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
237 printEdgeWeight(*ei);
240 // This block is visited, mark this before the recursion.
243 // Recurse into successors.
244 for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
246 recurseBasicBlock(*bbi);
250 bool ProfileEstimatorPass::runOnFunction(Function &F) {
251 if (F.isDeclaration()) return false;
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();
259 // Mark all blocks as to visit.
260 for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
261 BBToVisit.insert(bi);
263 DEBUG(errs() << "Working on function " << F.getNameStr() << "\n");
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);
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
279 unsigned size = BBToVisit.size();
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
287 if (BBToVisit.size() < size) break;
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);
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: ");