//
// Note that to be useful, all profile-based optimizations should preserve
// ProfileInfo, which requires that they notify it when changes to the CFG are
-// made.
+// made. (This is not implemented yet.)
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_PROFILEINFO_H
#define LLVM_ANALYSIS_PROFILEINFO_H
+#include "llvm/BasicBlock.h"
+#include <cassert>
#include <string>
#include <map>
namespace llvm {
- class BasicBlock;
class Function;
class Pass;
- /// ProfileInfo Class - This class holds and maintains edge profiling
+ /// ProfileInfo Class - This class holds and maintains profiling
/// information for some unit of code.
class ProfileInfo {
public:
// Types for handling profiling information.
typedef std::pair<const BasicBlock*, const BasicBlock*> Edge;
+ typedef std::map<Edge, double> EdgeCounts;
+ typedef std::map<const BasicBlock*, double> BlockCounts;
protected:
// EdgeCounts - 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<Edge, unsigned> EdgeCounts;
+ std::map<const Function*, EdgeCounts> EdgeInformation;
// BlockCounts - Count the number of times a block is executed.
- std::map<const BasicBlock*, unsigned> BlockCounts;
+ std::map<const Function*, BlockCounts> BlockInformation;
// FunctionCounts - Count the number of times a function is executed.
- std::map<const Function*, unsigned> FunctionCounts;
+ std::map<const Function*, double> FunctionInformation;
public:
static char ID; // Class identification, replacement for typeinfo
virtual ~ProfileInfo(); // We want to be subclassed
+ // MissingValue - The value that is returned for execution counts in case
+ // no value is available.
+ static const int MissingValue = -1;
+
+ // getFunction() - Returns the Function for an Edge, checking for validity.
+ static const Function* getFunction(Edge e) {
+ assert(e.second && "Invalid ProfileInfo::Edge");
+ return e.second->getParent();
+ }
+
+ // getEdge() - Creates an Edge from two BasicBlocks.
+ static Edge getEdge(const BasicBlock* Src, const BasicBlock* Dest) {
+ return std::make_pair(Src,Dest);
+ }
+
//===------------------------------------------------------------------===//
/// Profile Information Queries
///
- unsigned getExecutionCount(const Function *F) const;
+ double getExecutionCount(const Function *F);
+
+ double getExecutionCount(const BasicBlock *BB);
+
+ double getEdgeWeight(Edge e) const {
+ std::map<const Function*, EdgeCounts>::const_iterator J =
+ EdgeInformation.find(getFunction(e));
+ if (J == EdgeInformation.end()) return MissingValue;
- unsigned getExecutionCount(const BasicBlock *BB) const;
+ EdgeCounts::const_iterator I = J->second.find(e);
+ if (I == J->second.end()) return MissingValue;
- unsigned getEdgeWeight(const BasicBlock *Src,
- const BasicBlock *Dest) const {
- std::map<Edge, unsigned>::const_iterator I =
- EdgeCounts.find(std::make_pair(Src, Dest));
- return I != EdgeCounts.end() ? I->second : 0;
+ return I->second;
}
//===------------------------------------------------------------------===//
ProfileInfo::~ProfileInfo() {}
-unsigned ProfileInfo::getExecutionCount(const BasicBlock *BB) const {
- if (BlockCounts.find(BB) != BlockCounts.end())
- return BlockCounts.find(BB)->second;
+double ProfileInfo::getExecutionCount(const BasicBlock *BB) {
+ std::map<const Function*, BlockCounts>::iterator J =
+ BlockInformation.find(BB->getParent());
+ if (J != BlockInformation.end()) {
+ BlockCounts::iterator I = J->second.find(BB);
+ if (I != J->second.end())
+ return I->second;
+ }
pred_const_iterator PI = pred_begin(BB), PE = pred_end(BB);
if (PI == PE) {
// If this is the entry block, look for the Null -> Entry edge.
if (BB == &BB->getParent()->getEntryBlock())
- return getEdgeWeight(0, BB);
+ return getEdgeWeight(getEdge(0, BB));
else
return 0; // Otherwise, this is a dead block.
}
// Otherwise, if there are predecessors, the execution count of this block is
- // the sum of the edge frequencies from the incoming edges. Note that if
- // there are multiple edges from a predecessor to this block that we don't
- // want to count its weight multiple times. For this reason, we keep track of
- // the predecessors we've seen and only count them if we haven't run into them
- // yet.
- //
- // We don't want to create an std::set unless we are dealing with a block that
- // has a LARGE number of in-edges. Handle the common case of having only a
- // few in-edges with special code.
- //
- const BasicBlock *FirstPred = *PI;
- unsigned Count = getEdgeWeight(FirstPred, BB);
- ++PI;
- if (PI == PE) return Count; // Quick exit for single predecessor blocks
-
- const BasicBlock *SecondPred = *PI;
- if (SecondPred != FirstPred) Count += getEdgeWeight(SecondPred, BB);
- ++PI;
- if (PI == PE) return Count; // Quick exit for two predecessor blocks
-
- const BasicBlock *ThirdPred = *PI;
- if (ThirdPred != FirstPred && ThirdPred != SecondPred)
- Count += getEdgeWeight(ThirdPred, BB);
- ++PI;
- if (PI == PE) return Count; // Quick exit for three predecessor blocks
-
+ // the sum of the edge frequencies from the incoming edges.
std::set<const BasicBlock*> ProcessedPreds;
- ProcessedPreds.insert(FirstPred);
- ProcessedPreds.insert(SecondPred);
- ProcessedPreds.insert(ThirdPred);
+ double Count = 0;
for (; PI != PE; ++PI)
- if (ProcessedPreds.insert(*PI).second)
- Count += getEdgeWeight(*PI, BB);
+ if (ProcessedPreds.insert(*PI).second) {
+ double w = getEdgeWeight(getEdge(*PI, BB));
+ if (w == MissingValue) {
+ Count = MissingValue; break;
+ }
+ Count += w;
+ }
+
+ BlockInformation[BB->getParent()][BB] = Count;
return Count;
}
-unsigned ProfileInfo::getExecutionCount(const Function *F) const {
- if (FunctionCounts.find(F) != FunctionCounts.end())
- return FunctionCounts.find(F)->second;
+double ProfileInfo::getExecutionCount(const Function *F) {
+ std::map<const Function*, double>::iterator J =
+ FunctionInformation.find(F);
+ if (J != FunctionInformation.end())
+ return J->second;
- return getExecutionCount(&F->getEntryBlock());
+ double Count = getExecutionCount(&F->getEntryBlock());
+ FunctionInformation[F] = Count;
+ return Count;
}
bool LoaderPass::runOnModule(Module &M) {
ProfileInfoLoader PIL("profile-loader", Filename, M);
- EdgeCounts.clear();
+ EdgeInformation.clear();
std::vector<unsigned> ECs = PIL.getRawEdgeCounts();
- std::vector<unsigned> BCs = PIL.getRawBlockCounts();
- std::vector<unsigned> FCs = PIL.getRawFunctionCounts();
- // Instrument all of the edges...
- unsigned ei = 0;
- unsigned bi = 0;
- unsigned fi = 0;
- for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
- if (F->isDeclaration()) continue;
- if (fi<FCs.size()) FunctionCounts[F] = FCs[fi++];
- for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
- if (bi<BCs.size()) BlockCounts[BB] = BCs[bi++];
- // Okay, we have to add a counter of each outgoing edge. If the
- // outgoing edge is not critical don't split it, just insert the counter
- // in the source or destination of the edge.
- TerminatorInst *TI = BB->getTerminator();
- for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
- if (ei < ECs.size())
- EdgeCounts[std::make_pair(BB, TI->getSuccessor(s))]+= ECs[ei++];
+ if (ECs.size() > 0) {
+ unsigned ei = 0;
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ if (F->isDeclaration()) continue;
+ if (ei < ECs.size())
+ EdgeInformation[F][ProfileInfo::getEdge(0,&F->getEntryBlock())] +=
+ ECs[ei++];
+ for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
+ // Okay, we have to add a counter of each outgoing edge. If the
+ // outgoing edge is not critical don't split it, just insert the counter
+ // in the source or destination of the edge.
+ TerminatorInst *TI = BB->getTerminator();
+ for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
+ if (ei < ECs.size())
+ EdgeInformation[F][ProfileInfo::getEdge(BB, TI->getSuccessor(s))] +=
+ ECs[ei++];
+ }
}
}
+ if (ei != ECs.size()) {
+ cerr << "WARNING: profile information is inconsistent with "
+ << "the current program!\n";
+ }
+ }
+
+ BlockInformation.clear();
+ std::vector<unsigned> BCs = PIL.getRawBlockCounts();
+ if (BCs.size() > 0) {
+ unsigned bi = 0;
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ if (F->isDeclaration()) continue;
+ for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
+ if (bi < BCs.size())
+ BlockInformation[F][BB] = BCs[bi++];
+ }
+ if (bi != BCs.size()) {
+ cerr << "WARNING: profile information is inconsistent with "
+ << "the current program!\n";
+ }
}
-
- if (ei != ECs.size()) {
- cerr << "WARNING: profile information is inconsistent with "
- << "the current program!\n";
+
+ FunctionInformation.clear();
+ std::vector<unsigned> FCs = PIL.getRawFunctionCounts();
+ if (FCs.size() > 0) {
+ unsigned fi = 0;
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ if (F->isDeclaration()) continue;
+ if (fi < FCs.size())
+ FunctionInformation[F] = FCs[fi++];
+ }
+ if (fi != FCs.size()) {
+ cerr << "WARNING: profile information is inconsistent with "
+ << "the current program!\n";
+ }
}
return false;
unsigned NumBlocks = 0;
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
- NumBlocks += I->size();
+ if (!I->isDeclaration())
+ NumBlocks += I->size();
const Type *ATy = ArrayType::get(Type::Int32Ty, NumBlocks);
GlobalVariable *Counters =
// Instrument all of the blocks...
unsigned i = 0;
- for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
+ if (I->isDeclaration()) continue;
for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB)
// Insert counter at the start of the block
IncrementCounterInBlock(BB, i++, Counters);
+ }
// Add the initialization call to main.
InsertProfilingInitCall(Main, "llvm_start_block_profiling", Counters);
std::set<BasicBlock*> BlocksToInstrument;
unsigned NumEdges = 0;
- for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ if (F->isDeclaration()) continue;
+ // Reserve space for (0,entry) edge.
+ ++NumEdges;
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
// Keep track of which blocks need to be instrumented. We don't want to
// instrument blocks that are added as the result of breaking critical
BlocksToInstrument.insert(BB);
NumEdges += BB->getTerminator()->getNumSuccessors();
}
+ }
const Type *ATy = ArrayType::get(Type::Int32Ty, NumEdges);
GlobalVariable *Counters =
// Instrument all of the edges...
unsigned i = 0;
- for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ if (F->isDeclaration()) continue;
+ // Create counter for (0,entry) edge.
+ IncrementCounterInBlock(&F->getEntryBlock(), i++, Counters);
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
if (BlocksToInstrument.count(BB)) { // Don't instrument inserted blocks
// Okay, we have to add a counter of each outgoing edge. If the
}
}
}
+ }
// Add the initialization call to main.
InsertProfilingInitCall(Main, "llvm_start_edge_profiling", Counters);
/*empty*/;
if (SI == E) return; // No more successors to place.
- unsigned MaxExecutionCount = PI->getExecutionCount(*SI);
+ double MaxExecutionCount = PI->getExecutionCount(*SI);
BasicBlock *MaxSuccessor = *SI;
// Scan for more frequently executed successors
for (; SI != E; ++SI)
if (!PlacedBlocks.count(*SI)) {
- unsigned Count = PI->getExecutionCount(*SI);
+ double Count = PI->getExecutionCount(*SI);
if (Count > MaxExecutionCount ||
// Prefer to not disturb the code.
(Count == MaxExecutionCount && *SI == &*InsertPos)) {
}
};
+static double ignoreMissing(double w) {
+ if (w == ProfileInfo::MissingValue) return 0;
+ return w;
+}
+
namespace {
class ProfileAnnotator : public AssemblyAnnotationWriter {
ProfileInfo &PI;
ProfileAnnotator(ProfileInfo& pi) : PI(pi) {}
virtual void emitFunctionAnnot(const Function *F, raw_ostream &OS) {
- OS << ";;; %" << F->getName() << " called " << PI.getExecutionCount(F)
- << " times.\n;;;\n";
+ OS << ";;; %" << F->getName() << " called ";
+ double w = PI.getExecutionCount(F);
+ if (w == ProfileInfo::MissingValue)
+ OS << "(no value)";
+ else
+ OS << (unsigned)w;
+ OS << " times.\n;;;\n";
}
virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
raw_ostream &OS) {
- unsigned w = PI.getExecutionCount(BB);
- if (w != 0)
- OS << "\t;;; Basic block executed " << w << " times.\n";
+ double w = PI.getExecutionCount(BB);
+ if (w == ProfileInfo::MissingValue)
+ OS << "\t;;; (no value)\n";
else
- OS << "\t;;; Never executed!\n";
+ if (w != 0)
+ OS << "\t;;; Basic block executed " << w << " times.\n";
+ else
+ OS << "\t;;; Never executed!\n";
}
virtual void emitBasicBlockEndAnnot(const BasicBlock *BB, raw_ostream &OS) {
const TerminatorInst *TI = BB->getTerminator();
for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
BasicBlock* Succ = TI->getSuccessor(s);
- SuccCounts.push_back(std::make_pair(std::make_pair(BB,Succ),
- PI.getEdgeWeight(BB,Succ)));
+ double w = ignoreMissing(PI.getEdgeWeight(std::make_pair(BB,Succ)));
+ SuccCounts.push_back(std::make_pair(std::make_pair(BB,Succ), w));
}
if (!SuccCounts.empty()) {
OS << "\t;;; Out-edge counts:";
std::vector<std::pair<BasicBlock*, unsigned> > Counts;
for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) {
if (FI->isDeclaration()) continue;
- FunctionCounts.push_back(std::make_pair(FI,PI.getExecutionCount(FI)));
+ double w = ignoreMissing(PI.getExecutionCount(FI));
+ FunctionCounts.push_back(std::make_pair(FI,w));
for (Function::iterator BB = FI->begin(), BBE = FI->end();
BB != BBE; ++BB) {
- Counts.push_back(std::make_pair(BB,PI.getExecutionCount(BB)));
+ double w = ignoreMissing(PI.getExecutionCount(BB));
+ Counts.push_back(std::make_pair(BB,w));
}
}
projects / oota-llvm.git / commitdiff