Make ProfileEstimator more robust on general CFGs.
[oota-llvm.git] / lib / Analysis / ProfileEstimatorPass.cpp
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"
23 using namespace llvm;
24
25 static cl::opt<double>
26 LoopWeight(
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
32 namespace {
33   class VISIBILITY_HIDDEN ProfileEstimatorPass :
34       public FunctionPass, public ProfileInfo {
35     double ExecCount;
36     LoopInfo *LI;
37     std::set<BasicBlock*>  BBisVisited;
38     std::map<Loop*,double> LoopExitWeights;
39   public:
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;
44     }
45
46     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
47       AU.setPreservesAll();
48       AU.addRequired<LoopInfo>();
49     }
50
51     virtual const char *getPassName() const {
52       return "Profiling information estimator";
53     }
54
55     /// run - Estimate the profile information from the specified file.
56     virtual bool runOnFunction(Function &F);
57
58     BasicBlock *recurseBasicBlock(BasicBlock *BB);
59
60     void inline printEdgeWeight(Edge);
61   };
62 }  // End of anonymous namespace
63
64 char ProfileEstimatorPass::ID = 0;
65 static RegisterPass<ProfileEstimatorPass>
66 X("profile-estimator", "Estimate profiling information", false, true);
67
68 static RegisterAnalysisGroup<ProfileInfo> Y(X);
69
70 namespace llvm {
71   const PassInfo *ProfileEstimatorPassID = &X;
72
73   FunctionPass *createProfileEstimatorPass() {
74     return new ProfileEstimatorPass();
75   }
76
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);
81   }
82 }
83
84 static double ignoreMissing(double w) {
85   if (w == ProfileInfo::MissingValue) return 0;
86   return w;
87 }
88
89 static void inline printEdgeError(ProfileInfo::Edge e) {
90   DEBUG(errs() << "-- Edge " << e << " is not calculated, returning\n");
91 }
92
93 void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
94   DEBUG(errs() << "-- Weight of Edge " << E << ":"
95                << format("%g", getEdgeWeight(E)) << "\n");
96 }
97
98 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
99 // single block and then recurses into the successors.
100 BasicBlock* ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
101
102   // Break the recursion if this BasicBlock was already visited.
103   if (BBisVisited.find(BB) != BBisVisited.end()) return 0;
104
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);
109
110   double BBWeight = 0;
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);
118     }
119     if (BBisHeader && BBLoop->contains(*bbi)) {
120       printEdgeError(edge);
121       continue;
122     }
123     if (w == MissingValue) {
124       printEdgeError(edge);
125       return BB;
126     }
127   }
128   if (getExecutionCount(BB) != MissingValue) {
129     BBWeight = getExecutionCount(BB);
130   }
131
132   // Fetch all necessary information for current block.
133   SmallVector<Edge, 8> ExitEdges;
134   SmallVector<Edge, 8> Edges;
135   if (BBLoop) {
136     BBLoop->getExitEdges(ExitEdges);
137   }
138
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.
143   if (BBisHeader) {
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);
153         } else {
154           incoming -= w;
155         }
156       }
157     }
158     // If no exit edges, create one:
159     if (Edges.size() == 0) {
160       BasicBlock *Latch = BBLoop->getLoopLatch();
161       if (Latch) {
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);
168       }
169     }
170
171     // Distribute remaining weight onto the exit edges.
172     for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
173          ei != ee; ++ei) {
174       EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
175       printEdgeWeight(*ei);
176     }
177     // Increase flow into the loop.
178     BBWeight *= (ExecCount+1);
179   }
180
181   // Remove from current flow of block all the successor edges that already
182   // have some flow on them.
183   Edges.clear();
184   std::set<BasicBlock*> ProcessedSuccs;
185
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);
190   if (bbi == bbe) {
191     Edge edge = getEdge(BB,0);
192     EdgeInformation[BB->getParent()][edge] = BBWeight;
193     printEdgeWeight(edge);
194   }
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);
201       } else {
202         Edges.push_back(edge);
203       }
204     }
205   }
206
207   // Distribute remaining flow onto the outgoing edges.
208   for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
209        ei != ee; ++ei) {
210     EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
211     printEdgeWeight(*ei);
212   }
213
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);
220     if (!Uncalculated) 
221       Uncalculated = ret;
222   }
223   if (BBisVisited.find(Uncalculated) != BBisVisited.end())
224     return 0;
225   return Uncalculated;
226 }
227
228 bool ProfileEstimatorPass::runOnFunction(Function &F) {
229   if (F.isDeclaration()) return false;
230
231   LI = &getAnalysis<LoopInfo>();
232   FunctionInformation.erase(&F);
233   BlockInformation[&F].clear();
234   EdgeInformation[&F].clear();
235   BBisVisited.clear();
236
237   DEBUG(errs() << "Working on function " << F.getNameStr() << "\n");
238
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;
243
244   Edge edge = getEdge(0,entry);
245   EdgeInformation[&F][edge] = 1; printEdgeWeight(edge);
246   BasicBlock *BB = entry;
247   while (BB) {
248     BB = recurseBasicBlock(BB);
249     if (BB) {
250       for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
251            bbi != bbe; ++bbi) {
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: ";
257           printEdgeWeight(e);
258         }
259       }
260     }
261   }
262
263   return false;
264 }