More ProfileInfo improvements.
- Part of optimal static profiling patch sequence by Andreas Neustifter.
- Store edge, block, and function information separately for each functions
(instead of in one giant map).
- Return frequencies as double instead of int, and use a sentinel value for
missing information.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78477 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ProfileInfo.cpp b/lib/Analysis/ProfileInfo.cpp
index 1b86ec8..670d4e7 100644
--- a/lib/Analysis/ProfileInfo.cpp
+++ b/lib/Analysis/ProfileInfo.cpp
@@ -26,9 +26,14 @@
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);
@@ -36,53 +41,37 @@
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;
}
diff --git a/lib/Analysis/ProfileInfoLoaderPass.cpp b/lib/Analysis/ProfileInfoLoaderPass.cpp
index 323174b..c1dc9f2 100644
--- a/lib/Analysis/ProfileInfoLoaderPass.cpp
+++ b/lib/Analysis/ProfileInfoLoaderPass.cpp
@@ -69,34 +69,63 @@
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";
+ }
}
-
- 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";
+ }
+ }
+
+ 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;
diff --git a/lib/Transforms/Instrumentation/BlockProfiling.cpp b/lib/Transforms/Instrumentation/BlockProfiling.cpp
index 9139c92..9102075 100644
--- a/lib/Transforms/Instrumentation/BlockProfiling.cpp
+++ b/lib/Transforms/Instrumentation/BlockProfiling.cpp
@@ -106,7 +106,8 @@
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 =
@@ -115,10 +116,12 @@
// 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);
diff --git a/lib/Transforms/Instrumentation/EdgeProfiling.cpp b/lib/Transforms/Instrumentation/EdgeProfiling.cpp
index f291b44..283f863 100644
--- a/lib/Transforms/Instrumentation/EdgeProfiling.cpp
+++ b/lib/Transforms/Instrumentation/EdgeProfiling.cpp
@@ -55,7 +55,10 @@
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
@@ -63,6 +66,7 @@
BlocksToInstrument.insert(BB);
NumEdges += BB->getTerminator()->getNumSuccessors();
}
+ }
const Type *ATy = ArrayType::get(Type::Int32Ty, NumEdges);
GlobalVariable *Counters =
@@ -71,7 +75,10 @@
// 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
@@ -94,6 +101,7 @@
}
}
}
+ }
// Add the initialization call to main.
InsertProfilingInitCall(Main, "llvm_start_edge_profiling", Counters);
diff --git a/lib/Transforms/Scalar/BasicBlockPlacement.cpp b/lib/Transforms/Scalar/BasicBlockPlacement.cpp
index fb9b880..95fd67b 100644
--- a/lib/Transforms/Scalar/BasicBlockPlacement.cpp
+++ b/lib/Transforms/Scalar/BasicBlockPlacement.cpp
@@ -127,13 +127,13 @@
/*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)) {