X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FProfileEstimatorPass.cpp;h=b594e2ba55065e0a9ddc56b160e7a951d229a4f5;hb=3ca2ad11567f83883ae2719c5fac5afc30c7b3d1;hp=0efb5ac071b8feb25cd7a0e0b43ca2480c3a8aa4;hpb=55e354ac0e294bde258420f80a2cc11ea19db482;p=oota-llvm.git diff --git a/lib/Analysis/ProfileEstimatorPass.cpp b/lib/Analysis/ProfileEstimatorPass.cpp index 0efb5ac071b..b594e2ba550 100644 --- a/lib/Analysis/ProfileEstimatorPass.cpp +++ b/lib/Analysis/ProfileEstimatorPass.cpp @@ -19,27 +19,29 @@ #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 -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 BBisVisited; + std::set BBToVisit; std::map LoopExitWeights; + std::map 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 { @@ -54,25 +56,38 @@ namespace { /// 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 -X("profile-estimator", "Estimate profiling information", false, true); - -static RegisterAnalysisGroup 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); } @@ -83,42 +98,55 @@ static double ignoreMissing(double w) { 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 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; } } @@ -126,45 +154,121 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { BBWeight = getExecutionCount(BB); } - // fetch all necessary information for current block + // Fetch all necessary information for current block. SmallVector ExitEdges; SmallVector 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 ProcessedExits; for (SmallVector::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::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 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); @@ -172,22 +276,41 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { 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::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); } } @@ -195,39 +318,106 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { bool ProfileEstimatorPass::runOnFunction(Function &F) { if (F.isDeclaration()) return false; + // Fetch LoopInfo and clear ProfileInfo for this function. LI = &getAnalysis(); 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::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::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 "<