summaryrefslogtreecommitdiffstats
path: root/lib/Analysis/ProfileEstimatorPass.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/ProfileEstimatorPass.cpp')
-rw-r--r--lib/Analysis/ProfileEstimatorPass.cpp310
1 files changed, 310 insertions, 0 deletions
diff --git a/lib/Analysis/ProfileEstimatorPass.cpp b/lib/Analysis/ProfileEstimatorPass.cpp
new file mode 100644
index 0000000..c585c1d
--- /dev/null
+++ b/lib/Analysis/ProfileEstimatorPass.cpp
@@ -0,0 +1,310 @@
+//===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a concrete implementation of profiling information that
+// estimates the profiling information in a very crude and unimaginative way.
+//
+//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "profile-estimator"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/ProfileInfo.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Format.h"
+using namespace llvm;
+
+static cl::opt<double>
+LoopWeight(
+ "profile-estimator-loop-weight", cl::init(10),
+ cl::value_desc("loop-weight"),
+ cl::desc("Number of loop executions used for profile-estimator")
+);
+
+namespace {
+ class VISIBILITY_HIDDEN ProfileEstimatorPass :
+ public FunctionPass, public ProfileInfo {
+ double ExecCount;
+ LoopInfo *LI;
+ std::set<BasicBlock*> BBToVisit;
+ std::map<Loop*,double> LoopExitWeights;
+ public:
+ static char ID; // Class identification, replacement for typeinfo
+ explicit ProfileEstimatorPass(const double execcount = 0)
+ : FunctionPass(&ID), ExecCount(execcount) {
+ if (execcount == 0) ExecCount = LoopWeight;
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<LoopInfo>();
+ }
+
+ virtual const char *getPassName() const {
+ return "Profiling information estimator";
+ }
+
+ /// run - Estimate the profile information from the specified file.
+ virtual bool runOnFunction(Function &F);
+
+ virtual void recurseBasicBlock(BasicBlock *BB);
+
+ void inline printEdgeWeight(Edge);
+ };
+} // End of anonymous namespace
+
+char ProfileEstimatorPass::ID = 0;
+static RegisterPass<ProfileEstimatorPass>
+X("profile-estimator", "Estimate profiling information", false, true);
+
+static RegisterAnalysisGroup<ProfileInfo> Y(X);
+
+namespace llvm {
+ const PassInfo *ProfileEstimatorPassID = &X;
+
+ FunctionPass *createProfileEstimatorPass() {
+ return new ProfileEstimatorPass();
+ }
+
+ /// createProfileEstimatorPass - This function returns a Pass that estimates
+ /// profiling information using the given loop execution count.
+ Pass *createProfileEstimatorPass(const unsigned execcount) {
+ return new ProfileEstimatorPass(execcount);
+ }
+}
+
+static double ignoreMissing(double w) {
+ if (w == ProfileInfo::MissingValue) return 0;
+ return w;
+}
+
+static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
+ DEBUG(errs() << "-- Edge " << e << " is not calculated, " << M << "\n");
+}
+
+void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
+ DEBUG(errs() << "-- Weight of Edge " << E << ":"
+ << format("%g", getEdgeWeight(E)) << "\n");
+}
+
+// recurseBasicBlock() - This calculates the ProfileInfo estimation for a
+// single block and then recurses into the successors.
+// The algorithm preserves the flow condition, meaning that the sum of the
+// weight of the incoming edges must be equal the block weight which must in
+// turn be equal to the sume of the weights of the outgoing edges.
+// Since the flow of an block is deterimined from the current state of the
+// flow, once an edge has a flow assigned this flow is never changed again,
+// otherwise it would be possible to violate the flow condition in another
+// block.
+void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
+
+ // Break the recursion if this BasicBlock was already visited.
+ if (BBToVisit.find(BB) == BBToVisit.end()) return;
+
+ // Read the LoopInfo for this block.
+ bool BBisHeader = LI->isLoopHeader(BB);
+ Loop* BBLoop = LI->getLoopFor(BB);
+
+ // To get the block weight, read all incoming edges.
+ double BBWeight = 0;
+ std::set<BasicBlock*> ProcessedPreds;
+ for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
+ bbi != bbe; ++bbi ) {
+ // If this block was not considered already, add weight.
+ Edge edge = getEdge(*bbi,BB);
+ double w = getEdgeWeight(edge);
+ if (ProcessedPreds.insert(*bbi).second) {
+ BBWeight += ignoreMissing(w);
+ }
+ // If this block is a loop header and the predecessor is contained in this
+ // loop, thus the edge is a backedge, continue and do not check if the
+ // value is valid.
+ if (BBisHeader && BBLoop->contains(*bbi)) {
+ printEdgeError(edge, "but is backedge, continueing");
+ continue;
+ }
+ // If the edges value is missing (and this is no loop header, and this is
+ // no backedge) return, this block is currently non estimatable.
+ if (w == MissingValue) {
+ printEdgeError(edge, "returning");
+ return;
+ }
+ }
+ if (getExecutionCount(BB) != MissingValue) {
+ BBWeight = getExecutionCount(BB);
+ }
+
+ // Fetch all necessary information for current block.
+ SmallVector<Edge, 8> ExitEdges;
+ SmallVector<Edge, 8> Edges;
+ if (BBLoop) {
+ BBLoop->getExitEdges(ExitEdges);
+ }
+
+ // If this is a loop header, consider the following:
+ // Exactly the flow that is entering this block, must exit this block too. So
+ // do the following:
+ // *) get all the exit edges, read the flow that is already leaving this
+ // loop, remember the edges that do not have any flow on them right now.
+ // (The edges that have already flow on them are most likely exiting edges of
+ // other loops, do not touch those flows because the previously caclulated
+ // loopheaders would not be exact anymore.)
+ // *) In case there is not a single exiting edge left, create one at the loop
+ // latch to prevent the flow from building up in the loop.
+ // *) Take the flow that is not leaving the loop already and distribute it on
+ // the remaining exiting edges.
+ // (This ensures that all flow that enters the loop also leaves it.)
+ // *) Increase the flow into the loop by increasing the weight of this block.
+ // There is at least one incoming backedge that will bring us this flow later
+ // on. (So that the flow condition in this node is valid again.)
+ if (BBisHeader) {
+ double incoming = BBWeight;
+ // Subtract the flow leaving the loop.
+ std::set<Edge> ProcessedExits;
+ for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
+ ee = ExitEdges.end(); ei != ee; ++ei) {
+ if (ProcessedExits.insert(*ei).second) {
+ double w = getEdgeWeight(*ei);
+ if (w == MissingValue) {
+ Edges.push_back(*ei);
+ } else {
+ incoming -= w;
+ }
+ }
+ }
+ // If no exit edges, create one:
+ if (Edges.size() == 0) {
+ BasicBlock *Latch = BBLoop->getLoopLatch();
+ if (Latch) {
+ Edge edge = getEdge(Latch,0);
+ EdgeInformation[BB->getParent()][edge] = BBWeight;
+ printEdgeWeight(edge);
+ edge = getEdge(Latch, BB);
+ EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount;
+ printEdgeWeight(edge);
+ }
+ }
+ // Distribute remaining weight onto the exit edges.
+ for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
+ ei != ee; ++ei) {
+ EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
+ printEdgeWeight(*ei);
+ }
+ // Increase flow into the loop.
+ BBWeight *= (ExecCount+1);
+ }
+
+ BlockInformation[BB->getParent()][BB] = BBWeight;
+ // Up until now we considered only the loop exiting edges, now we have a
+ // definite block weight and must ditribute this onto the outgoing edges.
+ // Since there may be already flow attached to some of the edges, read this
+ // flow first and remember the edges that have still now flow attached.
+ Edges.clear();
+ std::set<BasicBlock*> ProcessedSuccs;
+
+ succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
+ // Also check for (BB,0) edges that may already contain some flow. (But only
+ // in case there are no successors.)
+ if (bbi == bbe) {
+ Edge edge = getEdge(BB,0);
+ EdgeInformation[BB->getParent()][edge] = BBWeight;
+ printEdgeWeight(edge);
+ }
+ for ( ; bbi != bbe; ++bbi ) {
+ if (ProcessedSuccs.insert(*bbi).second) {
+ Edge edge = getEdge(BB,*bbi);
+ double w = getEdgeWeight(edge);
+ if (w != MissingValue) {
+ BBWeight -= getEdgeWeight(edge);
+ } else {
+ Edges.push_back(edge);
+ }
+ }
+ }
+
+ // Finally we know what flow is still not leaving the block, distribute this
+ // flow onto the empty edges.
+ for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
+ ei != ee; ++ei) {
+ EdgeInformation[BB->getParent()][*ei] += BBWeight/Edges.size();
+ printEdgeWeight(*ei);
+ }
+
+ // This block is visited, mark this before the recursion.
+ BBToVisit.erase(BB);
+
+ // Recurse into successors.
+ for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
+ bbi != bbe; ++bbi) {
+ recurseBasicBlock(*bbi);
+ }
+}
+
+bool ProfileEstimatorPass::runOnFunction(Function &F) {
+ if (F.isDeclaration()) return false;
+
+ // Fetch LoopInfo and clear ProfileInfo for this function.
+ LI = &getAnalysis<LoopInfo>();
+ FunctionInformation.erase(&F);
+ BlockInformation[&F].clear();
+ EdgeInformation[&F].clear();
+
+ // Mark all blocks as to visit.
+ for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
+ BBToVisit.insert(bi);
+
+ DEBUG(errs() << "Working on function " << F.getNameStr() << "\n");
+
+ // Since the entry block is the first one and has no predecessors, the edge
+ // (0,entry) is inserted with the starting weight of 1.
+ BasicBlock *entry = &F.getEntryBlock();
+ BlockInformation[&F][entry] = 1;
+ Edge edge = getEdge(0,entry);
+ EdgeInformation[&F][edge] = 1;
+ printEdgeWeight(edge);
+
+ // Since recurseBasicBlock() maybe returns with a block which was not fully
+ // estimated, use recurseBasicBlock() until everything is calculated.
+ recurseBasicBlock(entry);
+ while (BBToVisit.size() > 0) {
+ // Remember number of open blocks, this is later used to check if progress
+ // was made.
+ unsigned size = BBToVisit.size();
+
+ // Try to calculate all blocks in turn.
+ for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(),
+ be = BBToVisit.end(); bi != be; ++bi) {
+ recurseBasicBlock(*bi);
+ // If at least one block was finished, break because iterator may be
+ // invalid.
+ if (BBToVisit.size() < size) break;
+ }
+
+ // If there was not a single block resovled, make some assumptions.
+ if (BBToVisit.size() == size) {
+ BasicBlock *BB = *(BBToVisit.begin());
+ // Since this BB was not calculated because of missing incoming edges,
+ // set these edges to zero.
+ for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
+ bbi != bbe; ++bbi) {
+ Edge e = getEdge(*bbi,BB);
+ double w = getEdgeWeight(e);
+ if (w == MissingValue) {
+ EdgeInformation[&F][e] = 0;
+ DEBUG(errs() << "Assuming edge weight: ");
+ printEdgeWeight(e);
+ }
+ }
+ }
+ }
+
+ return false;
+}
OpenPOWER on IntegriCloud