X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FProfileEstimatorPass.cpp;h=2b9afe307d1aefc00ca59d323034049bccfe1505;hb=09aa3f0ef35d9241c92439d74b8d5e9a81d814c2;hp=ef72383710dc25728d1fc1ff5c6bf2a5c00ecba4;hpb=19531d113c74d734a6e4128653ad694089e8981b;p=oota-llvm.git diff --git a/lib/Analysis/ProfileEstimatorPass.cpp b/lib/Analysis/ProfileEstimatorPass.cpp index ef72383710d..2b9afe307d1 100644 --- a/lib/Analysis/ProfileEstimatorPass.cpp +++ b/lib/Analysis/ProfileEstimatorPass.cpp @@ -30,16 +30,17 @@ LoopWeight( ); 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) { + : FunctionPass(ID), ExecCount(execcount) { + initializeProfileEstimatorPassPass(*PassRegistry::getPassRegistry()); if (execcount == 0) ExecCount = LoopWeight; } @@ -55,6 +56,16 @@ 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); @@ -62,13 +73,14 @@ namespace { } // 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(); @@ -86,42 +98,55 @@ static double ignoreMissing(double w) { return w; } -static void inline printEdgeError(BasicBlock *V1, BasicBlock *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"); } void inline ProfileEstimatorPass::printEdgeWeight(Edge E) { - DEBUG(errs() << "-- Weight of Edge " << E << ":" - << format("%g", getEdgeWeight(E)) << "\n"); + 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 (BBisVisited.find(BB) != BBisVisited.end()) return; + if (BBToVisit.find(BB) == BBToVisit.end()) return; - // Check if incoming edges are calculated already, if BB is header allow - // backedges that are uncalculated for now. + // 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)) { - printEdgeError(*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, continueing"); continue; } - if (BBisVisited.find(*bbi) == BBisVisited.end()) { - printEdgeError(*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; } } @@ -136,41 +161,108 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { BBLoop->getExitEdges(ExitEdges); } - // If block is an loop header, first subtract all weights 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. + 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; + } } } - // Distribute remaining weight onto the exit edges. + // 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 (SmallVector::iterator ei = Edges.begin(), ee = Edges.end(); ei != ee; ++ei) { - EdgeInformation[BB->getParent()][*ei] += incoming/Edges.size(); + 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); } - // 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; - // Otherwise consider weight of outgoing edges and store them for - // distribution of remaining weight. In case the block has no successors - // create a (BB,0) edge. 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; @@ -184,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(); + 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 this Block visited and recurse into successors. - 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); } } @@ -207,41 +318,105 @@ 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(); - DEBUG(errs() << "Working on function " << F.getNameStr() << "\n"); + // 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.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; - + BlockInformation[&F][entry] = pow(2.0, 32.0); Edge edge = getEdge(0,entry); - EdgeInformation[&F][edge] = 1; printEdgeWeight(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(); + + // 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; + } - // In case something went wrong, clear all results, not profiling info is - // available. - if (BBisVisited.size() != F.size()) { - DEBUG(errs() << "-- could not estimate profile, using default profile\n"); - FunctionInformation.erase(&F); + // 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 "<