diff options
| -rw-r--r-- | include/llvm/Analysis/ProfileInfo.h | 180 | ||||
| -rw-r--r-- | lib/Analysis/ProfileInfo.cpp | 965 |
2 files changed, 1071 insertions, 74 deletions
diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h index 2a80f3d4c4..80ba6d8533 100644 --- a/include/llvm/Analysis/ProfileInfo.h +++ b/include/llvm/Analysis/ProfileInfo.h @@ -21,116 +21,228 @@ #ifndef LLVM_ANALYSIS_PROFILEINFO_H #define LLVM_ANALYSIS_PROFILEINFO_H -#include "llvm/BasicBlock.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" #include <cassert> #include <string> #include <map> +#include <set> namespace llvm { - class Function; class Pass; class raw_ostream; + class BasicBlock; + class Function; + class MachineBasicBlock; + class MachineFunction; + + // Helper for dumping edges to errs(). + raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E); + raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E); + + raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB); + raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB); + + raw_ostream& operator<<(raw_ostream &O, const Function *F); + raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF); + /// ProfileInfo Class - This class holds and maintains profiling /// information for some unit of code. - class ProfileInfo { + template<class FType, class BType> + class ProfileInfoT { public: // Types for handling profiling information. - typedef std::pair<const BasicBlock*, const BasicBlock*> Edge; + typedef std::pair<const BType*, const BType*> Edge; typedef std::pair<Edge, double> EdgeWeight; typedef std::map<Edge, double> EdgeWeights; - typedef std::map<const BasicBlock*, double> BlockCounts; + typedef std::map<const BType*, double> BlockCounts; + typedef std::map<const BType*, const BType*> Path; protected: // EdgeInformation - Count the number of times a transition between two // blocks is executed. As a special case, we also hold an edge from the // null BasicBlock to the entry block to indicate how many times the // function was entered. - std::map<const Function*, EdgeWeights> EdgeInformation; + std::map<const FType*, EdgeWeights> EdgeInformation; // BlockInformation - Count the number of times a block is executed. - std::map<const Function*, BlockCounts> BlockInformation; + std::map<const FType*, BlockCounts> BlockInformation; // FunctionInformation - Count the number of times a function is executed. - std::map<const Function*, double> FunctionInformation; + std::map<const FType*, double> FunctionInformation; + + ProfileInfoT<MachineFunction, MachineBasicBlock> *MachineProfile; public: static char ID; // Class identification, replacement for typeinfo - virtual ~ProfileInfo(); // We want to be subclassed + ProfileInfoT(); + ~ProfileInfoT(); // We want to be subclassed // MissingValue - The value that is returned for execution counts in case // no value is available. static const double MissingValue; // getFunction() - Returns the Function for an Edge, checking for validity. - static const Function* getFunction(Edge e) { + static const FType* getFunction(Edge e) { if (e.first) { return e.first->getParent(); } else if (e.second) { return e.second->getParent(); } assert(0 && "Invalid ProfileInfo::Edge"); - return (const Function*)0; + return (const FType*)0; } // getEdge() - Creates an Edge from two BasicBlocks. - static Edge getEdge(const BasicBlock *Src, const BasicBlock *Dest) { + static Edge getEdge(const BType *Src, const BType *Dest) { return std::make_pair(Src, Dest); } //===------------------------------------------------------------------===// /// Profile Information Queries /// - double getExecutionCount(const Function *F); + double getExecutionCount(const FType *F); + + double getExecutionCount(const BType *BB); - double getExecutionCount(const BasicBlock *BB); + void setExecutionCount(const BType *BB, double w); + + void addExecutionCount(const BType *BB, double w); double getEdgeWeight(Edge e) const { - std::map<const Function*, EdgeWeights>::const_iterator J = + typename std::map<const FType*, EdgeWeights>::const_iterator J = EdgeInformation.find(getFunction(e)); if (J == EdgeInformation.end()) return MissingValue; - EdgeWeights::const_iterator I = J->second.find(e); + typename EdgeWeights::const_iterator I = J->second.find(e); if (I == J->second.end()) return MissingValue; return I->second; } - EdgeWeights &getEdgeWeights (const Function *F) { + void setEdgeWeight(Edge e, double w) { + DEBUG_WITH_TYPE("profile-info", + errs() << "Creating Edge " << e + << " (weight: " << format("%.20g",w) << ")\n"); + EdgeInformation[getFunction(e)][e] = w; + } + + void addEdgeWeight(Edge e, double w); + + EdgeWeights &getEdgeWeights (const FType *F) { return EdgeInformation[F]; } //===------------------------------------------------------------------===// /// Analysis Update Methods /// - void removeBlock(const BasicBlock *BB) { - std::map<const Function*, BlockCounts>::iterator J = - BlockInformation.find(BB->getParent()); - if (J == BlockInformation.end()) return; - - J->second.erase(BB); + void removeBlock(const BType *BB); + + void removeEdge(Edge e); + + void replaceEdge(const Edge &, const Edge &); + + enum GetPathMode { + GetPathToExit = 1, + GetPathToValue = 2, + GetPathToDest = 4, + GetPathWithNewEdges = 8 + }; + + const BType *GetPath(const BType *Src, const BType *Dest, + Path &P, unsigned Mode); + + void divertFlow(const Edge &, const Edge &); + + void splitEdge(const BType *FirstBB, const BType *SecondBB, + const BType *NewBB, bool MergeIdenticalEdges = false); + + void splitBlock(const BType *Old, const BType* New); + + void splitBlock(const BType *BB, const BType* NewBB, + BType *const *Preds, unsigned NumPreds); + + void replaceAllUses(const BType *RmBB, const BType *DestBB); + + void transfer(const FType *Old, const FType *New); + + void repair(const FType *F); + + void dump(FType *F = 0, bool real = true) { + errs() << "**** This is ProfileInfo " << this << " speaking:\n"; + if (!real) { + typename std::set<const FType*> Functions; + + errs() << "Functions: \n"; + if (F) { + errs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n"; + Functions.insert(F); + } else { + for (typename std::map<const FType*, double>::iterator fi = FunctionInformation.begin(), + fe = FunctionInformation.end(); fi != fe; ++fi) { + errs() << fi->first << "@" << format("%p",fi->first) << ": " << format("%.20g",fi->second) << "\n"; + Functions.insert(fi->first); + } + } + + for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end(); + FI != FE; ++FI) { + const FType *F = *FI; + typename std::map<const FType*, BlockCounts>::iterator bwi = BlockInformation.find(F); + errs() << "BasicBlocks for Function " << F << ":\n"; + for (typename BlockCounts::const_iterator bi = bwi->second.begin(), be = bwi->second.end(); bi != be; ++bi) { + errs() << bi->first << "@" << format("%p", bi->first) << ": " << format("%.20g",bi->second) << "\n"; + } + } + + for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end(); + FI != FE; ++FI) { + typename std::map<const FType*, EdgeWeights>::iterator ei = EdgeInformation.find(*FI); + errs() << "Edges for Function " << ei->first << ":\n"; + for (typename EdgeWeights::iterator ewi = ei->second.begin(), ewe = ei->second.end(); + ewi != ewe; ++ewi) { + errs() << ewi->first << ": " << format("%.20g",ewi->second) << "\n"; + } + } + } else { + assert(F && "No function given, this is not supported!"); + errs() << "Functions: \n"; + errs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n"; + + errs() << "BasicBlocks for Function " << F << ":\n"; + for (typename FType::const_iterator BI = F->begin(), BE = F->end(); + BI != BE; ++BI) { + const BType *BB = &(*BI); + errs() << BB << "@" << format("%p", BB) << ": " << format("%.20g",getExecutionCount(BB)) << "\n"; + } + } + errs() << "**** ProfileInfo " << this << ", over and out.\n"; } - void removeEdge(Edge e) { - std::map<const Function*, EdgeWeights>::iterator J = - EdgeInformation.find(getFunction(e)); - if (J == EdgeInformation.end()) return; + bool CalculateMissingEdge(const BType *BB, Edge &removed, bool assumeEmptyExit = false); - J->second.erase(e); - } + bool EstimateMissingEdges(const BType *BB); - void splitEdge(const BasicBlock *FirstBB, const BasicBlock *SecondBB, - const BasicBlock *NewBB, bool MergeIdenticalEdges = false); + ProfileInfoT<MachineFunction, MachineBasicBlock> *MI() { + if (MachineProfile == 0) + MachineProfile = new ProfileInfoT<MachineFunction, MachineBasicBlock>(); + return MachineProfile; + } - void replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB); + bool hasMI() const { + return (MachineProfile != 0); + } }; + typedef ProfileInfoT<Function, BasicBlock> ProfileInfo; + typedef ProfileInfoT<MachineFunction, MachineBasicBlock> MachineProfileInfo; + /// createProfileLoaderPass - This function returns a Pass that loads the /// profiling information for the module from the specified filename, making /// it available to the optimizers. Pass *createProfileLoaderPass(const std::string &Filename); - raw_ostream& operator<<(raw_ostream &O, ProfileInfo::Edge E); - } // End llvm namespace #endif diff --git a/lib/Analysis/ProfileInfo.cpp b/lib/Analysis/ProfileInfo.cpp index 7f24f5a238..5a7f6918ec 100644 --- a/lib/Analysis/ProfileInfo.cpp +++ b/lib/Analysis/ProfileInfo.cpp @@ -11,25 +11,51 @@ // "no profile" implementation. // //===----------------------------------------------------------------------===// - +#define DEBUG_TYPE "profile-info" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ProfileInfo.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" #include "llvm/Pass.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Support/Format.h" +#include "llvm/ADT/SmallSet.h" #include <set> +#include <queue> +#include <limits> using namespace llvm; // Register the ProfileInfo interface, providing a nice name to refer to. static RegisterAnalysisGroup<ProfileInfo> Z("Profile Information"); + +namespace llvm { + +template <> +ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {} +template <> +ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {} + +template <> +ProfileInfoT<Function, BasicBlock>::ProfileInfoT() { + MachineProfile = 0; +} +template <> +ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() { + if (MachineProfile) delete MachineProfile; +} + +template<> char ProfileInfo::ID = 0; -ProfileInfo::~ProfileInfo() {} +template<> +char MachineProfileInfo::ID = 0; +template<> const double ProfileInfo::MissingValue = -1; +template<> +const double MachineProfileInfo::MissingValue = -1; + +template<> double ProfileInfo::getExecutionCount(const BasicBlock *BB) { std::map<const Function*, BlockCounts>::iterator J = BlockInformation.find(BB->getParent()); @@ -39,35 +65,72 @@ double ProfileInfo::getExecutionCount(const BasicBlock *BB) { return I->second; } + double Count = MissingValue; + pred_const_iterator PI = pred_begin(BB), PE = pred_end(BB); // Are there zero predecessors of this block? if (PI == PE) { - // If this is the entry block, look for the Null -> Entry edge. - if (BB == &BB->getParent()->getEntryBlock()) - return getEdgeWeight(getEdge(0, BB)); - else - return 0; // Otherwise, this is a dead block. + Edge e = getEdge(0,BB); + Count = getEdgeWeight(e); + } else { + // Otherwise, if there are predecessors, the execution count of this block is + // the sum of the edge frequencies from the incoming edges. + std::set<const BasicBlock*> ProcessedPreds; + Count = 0; + for (; PI != PE; ++PI) + if (ProcessedPreds.insert(*PI).second) { + double w = getEdgeWeight(getEdge(*PI, BB)); + if (w == MissingValue) { + Count = MissingValue; + break; + } + Count += w; + } } - // Otherwise, if there are predecessors, the execution count of this block is - // the sum of the edge frequencies from the incoming edges. - std::set<const BasicBlock*> ProcessedPreds; - double Count = 0; - for (; PI != PE; ++PI) - if (ProcessedPreds.insert(*PI).second) { - double w = getEdgeWeight(getEdge(*PI, BB)); - if (w == MissingValue) { - Count = MissingValue; - break; - } - Count += w; + // If the predecessors did not suffice to get block weight, try successors. + if (Count == MissingValue) { + + succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB); + + // Are there zero successors of this block? + if (SI == SE) { + Edge e = getEdge(BB,0); + Count = getEdgeWeight(e); + } else { + std::set<const BasicBlock*> ProcessedSuccs; + Count = 0; + for (; SI != SE; ++SI) + if (ProcessedSuccs.insert(*SI).second) { + double w = getEdgeWeight(getEdge(BB, *SI)); + if (w == MissingValue) { + Count = MissingValue; + break; + } + Count += w; + } } + } if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count; return Count; } +template<> +double MachineProfileInfo::getExecutionCount(const MachineBasicBlock *MBB) { + std::map<const MachineFunction*, BlockCounts>::iterator J = + BlockInformation.find(MBB->getParent()); + if (J != BlockInformation.end()) { + BlockCounts::iterator I = J->second.find(MBB); + if (I != J->second.end()) + return I->second; + } + + return MissingValue; +} + +template<> double ProfileInfo::getExecutionCount(const Function *F) { std::map<const Function*, double>::iterator J = FunctionInformation.find(F); @@ -83,35 +146,204 @@ double ProfileInfo::getExecutionCount(const Function *F) { return Count; } +template<> +double MachineProfileInfo::getExecutionCount(const MachineFunction *MF) { + std::map<const MachineFunction*, double>::iterator J = + FunctionInformation.find(MF); + if (J != FunctionInformation.end()) + return J->second; + + double Count = getExecutionCount(&MF->front()); + if (Count != MissingValue) FunctionInformation[MF] = Count; + return Count; +} + +template<> +void ProfileInfo::setExecutionCount(const BasicBlock *BB, double w) { + DEBUG(errs() << "Creating Block " << BB->getName() + << " (weight: " << format("%.20g",w) << ")\n"); + BlockInformation[BB->getParent()][BB] = w; +} + +template<> +void MachineProfileInfo::setExecutionCount(const MachineBasicBlock *MBB, double w) { + DEBUG(errs() << "Creating Block " << MBB->getBasicBlock()->getName() + << " (weight: " << format("%.20g",w) << ")\n"); + BlockInformation[MBB->getParent()][MBB] = w; +} + +template<> +void ProfileInfo::addEdgeWeight(Edge e, double w) { + double oldw = getEdgeWeight(e); + assert (oldw != MissingValue && "Adding weight to Edge with no previous weight"); + DEBUG(errs() << "Adding to Edge " << e + << " (new weight: " << format("%.20g",oldw + w) << ")\n"); + EdgeInformation[getFunction(e)][e] = oldw + w; +} + +template<> +void ProfileInfo::addExecutionCount(const BasicBlock *BB, double w) { + double oldw = getExecutionCount(BB); + assert (oldw != MissingValue && "Adding weight to Block with no previous weight"); + DEBUG(errs() << "Adding to Block " << BB->getName() + << " (new weight: " << format("%.20g",oldw + w) << ")\n"); + BlockInformation[BB->getParent()][BB] = oldw + w; +} + +template<> +void ProfileInfo::removeBlock(const BasicBlock *BB) { + std::map<const Function*, BlockCounts>::iterator J = + BlockInformation.find(BB->getParent()); + if (J == BlockInformation.end()) return; + + DEBUG(errs() << "Deleting " << BB->getName() << "\n"); + J->second.erase(BB); +} + +template<> +void ProfileInfo::removeEdge(Edge e) { + std::map<const Function*, EdgeWeights>::iterator J = + EdgeInformation.find(getFunction(e)); + if (J == EdgeInformation.end()) return; + + DEBUG(errs() << "Deleting" << e << "\n"); + J->second.erase(e); +} + +template<> +void ProfileInfo::replaceEdge(const Edge &oldedge, const Edge &newedge) { + double w; + if ((w = getEdgeWeight(newedge)) == MissingValue) { + w = getEdgeWeight(oldedge); + DEBUG(errs() << "Replacing " << oldedge << " with " << newedge << "\n"); + } else { + w += getEdgeWeight(oldedge); + DEBUG(errs() << "Adding " << oldedge << " to " << newedge << "\n"); + } + setEdgeWeight(newedge,w); + removeEdge(oldedge); +} + +template<> +const BasicBlock *ProfileInfo::GetPath(const BasicBlock *Src, const BasicBlock *Dest, + Path &P, unsigned Mode) { + const BasicBlock *BB = 0; + bool hasFoundPath = false; + + std::queue<const BasicBlock *> BFS; + BFS.push(Src); + + while(BFS.size() && !hasFoundPath) { + BB = BFS.front(); + BFS.pop(); + + succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB); + if (Succ == End) { + P[0] = BB; + if (Mode & GetPathToExit) { + hasFoundPath = true; + BB = 0; + } + } + for(;Succ != End; ++Succ) { + if (P.find(*Succ) != P.end()) continue; + Edge e = getEdge(BB,*Succ); + if ((Mode & GetPathWithNewEdges) && (getEdgeWeight(e) != MissingValue)) continue; + P[*Succ] = BB; + BFS.push(*Succ); + if ((Mode & GetPathToDest) && *Succ == Dest) { + hasFoundPath = true; + BB = *Succ; + break; + } + if ((Mode & GetPathToValue) && (getExecutionCount(*Succ) != MissingValue)) { + hasFoundPath = true; + BB = *Succ; + break; + } + } + } + + return BB; +} + +template<> +void ProfileInfo::divertFlow(const Edge &oldedge, const Edge &newedge) { + DEBUG(errs() << "Diverting " << oldedge << " via " << newedge ); + + // First check if the old edge was taken, if not, just delete it... + if (getEdgeWeight(oldedge) == 0) { + removeEdge(oldedge); + return; + } + + Path P; + P[newedge.first] = 0; + P[newedge.second] = newedge.first; + const BasicBlock *BB = GetPath(newedge.second,oldedge.second,P,GetPathToExit | GetPathToDest); + + double w = getEdgeWeight (oldedge); + DEBUG(errs() << ", Weight: " << format("%.20g",w) << "\n"); + do { + const BasicBlock *Parent = P.find(BB)->second; + Edge e = getEdge(Parent,BB); + double oldw = getEdgeWeight(e); + double oldc = getExecutionCount(e.first); + setEdgeWeight(e, w+oldw); + if (Parent != oldedge.first) { + setExecutionCount(e.first, w+oldc); + } + BB = Parent; + } while (BB != newedge.first); + removeEdge(oldedge); +} + /// Replaces all occurences of RmBB in the ProfilingInfo with DestBB. /// This checks all edges of the function the blocks reside in and replaces the /// occurences of RmBB with DestBB. +template<> void ProfileInfo::replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB) { - DEBUG(errs() << "Replacing " << RmBB->getNameStr() - << " with " << DestBB->getNameStr() << "\n"); + DEBUG(errs() << "Replacing " << RmBB->getName() + << " with " << DestBB->getName() << "\n"); const Function *F = DestBB->getParent(); std::map<const Function*, EdgeWeights>::iterator J = EdgeInformation.find(F); if (J == EdgeInformation.end()) return; - for (EdgeWeights::iterator I = J->second.begin(), E = J->second.end(); - I != E; ++I) { - Edge e = I->first; - Edge newedge; bool foundedge = false; + Edge e, newedge; + bool erasededge = false; + EdgeWeights::iterator I = J->second.begin(), E = J->second.end(); + while(I != E) { + e = (I++)->first; + bool foundedge = false; bool eraseedge = false; if (e.first == RmBB) { - newedge = getEdge(DestBB, e.second); - foundedge = true; + if (e.second == DestBB) { + eraseedge = true; + } else { + newedge = getEdge(DestBB, e.second); + foundedge = true; + } } if (e.second == RmBB) { - newedge = getEdge(e.first, DestBB); - foundedge = true; + if (e.first == DestBB) { + eraseedge = true; + } else { + newedge = getEdge(e.first, DestBB); + foundedge = true; + } } if (foundedge) { - double w = getEdgeWeight(e); - EdgeInformation[F][newedge] = w; - DEBUG(errs() << "Replacing " << e << " with " << newedge << "\n"); - J->second.erase(e); + replaceEdge(e, newedge); + } + if (eraseedge) { + if (erasededge) { + Edge newedge = getEdge(DestBB, DestBB); + replaceEdge(e, newedge); + } else { + removeEdge(e); + erasededge = true; + } } } } @@ -119,6 +351,7 @@ void ProfileInfo::replaceAllUses(const BasicBlock *RmBB, /// Splits an edge in the ProfileInfo and redirects flow over NewBB. /// Since its possible that there is more than one edge in the CFG from FristBB /// to SecondBB its necessary to redirect the flow proporionally. +template<> void ProfileInfo::splitEdge(const BasicBlock *FirstBB, const BasicBlock *SecondBB, const BasicBlock *NewBB, @@ -153,7 +386,7 @@ void ProfileInfo::splitEdge(const BasicBlock *FirstBB, // We know now how many edges there are from FirstBB to SecondBB, reroute a // proportional part of the edge weight over NewBB. - double neww = w / succ_count; + double neww = floor(w / succ_count); ECs[n1] += neww; ECs[n2] += neww; BlockInformation[F][NewBB] += neww; @@ -164,14 +397,666 @@ void ProfileInfo::splitEdge(const BasicBlock *FirstBB, } } -raw_ostream& llvm::operator<<(raw_ostream &O, ProfileInfo::Edge E) { +template<> +void ProfileInfo::splitBlock(const BasicBlock *Old, const BasicBlock* New) { + const Function *F = Old->getParent(); + std::map<const Function*, EdgeWeights>::iterator J = + EdgeInformation.find(F); + if (J == EdgeInformation.end()) return; + + DEBUG(errs() << "Splitting " << Old->getName() << " to " << New->getName() << "\n"); + + std::set<Edge> Edges; + for (EdgeWeights::iterator ewi = J->second.begin(), ewe = J->second.end(); + ewi != ewe; ++ewi) { + Edge old = ewi->first; + if (old.first == Old) { + Edges.insert(old); + } + } + for (std::set<Edge>::iterator EI = Edges.begin(), EE = Edges.end(); + EI != EE; ++EI) { + Edge newedge = getEdge(New, EI->second); + replaceEdge(*EI, newedge); + } + + double w = getExecutionCount(Old); + setEdgeWeight(getEdge(Old, New), w); + setExecutionCount(New, w); +} + +template<> +void ProfileInfo::splitBlock(const BasicBlock *BB, const BasicBlock* NewBB, + BasicBlock *const *Preds, unsigned NumPreds) { + const Function *F = BB->getParent(); + std::map<const Function*, EdgeWeights>::iterator J = + EdgeInformation.find(F); + if (J == EdgeInformation.end()) return; + + DEBUG(errs() << "Splitting " << NumPreds << " Edges from " << BB->getName() + << " to " << NewBB->getName() << "\n"); + + // Collect weight that was redirected over NewBB. + double newweight = 0; + + std::set<const BasicBlock *> ProcessedPreds; + // For all requestes Predecessors. + for (unsigned pred = 0; pred < NumPreds; ++pred) { + const BasicBlock * Pred = Preds[pred]; + if (ProcessedPreds.insert(Pred).second) { + // Create edges and read old weight. + Edge oldedge = getEdge(Pred, BB); + Edge newedge = getEdge(Pred, NewBB); + + // Remember how much weight was redirected. + newweight += getEdgeWeight(oldedge); + + replaceEdge(oldedge,newedge); + } + } + + Edge newedge = getEdge(NewBB,BB); + setEdgeWeight(newedge, newweight); + setExecutionCount(NewBB, newweight); +} + +template<> +void ProfileInfo::transfer(const Function *Old, const Function *New) { + DEBUG(errs() << "Replacing Function " << Old->getName() << " with " + << New->getName() << "\n"); + std::map<const Function*, EdgeWeights>::iterator J = + EdgeInformation.find(Old); + if(J != EdgeInformation.end()) { + EdgeInformation[New] = J->second; + } + EdgeInformation.erase(Old); + BlockInformation.erase(Old); + FunctionInformation.erase(Old); +} + +static double readEdgeOrRemember(ProfileInfo::Edge edge, double w, ProfileInfo::Edge &tocalc, + unsigned &uncalc) { + if (w == ProfileInfo::MissingValue) { + tocalc = edge; + uncalc++; + return 0; + } else { + return w; + } +} + +template<> +bool ProfileInfo::CalculateMissingEdge(const BasicBlock *BB, Edge &removed, bool assumeEmptySelf) { + Edge edgetocalc; + unsigned uncalculated = 0; + + // collect weights of all incoming and outgoing edges, rememer edges that + // have no value + double incount = 0; + SmallSet<const BasicBlock*,8> pred_visited; + pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB); + if (bbi==bbe) { + Edge e = getEdge(0,BB); + incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated); + } + for (;bbi != bbe; ++bbi) { + if (pred_visited.insert(*bbi)) { + Edge e = getEdge(*bbi,BB); + incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated); + } + } + + double outcount = 0; + SmallSet<const BasicBlock*,8> succ_visited; + succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB); + if (sbbi==sbbe) { + Edge e = getEdge(BB,0); + if (getEdgeWeight(e) == MissingValue) { + double w = getExecutionCount(BB); + if (w != MissingValue) { + setEdgeWeight(e,w); + removed = e; + } + } + outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated); + } + for (;sbbi != sbbe; ++sbbi) { + if (succ_visited.insert(*sbbi)) { + Edge e = getEdge(BB,*sbbi); + outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated); + } + } + + // if exactly one edge weight was missing, calculate it and remove it from + // spanning tree + if (uncalculated == 0 ) { + return true; + } else + if (uncalculated == 1) { + if (incount < outcount) { + EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount; + } else { + EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount; + } + DEBUG(errs() << "--Calc Edge Counter for " << edgetocalc << ": " + << format("%.20g", getEdgeWeight(edgetocalc)) << "\n"); + removed = edgetocalc; + return true; + } else + if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) { + setEdgeWeight(edgetocalc, incount * 10); + removed = edgetocalc; + return true; + } else { + return false; + } +} + +static void readEdge(ProfileInfo *PI, ProfileInfo::Edge e, double &calcw, std::set<ProfileInfo::Edge> &misscount) { + double w = PI->getEdgeWeight(e); + if (w != ProfileInfo::MissingValue) { + calcw += w; + } else { + misscount.insert(e); + } +} + +template<> +bool ProfileInfo::EstimateMissingEdges(const BasicBlock *BB) { + bool hasNoSuccessors = false; + + double inWeight = 0; + std::set<Edge> inMissing; + std::set<const BasicBlock*> ProcessedPreds; + pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB); + if (bbi == bbe) { + readEdge(this,getEdge(0,BB),inWeight,inMissing); + } + for( ; bbi != bbe; ++bbi ) { + if (ProcessedPreds.insert(*bbi).second) { + readEdge(this,getEdge(*bbi,BB),inWeight,inMissing); + } + } + + double outWeight = 0; + std::set<Edge> outMissing; + std::set<const BasicBlock*> ProcessedSuccs; + succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB); + if (sbbi == sbbe) { + readEdge(this,getEdge(BB,0),outWeight,outMissing); + hasNoSuccessors = true; + } + for ( ; sbbi != sbbe; ++sbbi ) { + if (ProcessedSuccs.insert(*sbbi).second) { + readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing); + } + } + + double share; + std::set<Edge>::iterator ei,ee; + if (inMissing.size() == 0 && outMissing.size() > 0) { + ei = outMissing.begin(); + ee = outMissing.end(); + share = inWeight/outMissing.size(); + setExecutionCount(BB,inWeight); + } else + if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) { + ei = inMissing.begin(); + ee = inMissing.end(); + share = 0; + setExecutionCount(BB,0); + } else + if (inMissing.size() == 0 && outMissing.size() == 0) { + setExecutionCount(BB,outWeight); + return true; + } else { + return false; + } + for ( ; ei != ee; ++ei ) { + setEdgeWeight(*ei,share); + } + return true; +} + +template<> +void ProfileInfo::repair(const Function *F) { +// if (getExecutionCount(&(F->getEntryBlock())) == 0) { +// for (Function::const_iterator FI = F->begin(), FE = F->end(); +// FI != FE; ++FI) { +// const BasicBlock* BB = &(*FI); +// { +// pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB); +// if (NBB == End) { +// setEdgeWeight(getEdge(0,BB),0); +// } +// for(;NBB != End; ++NBB) { +// setEdgeWeight(getEdge(*NBB,BB),0); +// } +// } +// { +// succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); +// if (NBB == End) { +// setEdgeWeight(getEdge(0,BB),0); +// } +// for(;NBB != End; ++NBB) { +// setEdgeWeight(getEdge(*NBB,BB),0); +// } +// } +// } +// return; +// } + // The set of BasicBlocks that are still unvisited. + std::set<const BasicBlock*> Unvisited; + + // The set of return edges (Edges with no successors). + std::set<Edge> ReturnEdges; + double ReturnWeight = 0; + + // First iterate over the whole function and collect: + // 1) The blocks in this function in the Unvisited set. + // 2) The return edges in the ReturnEdges set. + // 3) The flow that is leaving the function already via return edges. + + // Data structure for searching the function. + std::queue<const BasicBlock *> BFS; + const BasicBlock *BB = &(F->getEntryBlock()); + BFS.push(BB); + Unvisited.insert(BB); + + while (BFS.size()) { + BB = BFS.front(); BFS.pop(); + succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); + if (NBB == End) { + Edge e = getEdge(BB,0); + double w = getEdgeWeight(e); + if (w == MissingValue) { + // If the return edge has no value, try to read value from block. + double bw = getExecutionCount(BB); + if (bw != MissingValue) { + setEdgeWeight(e,bw); + ReturnWeight += bw; + } else { + // If both return edge and block provide no value, collect edge. + ReturnEdges.insert(e); + } + } else { + // If the return edge has a proper value, collect it. + ReturnWeight += w; + } + } + for (;NBB != End; ++NBB) { + if (Unvisited.insert(*NBB).second) { + BFS.push(*NBB); + } + } + } + + while (Unvisited.size() > 0) { + unsigned oldUnvisitedCount = Unvisited.size(); + bool FoundPath = false; + + // If there is only one edge left, calculate it. + if (ReturnEdges.size() == 1) { + ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight; + + Edge e = *ReturnEdges.begin(); + setEdgeWeight(e,ReturnWeight); + setExecutionCount(e.first,ReturnWeight); + + Unvisited.erase(e.first); + ReturnEdges.erase(e); + continue; + } + + // Calculate all blocks where only one edge is missing, this may also + // resolve furhter return edges. + std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE) { + const BasicBlock *BB = *FI; ++FI; + Edge e; + if(CalculateMissingEdge(BB,e,true)) { + if (BlockInformation[F].find(BB) == BlockInformation[F].end()) { + setExecutionCount(BB,getExecutionCount(BB)); + } + Unvisited.erase(BB); + if (e.first != 0 && e.second == 0) { + ReturnEdges.erase(e); + ReturnWeight += getEdgeWeight(e); + } + } + } + if (oldUnvisitedCount > Unvisited.size()) continue; + + // Estimate edge weights by dividing the flow proportionally. + FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE) { + const BasicBlock *BB = *FI; ++FI; + const BasicBlock *Dest = 0; + bool AllEdgesHaveSameReturn = true; + // Check each Successor, these must all end up in the same or an empty + // return block otherwise its dangerous to do an estimation on them. + for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB); + Succ != End; ++Succ) { + Path P; + GetPath(*Succ, 0, P, GetPathToExit); + if (Dest && Dest != P[0]) { + AllEdgesHaveSameReturn = false; + } + Dest = P[0]; + } + if (AllEdgesHaveSameReturn) { + if(EstimateMissingEdges(BB)) { + Unvisited.erase(BB); + break; + } + } + } + if (oldUnvisitedCount > Unvisited.size()) continue; + + // Check if there is a path to an block that has a known value and redirect + // flow accordingly. + FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE && !FoundPath) { + // Fetch path. + const BasicBlock *BB = *FI; ++FI; + Path P; + const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue); + + // Calculate incoming flow. + double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0; + std::set<const BasicBlock *> Processed; + for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB); + NBB != End; ++NBB) { + if (Processed.insert(*NBB).second) { + Edge e = getEdge(*NBB, BB); + double ew = getEdgeWeight(e); + if (ew != MissingValue) { + iw += ew; + invalid++; + } else { + // If the path contains the successor, this means its a backedge, + // do not count as missing. + if (P.find(*NBB) == P.end()) + inmissing++; + } + incount++; + } + } + if (inmissing == incount) continue; + if (invalid == 0) continue; + + // Subtract (already) outgoing flow. + Processed.clear(); + for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); + NBB != End; ++NBB) { + if (Processed.insert(*NBB).second) { + Edge e = getEdge(BB, *NBB); + double ew = getEdgeWeight(e); + if (ew != MissingValue) { + iw -= ew; + } + } + } + if (iw < 0) continue; + + // Check the recieving end of the path if it can handle the flow. + double ow = getExecutionCount(Dest); + Processed.clear(); + for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); + NBB != End; ++NBB) { + if (Processed.insert(*NBB).second) { + Edge e = getEdge(BB, *NBB); + double ew = getEdgeWeight(e); + if (ew != MissingValue) { + ow -= ew; + } + } + } + if (ow < 0) continue; + + // Determine how much flow shall be used. + double ew = getEdgeWeight(getEdge(P[Dest],Dest)); + if (ew != MissingValue) { + ew = ew<ow?ew:ow; + ew = ew<iw?ew:iw; + } else { + if (inmissing == 0) + ew = iw; + } + + // Create flow. + if (ew != MissingValue) { + do { + Edge e = getEdge(P[Dest],Dest); + if (getEdgeWeight(e) == MissingValue) { + setEdgeWeight(e,ew); + FoundPath = true; + } + Dest = P[Dest]; + } while (Dest != BB); + } + } + if (FoundPath) continue; + + // Calculate a block with self loop. + FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE && !FoundPath) { + const BasicBlock *BB = *FI; ++FI; + bool SelfEdgeFound = false; + for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); + NBB != End; ++NBB) { + if (*NBB == BB) { + SelfEdgeFound = true; + break; + } + } + if (SelfEdgeFound) { + Edge e = getEdge(BB,BB); + if (getEdgeWeight(e) == MissingValue) { + double iw = 0; + std::set<const BasicBlock *> Processed; + for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB); + NBB != End; ++NBB) { + if (Processed.insert(*NBB).second) { + Edge e = getEdge(*NBB, BB); + double ew = getEdgeWeight(e); + if (ew != MissingValue) { + iw += ew; + } + } + } + setEdgeWeight(e,iw * 10); + FoundPath = true; + } + } + } + if (FoundPath) continue; + + // Determine backedges, set them to zero. + FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE && !FoundPath) { + const BasicBlock *BB = *FI; ++FI; + const BasicBlock *Dest; + Path P; + bool BackEdgeFound = false; + for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB); + NBB != End; ++NBB) { + Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges); + if (Dest == *NBB) { + BackEdgeFound = true; + break; + } + } + if (BackEdgeFound) { + Edge e = getEdge(Dest,BB); + double w = getEdgeWeight(e); + if (w == MissingValue) { + setEdgeWeight(e,0); + FoundPath = true; + } + do { + Edge e = getEdge(P[Dest], Dest); + double w = getEdgeWeight(e); + if (w == MissingValue) { + setEdgeWeight(e,0); + FoundPath = true; + } + Dest = P[Dest]; + } while (Dest != BB); + } + } + if (FoundPath) continue; + + // Channel flow to return block. + FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE && !FoundPath) { + const BasicBlock *BB = *FI; ++FI; + + Path P; + const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges); + Dest = P[0]; + if (!Dest) continue; + + if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) { + // Calculate incoming flow. + double iw = 0; + std::set<const BasicBlock *> Processed; + for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB); + NBB != End; ++NBB) { + if (Processed.insert(*NBB).second) { + Edge e = getEdge(*NBB, BB); + double ew = getEdgeWeight(e); + if (ew != MissingValue) { + iw += ew; + } + } + } + do { + Edge e = getEdge(P[Dest], Dest); + double w = getEdgeWeight(e); + if (w == MissingValue) { + setEdgeWeight(e,iw); + FoundPath = true; + } else { + assert(0 && "Edge should not have value already!"); + } + Dest = P[Dest]; + } while (Dest != BB); + } + } + if (FoundPath) continue; + + // Speculatively set edges to zero. + FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE && !FoundPath) { + const BasicBlock *BB = *FI; ++FI; + + for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB); + NBB != End; ++NBB) { + Edge e = getEdge(*NBB,BB); + double w = getEdgeWeight(e); + if (w == MissingValue) { + setEdgeWeight(e,0); + FoundPath = true; + break; + } + } + } + if (FoundPath) continue; + + errs() << "{"; + FI = Unvisited.begin(), FE = Unvisited.end(); + while(FI != FE) { + const BasicBlock *BB = *FI; ++FI; + errs() << BB->getName(); + if (FI != FE) + errs() << ","; + } + errs() << "}"; + + errs() << "ASSERT: could not repair function"; + assert(0 && "could not repair function"); + } + + EdgeWeights J = EdgeInformation[F]; + for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) { + Edge e = EI->first; + + bool SuccFound = false; + if (e.first != 0) { + succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first); + if (NBB == End) { + if (0 == e.second) { + SuccFound = true; + } + } + for (;NBB != End; ++NBB) { + if (*NBB == e.second) { + SuccFound = true; + break; + } + } + if (!SuccFound) { + removeEdge(e); + } + } + } +} + +raw_ostream& operator<<(raw_ostream &O, const Function *F) { + return O << F->getName(); +} + +raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) { + return O << MF->getFunction()->getName() << "(MF)"; +} + +raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) { + return O << BB->getName(); +} + +raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) { + return O << MBB->getBasicBlock()->getName() << "(MB)"; +} + +raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) { O << "("; - O << (E.first ? E.first->getNameStr() : "0"); + + if (E.first) + O << E.first; + else + O << "0"; + + O << ","; + + if (E.second) + O << E.second; + else + O << "0"; + + return O << ")"; +} + +raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) { + O << "("; + + if (E.first) + O << E.first; + else + O << "0"; + O << ","; - O << (E.second ? E.second->getNameStr() : "0"); + + if (E.second) + O << E.second; + else + O << "0"; + return O << ")"; } +} // namespace llvm + //===----------------------------------------------------------------------===// // NoProfile ProfileInfo implementation // |