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"
24 static cl::opt<double>
26 "profile-estimator-loop-weight", cl::init(10),
27 cl::value_desc("loop-weight"),
28 cl::desc("Number of loop executions used for profile-estimator")
32 class VISIBILITY_HIDDEN ProfileEstimatorPass :
33 public FunctionPass, public ProfileInfo {
36 std::set<BasicBlock*> BBisVisited;
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 = ProfileInfoExecCount;
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 } // End of anonymous namespace
61 char ProfileEstimatorPass::ID = 0;
62 static RegisterPass<ProfileEstimatorPass>
63 X("profile-estimator", "Estimate profiling information", false, true);
65 static RegisterAnalysisGroup<ProfileInfo> Y(X);
68 const PassInfo *ProfileEstimatorPassID = &X;
70 FunctionPass *createProfileEstimatorPass() {
71 return new ProfileEstimatorPass();
74 // createProfileEstimatorPass - This function returns a Pass that estimates
75 // profiling information using the given loop execution count.
76 Pass *createProfileEstimatorPass(const unsigned execcount) {
77 return new ProfileEstimatorPass(execcount);
81 static double ignoreMissing(double w) {
82 if (w == ProfileInfo::MissingValue) return 0;
86 #define EDGE_ERROR(V1,V2) \
87 DEBUG(errs() << "-- Edge (" <<(V1)->getName() << "," << (V2)->getName() \
88 << ") is not calculated, returning\n")
90 #define EDGE_WEIGHT(E) \
91 DEBUG(errs() << "-- Weight of Edge (" \
92 << ((E).first ? (E).first->getNameStr() : "0") \
93 << "," << (E).second->getName() << "):" \
94 << getEdgeWeight(E) << "\n")
96 // recurseBasicBlock() - This calculates the ProfileInfo estimation for a
97 // single block and then recurses into the successors.
98 void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
100 // break recursion if already visited
101 if (BBisVisited.find(BB) != BBisVisited.end()) return;
103 // check if uncalculated incoming edges are calculated already, if BB is
104 // header allow backedges
105 bool BBisHeader = LI->isLoopHeader(BB);
106 Loop* BBLoop = LI->getLoopFor(BB);
109 std::set<BasicBlock*> ProcessedPreds;
110 for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
111 bbi != bbe; ++bbi ) {
112 if (ProcessedPreds.insert(*bbi).second) {
113 Edge edge = getEdge(*bbi,BB);
114 BBWeight += ignoreMissing(getEdgeWeight(edge));
116 if (BBisHeader && BBLoop == LI->getLoopFor(*bbi)) {
120 if (BBisVisited.find(*bbi) == BBisVisited.end()) {
125 if (getExecutionCount(BB) != MissingValue) {
126 BBWeight = getExecutionCount(BB);
129 // fetch all necessary information for current block
130 SmallVector<Edge, 8> ExitEdges;
131 SmallVector<Edge, 8> Edges;
133 BBLoop->getExitEdges(ExitEdges);
136 // if block is an loop header, first subtract all weigths from edges that
137 // exit this loop, then distribute remaining weight on to the edges exiting
138 // this loop. finally the weight of the block is increased, to simulate
139 // several executions of this loop
141 double incoming = BBWeight;
142 // subtract the flow leaving the loop
143 for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
144 ee = ExitEdges.end(); ei != ee; ++ei) {
145 double w = getEdgeWeight(*ei);
146 if (w == MissingValue) {
147 Edges.push_back(*ei);
152 // distribute remaining weight onto the exit edges
153 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
155 EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
158 // increase flow into the loop
159 BBWeight *= (ExecCount+1);
162 // remove from current flow of block all the successor edges that already
163 // have some flow on them
165 std::set<BasicBlock*> ProcessedSuccs;
166 for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
167 bbi != bbe; ++bbi ) {
168 if (ProcessedSuccs.insert(*bbi).second) {
169 Edge edge = getEdge(BB,*bbi);
170 double w = getEdgeWeight(edge);
171 if (w != MissingValue) {
172 BBWeight -= getEdgeWeight(edge);
174 Edges.push_back(edge);
179 // distribute remaining flow onto the outgoing edges
180 for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
182 EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
186 // mark as visited and recurse into subnodes
187 BBisVisited.insert(BB);
188 for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
191 recurseBasicBlock(*bbi);
195 bool ProfileEstimatorPass::runOnFunction(Function &F) {
196 if (F.isDeclaration()) return false;
198 LI = &getAnalysis<LoopInfo>();
199 FunctionInformation.erase(&F);
200 BlockInformation[&F].clear();
201 EdgeInformation[&F].clear();
204 DEBUG(errs() << "Working on function " << F.getName() << "\n");
206 // since the entry block is the first one and has no predecessors, the edge
207 // (0,entry) is inserted with the starting weight of 1
208 BasicBlock *entry = &F.getEntryBlock();
209 BlockInformation[&F][entry] = 1;
211 Edge edge = getEdge(0,entry);
212 EdgeInformation[&F][edge] = 1; EDGE_WEIGHT(edge);
213 recurseBasicBlock(entry);
215 // in case something went wrong, clear all results, not profiling info
217 if (BBisVisited.size() != F.size()) {
218 DEBUG(errs() << "-- could not estimate profile, using default profile\n");
219 FunctionInformation.erase(&F);
220 BlockInformation[&F].clear();
221 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
222 for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
224 Edge e = getEdge(*bbi,BB);
225 EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);
227 for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
229 Edge e = getEdge(BB,*bbi);
230 EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);