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 VISIBILITY_HIDDEN ProfileEstimatorPass :
34 public FunctionPass, public ProfileInfo {
37 std::set<BasicBlock*> BBisVisited;
38 std::map<Loop*,double> LoopExitWeights;
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 BasicBlock *recurseBasicBlock(BasicBlock *BB);
60 void inline printEdgeWeight(Edge);
62 } // End of anonymous namespace
64 char ProfileEstimatorPass::ID = 0;
65 static RegisterPass<ProfileEstimatorPass>
66 X("profile-estimator", "Estimate profiling information", false, true);
68 static RegisterAnalysisGroup<ProfileInfo> Y(X);
71 const PassInfo *ProfileEstimatorPassID = &X;
73 FunctionPass *createProfileEstimatorPass() {
74 return new ProfileEstimatorPass();
77 /// createProfileEstimatorPass - This function returns a Pass that estimates
78 /// profiling information using the given loop execution count.
79 Pass *createProfileEstimatorPass(const unsigned execcount) {
80 return new ProfileEstimatorPass(execcount);
84 static double ignoreMissing(double w) {
85 if (w == ProfileInfo::MissingValue) return 0;
89 static void inline printEdgeError(ProfileInfo::Edge e) {
90 DEBUG(errs() << "-- Edge " << e << " is not calculated, returning\n");
93 void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
94 DEBUG(errs() << "-- Weight of Edge " << E << ":"
95 << format("%g", getEdgeWeight(E)) << "\n");
98 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
99 // single block and then recurses into the successors.
100 BasicBlock* ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
102 // Break the recursion if this BasicBlock was already visited.
103 if (BBisVisited.find(BB) != BBisVisited.end()) return 0;
105 // Check if incoming edges are calculated already, if BB is header allow
106 // backedges that are uncalculated for now.
107 bool BBisHeader = LI->isLoopHeader(BB);
108 Loop* BBLoop = LI->getLoopFor(BB);
111 std::set<BasicBlock*> ProcessedPreds;
112 for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
113 bbi != bbe; ++bbi ) {
114 Edge edge = getEdge(*bbi,BB);
115 double w = getEdgeWeight(edge);
116 if (ProcessedPreds.insert(*bbi).second) {
117 BBWeight += ignoreMissing(w);
119 if (BBisHeader && BBLoop->contains(*bbi)) {
120 printEdgeError(edge);
123 if (w == MissingValue) {
124 printEdgeError(edge);
128 if (getExecutionCount(BB) != MissingValue) {
129 BBWeight = getExecutionCount(BB);
132 // Fetch all necessary information for current block.
133 SmallVector<Edge, 8> ExitEdges;
134 SmallVector<Edge, 8> Edges;
136 BBLoop->getExitEdges(ExitEdges);
139 // If block is an loop header, first subtract all weights from edges that
140 // exit this loop, then distribute remaining weight on to the edges exiting
141 // this loop. Finally the weight of the block is increased, to simulate
142 // several executions of this loop.
144 double incoming = BBWeight;
145 // Subtract the flow leaving the loop.
146 std::set<Edge> ProcessedExits;
147 for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
148 ee = ExitEdges.end(); ei != ee; ++ei) {
149 if (ProcessedExits.insert(*ei).second) {
150 double w = getEdgeWeight(*ei);
151 if (w == MissingValue) {
152 Edges.push_back(*ei);
158 // If no exit edges, create one:
159 if (Edges.size() == 0) {
160 BasicBlock *Latch = BBLoop->getLoopLatch();
162 Edge edge = getEdge(Latch,0);
163 EdgeInformation[BB->getParent()][edge] = BBWeight;
164 printEdgeWeight(edge);
165 edge = getEdge(Latch, BB);
166 EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount;
167 printEdgeWeight(edge);
171 // Distribute remaining weight onto the exit edges.
172 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
174 EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
175 printEdgeWeight(*ei);
177 // Increase flow into the loop.
178 BBWeight *= (ExecCount+1);
181 // Remove from current flow of block all the successor edges that already
182 // have some flow on them.
184 std::set<BasicBlock*> ProcessedSuccs;
186 // Otherwise consider weight of outgoing edges and store them for
187 // distribution of remaining weight. In case the block has no successors
188 // create a (BB,0) edge.
189 succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
191 Edge edge = getEdge(BB,0);
192 EdgeInformation[BB->getParent()][edge] = BBWeight;
193 printEdgeWeight(edge);
195 for ( ; bbi != bbe; ++bbi ) {
196 if (ProcessedSuccs.insert(*bbi).second) {
197 Edge edge = getEdge(BB,*bbi);
198 double w = getEdgeWeight(edge);
199 if (w != MissingValue) {
200 BBWeight -= getEdgeWeight(edge);
202 Edges.push_back(edge);
207 // Distribute remaining flow onto the outgoing edges.
208 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
210 EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
211 printEdgeWeight(*ei);
214 // Mark this Block visited and recurse into successors.
215 BBisVisited.insert(BB);
216 BasicBlock *Uncalculated = 0;
217 for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
218 bbi != bbe; ++bbi ) {
219 BasicBlock* ret = recurseBasicBlock(*bbi);
223 if (BBisVisited.find(Uncalculated) != BBisVisited.end())
228 bool ProfileEstimatorPass::runOnFunction(Function &F) {
229 if (F.isDeclaration()) return false;
231 LI = &getAnalysis<LoopInfo>();
232 FunctionInformation.erase(&F);
233 BlockInformation[&F].clear();
234 EdgeInformation[&F].clear();
237 DEBUG(errs() << "Working on function " << F.getNameStr() << "\n");
239 // Since the entry block is the first one and has no predecessors, the edge
240 // (0,entry) is inserted with the starting weight of 1.
241 BasicBlock *entry = &F.getEntryBlock();
242 BlockInformation[&F][entry] = 1;
244 Edge edge = getEdge(0,entry);
245 EdgeInformation[&F][edge] = 1; printEdgeWeight(edge);
246 BasicBlock *BB = entry;
248 BB = recurseBasicBlock(BB);
250 for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
252 Edge e = getEdge(*bbi,BB);
253 double w = getEdgeWeight(e);
254 if (w == MissingValue) {
255 EdgeInformation[&F][e] = 0;
256 errs() << "Assuming edge weight: ";