aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis/ProfileEstimatorPass.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/ProfileEstimatorPass.cpp')
-rw-r--r--lib/Analysis/ProfileEstimatorPass.cpp426
1 files changed, 0 insertions, 426 deletions
diff --git a/lib/Analysis/ProfileEstimatorPass.cpp b/lib/Analysis/ProfileEstimatorPass.cpp
deleted file mode 100644
index 365b64c..0000000
--- a/lib/Analysis/ProfileEstimatorPass.cpp
+++ /dev/null
@@ -1,426 +0,0 @@
-//===- 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/Analysis/Passes.h"
-#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/ProfileInfo.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Format.h"
-#include "llvm/Support/raw_ostream.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 ProfileEstimatorPass : public FunctionPass, public ProfileInfo {
- double ExecCount;
- LoopInfo *LI;
- std::set<BasicBlock*> BBToVisit;
- std::map<Loop*,double> LoopExitWeights;
- std::map<Edge,double> MinimalWeight;
- public:
- static char ID; // Class identification, replacement for typeinfo
- explicit ProfileEstimatorPass(const double execcount = 0)
- : FunctionPass(ID), ExecCount(execcount) {
- initializeProfileEstimatorPassPass(*PassRegistry::getPassRegistry());
- 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);
-
- /// getAdjustedAnalysisPointer - This method is used when a pass implements
- /// an analysis interface through multiple inheritance. If needed, it
- /// should override this to adjust the this pointer as needed for the
- /// specified pass info.
- virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
- if (PI == &ProfileInfo::ID)
- return (ProfileInfo*)this;
- return this;
- }
-
- virtual void recurseBasicBlock(BasicBlock *BB);
-
- void inline printEdgeWeight(Edge);
- };
-} // End of anonymous namespace
-
-char ProfileEstimatorPass::ID = 0;
-INITIALIZE_AG_PASS_BEGIN(ProfileEstimatorPass, ProfileInfo, "profile-estimator",
- "Estimate profiling information", false, true, false)
-INITIALIZE_PASS_DEPENDENCY(LoopInfo)
-INITIALIZE_AG_PASS_END(ProfileEstimatorPass, ProfileInfo, "profile-estimator",
- "Estimate profiling information", false, true, false)
-
-namespace llvm {
- char &ProfileEstimatorPassID = ProfileEstimatorPass::ID;
-
- 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(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n");
-}
-
-void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
- DEBUG(dbgs() << "-- Weight of Edge " << E << ":"
- << format("%20.20g", 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, continuing");
- 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 (SmallVectorImpl<Edge>::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);
- // Check if there is a necessary minimal weight, if yes, subtract it
- // from weight.
- if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
- incoming -= MinimalWeight[*ei];
- DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
- }
- } 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 to the exting edges. To prevent fractions
- // from building up and provoking precision problems the weight which is to
- // be distributed is split and the rounded, the last edge gets a somewhat
- // bigger value, but we are close enough for an estimation.
- double fraction = floor(incoming/Edges.size());
- for (SmallVectorImpl<Edge>::iterator ei = Edges.begin(), ee = Edges.end();
- ei != ee; ++ei) {
- double w = 0;
- if (ei != (ee-1)) {
- w = fraction;
- incoming -= fraction;
- } else {
- w = incoming;
- }
- EdgeInformation[BB->getParent()][*ei] += w;
- // Read necessary minimal weight.
- if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
- EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
- DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
- }
- printEdgeWeight(*ei);
-
- // Add minimal weight to paths to all exit edges, this is used to ensure
- // that enough flow is reaching this edges.
- Path p;
- const BasicBlock *Dest = GetPath(BB, (*ei).first, p, GetPathToDest);
- while (Dest != BB) {
- const BasicBlock *Parent = p.find(Dest)->second;
- Edge e = getEdge(Parent, Dest);
- if (MinimalWeight.find(e) == MinimalWeight.end()) {
- MinimalWeight[e] = 0;
- }
- MinimalWeight[e] += w;
- DEBUG(dbgs() << "Minimal Weight for " << e << ": " << format("%.20g",MinimalWeight[e]) << "\n");
- Dest = Parent;
- }
- }
- // 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 distribute 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);
- // If minimal weight is necessary, reserve weight by subtracting weight
- // from block weight, this is readded later on.
- if (MinimalWeight.find(edge) != MinimalWeight.end()) {
- BBWeight -= MinimalWeight[edge];
- DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[edge]) << " at " << edge << "\n");
- }
- }
- }
- }
-
- double fraction = Edges.size() ? floor(BBWeight/Edges.size()) : 0.0;
- // Finally we know what flow is still not leaving the block, distribute this
- // flow onto the empty edges.
- for (SmallVectorImpl<Edge>::iterator ei = Edges.begin(), ee = Edges.end();
- ei != ee; ++ei) {
- if (ei != (ee-1)) {
- EdgeInformation[BB->getParent()][*ei] += fraction;
- BBWeight -= fraction;
- } else {
- EdgeInformation[BB->getParent()][*ei] += BBWeight;
- }
- // Readd minial necessary weight.
- if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
- EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
- DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
- }
- 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();
- BBToVisit.clear();
-
- // Mark all blocks as to visit.
- for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
- BBToVisit.insert(bi);
-
- // Clear Minimal Edges.
- MinimalWeight.clear();
-
- DEBUG(dbgs() << "Working on function " << F.getName() << "\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] = pow(2.0, 32.0);
- Edge edge = getEdge(0,entry);
- EdgeInformation[&F][edge] = BlockInformation[&F][entry];
- printEdgeWeight(edge);
-
- // Since recurseBasicBlock() maybe returns with a block which was not fully
- // estimated, use recurseBasicBlock() until everything is calculated.
- bool cleanup = false;
- recurseBasicBlock(entry);
- while (BBToVisit.size() > 0 && !cleanup) {
- // 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 resolved, make some assumptions.
- if (BBToVisit.size() == size) {
- bool found = false;
- for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end();
- (BBI != BBE) && (!found); ++BBI) {
- BasicBlock *BB = *BBI;
- // Try each predecessor if it can be assumend.
- for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
- (bbi != bbe) && (!found); ++bbi) {
- Edge e = getEdge(*bbi,BB);
- double w = getEdgeWeight(e);
- // Check that edge from predecessor is still free.
- if (w == MissingValue) {
- // Check if there is a circle from this block to predecessor.
- Path P;
- const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest);
- if (Dest != *bbi) {
- // If there is no circle, just set edge weight to 0
- EdgeInformation[&F][e] = 0;
- DEBUG(dbgs() << "Assuming edge weight: ");
- printEdgeWeight(e);
- found = true;
- }
- }
- }
- }
- if (!found) {
- cleanup = true;
- DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n");
- }
- }
- }
- // In case there was no safe way to assume edges, set as a last measure,
- // set _everything_ to zero.
- if (cleanup) {
- FunctionInformation[&F] = 0;
- BlockInformation[&F].clear();
- EdgeInformation[&F].clear();
- for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
- const BasicBlock *BB = &(*FI);
- BlockInformation[&F][BB] = 0;
- const_pred_iterator predi = pred_begin(BB), prede = pred_end(BB);
- if (predi == prede) {
- Edge e = getEdge(0,BB);
- setEdgeWeight(e,0);
- }
- for (;predi != prede; ++predi) {
- Edge e = getEdge(*predi,BB);
- setEdgeWeight(e,0);
- }
- succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB);
- if (succi == succe) {
- Edge e = getEdge(BB,0);
- setEdgeWeight(e,0);
- }
- for (;succi != succe; ++succi) {
- Edge e = getEdge(*succi,BB);
- setEdgeWeight(e,0);
- }
- }
- }
-
- return false;
-}
generated by cgit v1.1 at 2024-05-29 22:35:44 +0000