#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>
-ProfileInfoExecCount(
+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 {
+ class ProfileEstimatorPass : public FunctionPass, public ProfileInfo {
double ExecCount;
LoopInfo *LI;
- std::set<BasicBlock*> BBisVisited;
+ 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) {
- if (execcount == 0) ExecCount = ProfileInfoExecCount;
+ : FunctionPass(ID), ExecCount(execcount) {
+ initializeProfileEstimatorPassPass(*PassRegistry::getPassRegistry());
+ if (execcount == 0) ExecCount = LoopWeight;
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
/// 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;
-static RegisterPass<ProfileEstimatorPass>
-X("profile-estimator", "Estimate profiling information", false, true);
-
-static RegisterAnalysisGroup<ProfileInfo> Y(X);
+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 {
- const PassInfo *ProfileEstimatorPassID = &X;
+ 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.
+ /// 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);
}
return w;
}
-#define EDGE_ERROR(V1,V2) \
- DEBUG(errs() << "-- Edge (" <<(V1)->getName() << "," << (V2)->getName() \
- << ") is not calculated, returning\n")
+static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
+ DEBUG(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n");
+}
-#define EDGE_WEIGHT(E) \
- DEBUG(errs() << "-- Weight of Edge (" \
- << ((E).first ? (E).first->getNameStr() : "0") \
- << "," << (E).second->getName() << "):" \
- << getEdgeWeight(E) << "\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 recursion if already visited
- if (BBisVisited.find(BB) != BBisVisited.end()) return;
+ // Break the recursion if this BasicBlock was already visited.
+ if (BBToVisit.find(BB) == BBToVisit.end()) return;
- // check if uncalculated incoming edges are calculated already, if BB is
- // header allow backedges
+ // 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) {
- Edge edge = getEdge(*bbi,BB);
- BBWeight += ignoreMissing(getEdgeWeight(edge));
+ BBWeight += ignoreMissing(w);
}
- if (BBisHeader && BBLoop == LI->getLoopFor(*bbi)) {
- EDGE_ERROR(*bbi,BB);
+ // 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 (BBisVisited.find(*bbi) == BBisVisited.end()) {
- EDGE_ERROR(*bbi,BB);
+ // 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;
}
}
BBWeight = getExecutionCount(BB);
}
- // fetch all necessary information for current block
+ // Fetch all necessary information for current block.
SmallVector<Edge, 8> ExitEdges;
SmallVector<Edge, 8> Edges;
if (BBLoop) {
BBLoop->getExitEdges(ExitEdges);
}
- // if block is an loop header, first subtract all weigths from edges that
- // exit this loop, then distribute remaining weight on to the edges exiting
- // this loop. finally the weight of the block is increased, to simulate
- // several executions of this loop
+ // 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
+ // Subtract the flow leaving the loop.
+ std::set<Edge> ProcessedExits;
for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
ee = ExitEdges.end(); ei != ee; ++ei) {
- double w = getEdgeWeight(*ei);
- if (w == MissingValue) {
- Edges.push_back(*ei);
- } else {
- incoming -= w;
+ 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 onto the exit edges
+
+ // 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 (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
ei != ee; ++ei) {
- EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size();
- EDGE_WEIGHT(*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
+ // Increase flow into the loop.
BBWeight *= (ExecCount+1);
}
- // remove from current flow of block all the successor edges that already
- // have some flow on them
+ 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;
- for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
- bbi != bbe; ++bbi ) {
+
+ 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);
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");
+ }
}
}
}
- // distribute remaining flow onto the outgoing edges
+ double fraction = floor(BBWeight/Edges.size());
+ // 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();
- EDGE_WEIGHT(*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);
}
- // mark as visited and recurse into subnodes
- BBisVisited.insert(BB);
- for ( succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
- bbi != bbe;
- ++bbi ) {
+ // 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();
- BBisVisited.clear();
+ BBToVisit.clear();
- DEBUG(errs() << "Working on function " << F.getName() << "\n");
+ // Mark all blocks as to visit.
+ for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
+ BBToVisit.insert(bi);
- // 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;
+ // Clear Minimal Edges.
+ MinimalWeight.clear();
+ DEBUG(dbgs() << "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] = pow(2.0, 32.0);
Edge edge = getEdge(0,entry);
- EdgeInformation[&F][edge] = 1; EDGE_WEIGHT(edge);
+ 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();
- // in case something went wrong, clear all results, not profiling info
- // available
- if (BBisVisited.size() != F.size()) {
- DEBUG(errs() << "-- could not estimate profile, using default profile\n");
- FunctionInformation.erase(&F);
+ // 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();
- for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
- for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
- bbi != bbe; ++bbi) {
- Edge e = getEdge(*bbi,BB);
- EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);
+ 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 (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
- bbi != bbe; ++bbi) {
- Edge e = getEdge(BB,*bbi);
- EdgeInformation[&F][e] = 1; EDGE_WEIGHT(edge);
+ for (;succi != succe; ++succi) {
+ Edge e = getEdge(*succi,BB);
+ setEdgeWeight(e,0);
}
}
}
projects / oota-llvm.git / blobdiff