X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FProfileEstimatorPass.cpp;h=63468f842612db784e8b037c38f2e32383940147;hb=e32981048244ecfa67d0bdc211af1bac2020a555;hp=e767891eab3c81b13fe4006a6770898f59d4b607;hpb=6726b6d75a8b679068a58cb954ba97cf9d1690ba;p=oota-llvm.git diff --git a/lib/Analysis/ProfileEstimatorPass.cpp b/lib/Analysis/ProfileEstimatorPass.cpp index e767891eab3..63468f84261 100644 --- a/lib/Analysis/ProfileEstimatorPass.cpp +++ b/lib/Analysis/ProfileEstimatorPass.cpp @@ -35,10 +35,12 @@ namespace { LoopInfo *LI; 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; } @@ -54,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); @@ -61,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,12 +99,12 @@ static double ignoreMissing(double w) { } static void inline printEdgeError(ProfileInfo::Edge e, const char *M) { - DEBUG(errs() << "-- Edge " << e << " is not calculated, " << M << "\n"); + 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 @@ -127,7 +140,7 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { // 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"); + printEdgeError(edge, "but is backedge, continuing"); continue; } // If the edges value is missing (and this is no loop header, and this is @@ -174,6 +187,12 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { 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; } @@ -191,11 +210,43 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { 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(); + 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); @@ -203,7 +254,7 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { 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. + // 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(); @@ -225,15 +276,32 @@ 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"); + } } } } + 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); } @@ -255,25 +323,30 @@ bool ProfileEstimatorPass::runOnFunction(Function &F) { 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); - DEBUG(errs() << "Working on function " << F.getNameStr() << "\n"); + // 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] = 1; + BlockInformation[&F][entry] = pow(2.0, 32.0); Edge edge = getEdge(0,entry); - EdgeInformation[&F][edge] = 1; + 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. + // estimated, use recurseBasicBlock() until everything is calculated. + bool cleanup = false; recurseBasicBlock(entry); - while (BBToVisit.size() > 0) { + while (BBToVisit.size() > 0 && !cleanup) { // Remember number of open blocks, this is later used to check if progress // was made. unsigned size = BBToVisit.size(); @@ -287,21 +360,65 @@ bool ProfileEstimatorPass::runOnFunction(Function &F) { if (BBToVisit.size() < size) break; } - // If there was not a single block resovled, make some assumptions. + // If there was not a single block resolved, 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); + 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 "<