aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/ProfileInfoLoader.h9
-rw-r--r--lib/Analysis/ProfileInfoLoader.cpp33
-rw-r--r--lib/Analysis/ProfileInfoLoaderPass.cpp161
3 files changed, 196 insertions, 7 deletions
diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h
index 87faa3e..e74ea3c 100644
--- a/include/llvm/Analysis/ProfileInfoLoader.h
+++ b/include/llvm/Analysis/ProfileInfoLoader.h
@@ -33,6 +33,7 @@ class ProfileInfoLoader {
std::vector<unsigned> FunctionCounts;
std::vector<unsigned> BlockCounts;
std::vector<unsigned> EdgeCounts;
+ std::vector<unsigned> OptimalEdgeCounts;
std::vector<unsigned> BBTrace;
bool Warned;
public:
@@ -66,6 +67,14 @@ public:
const std::vector<unsigned> &getRawEdgeCounts() const {
return EdgeCounts;
}
+
+ // getEdgeOptimalCounts - This method is used by consumers of optimal edge
+ // counting information.
+ //
+ const std::vector<unsigned> &getRawOptimalEdgeCounts() const {
+ return OptimalEdgeCounts;
+ }
+
};
} // End llvm namespace
diff --git a/lib/Analysis/ProfileInfoLoader.cpp b/lib/Analysis/ProfileInfoLoader.cpp
index f0641cf..5ca2e30 100644
--- a/lib/Analysis/ProfileInfoLoader.cpp
+++ b/lib/Analysis/ProfileInfoLoader.cpp
@@ -54,17 +54,34 @@ static void ReadProfilingBlock(const char *ToolName, FILE *F,
exit(1);
}
- // Make sure we have enough space...
+ // Make sure we have enough space... The space is initialised to -1 to
+ // facitiltate the loading of missing values for OptimalEdgeProfiling.
if (Data.size() < NumEntries)
- Data.resize(NumEntries);
+ Data.resize(NumEntries, -1);
// Accumulate the data we just read into the data.
if (!ShouldByteSwap) {
- for (unsigned i = 0; i != NumEntries; ++i)
- Data[i] += TempSpace[i];
+ for (unsigned i = 0; i != NumEntries; ++i) {
+ unsigned data = TempSpace[i];
+ if (data != (unsigned)-1) { // only load data if its not MissingVal
+ if (Data[i] == (unsigned)-1) {
+ Data[i] = data; // if data is still initialised
+ } else {
+ Data[i] += data;
+ }
+ }
+ }
} else {
- for (unsigned i = 0; i != NumEntries; ++i)
- Data[i] += ByteSwap(TempSpace[i], true);
+ for (unsigned i = 0; i != NumEntries; ++i) {
+ unsigned data = ByteSwap(TempSpace[i], true);
+ if (data != (unsigned)-1) { // only load data if its not MissingVal
+ if (Data[i] == (unsigned)-1) {
+ Data[i] = data;
+ } else {
+ Data[i] += data;
+ }
+ }
+ }
}
}
@@ -127,6 +144,10 @@ ProfileInfoLoader::ProfileInfoLoader(const char *ToolName,
ReadProfilingBlock(ToolName, F, ShouldByteSwap, EdgeCounts);
break;
+ case OptEdgeInfo:
+ ReadProfilingBlock(ToolName, F, ShouldByteSwap, OptimalEdgeCounts);
+ break;
+
case BBTraceInfo:
ReadProfilingBlock(ToolName, F, ShouldByteSwap, BBTrace);
break;
diff --git a/lib/Analysis/ProfileInfoLoaderPass.cpp b/lib/Analysis/ProfileInfoLoaderPass.cpp
index 8a8683b..1a2332c 100644
--- a/lib/Analysis/ProfileInfoLoaderPass.cpp
+++ b/lib/Analysis/ProfileInfoLoaderPass.cpp
@@ -11,7 +11,7 @@
// loads the information from a profile dump file.
//
//===----------------------------------------------------------------------===//
-
+#define DEBUG_TYPE "profile-loader"
#include "llvm/BasicBlock.h"
#include "llvm/InstrTypes.h"
#include "llvm/Module.h"
@@ -21,9 +21,17 @@
#include "llvm/Analysis/ProfileInfoLoader.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.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/Statistic.h"
+#include "llvm/ADT/SmallSet.h"
+#include <set>
using namespace llvm;
+STATISTIC(NumEdgesRead, "The # of edges read.");
+
static cl::opt<std::string>
ProfileInfoFilename("profile-info-file", cl::init("llvmprof.out"),
cl::value_desc("filename"),
@@ -32,6 +40,8 @@ ProfileInfoFilename("profile-info-file", cl::init("llvmprof.out"),
namespace {
class VISIBILITY_HIDDEN LoaderPass : public ModulePass, public ProfileInfo {
std::string Filename;
+ std::set<Edge> SpanningTree;
+ std::set<const BasicBlock*> BBisUnvisited;
public:
static char ID; // Class identification, replacement for typeinfo
explicit LoaderPass(const std::string &filename = "")
@@ -47,6 +57,13 @@ namespace {
return "Profiling information loader";
}
+ // recurseBasicBlock() - Calculates the edge weights for as much basic
+ // blocks as possbile.
+ virtual void recurseBasicBlock(const BasicBlock *BB);
+ virtual void readEdgeOrRemember(Edge, Edge&, unsigned &, unsigned &);
+ virtual void readOrRememberEdge(ProfileInfo::Edge, unsigned,
+ unsigned, Function*);
+
/// run - Load the profile information from the specified file.
virtual bool runOnModule(Module &M);
};
@@ -67,6 +84,90 @@ Pass *llvm::createProfileLoaderPass(const std::string &Filename) {
return new LoaderPass(Filename);
}
+void LoaderPass::readEdgeOrRemember(Edge edge, Edge &tocalc,
+ unsigned &uncalc, unsigned &count) {
+ double w;
+ if ((w = getEdgeWeight(edge)) == MissingValue) {
+ tocalc = edge;
+ uncalc++;
+ } else {
+ count+=w;
+ }
+}
+
+// recurseBasicBlock - Visits all neighbours of a block and then tries to
+// calculate the missing edge values.
+void LoaderPass::recurseBasicBlock(const BasicBlock *BB) {
+
+ // break recursion if already visited
+ if (BBisUnvisited.find(BB) == BBisUnvisited.end()) return;
+ BBisUnvisited.erase(BB);
+ if (!BB) return;
+
+ for (succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
+ bbi != bbe; ++bbi) {
+ recurseBasicBlock(*bbi);
+ }
+ for (pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
+ bbi != bbe; ++bbi) {
+ recurseBasicBlock(*bbi);
+ }
+
+ Edge edgetocalc;
+ unsigned uncalculated = 0;
+
+ // collect weights of all incoming and outgoing edges, rememer edges that
+ // have no value
+ unsigned incount = 0;
+ SmallSet<const BasicBlock*,8> pred_visited;
+ pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
+ if (bbi==bbe) {
+ readEdgeOrRemember(getEdge(0, BB),edgetocalc,uncalculated,incount);
+ }
+ for (;bbi != bbe; ++bbi) {
+ if (pred_visited.insert(*bbi)) {
+ readEdgeOrRemember(getEdge(*bbi, BB),edgetocalc,uncalculated,incount);
+ }
+ }
+
+ unsigned outcount = 0;
+ SmallSet<const BasicBlock*,8> succ_visited;
+ succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
+ if (sbbi==sbbe) {
+ readEdgeOrRemember(getEdge(BB, 0),edgetocalc,uncalculated,outcount);
+ }
+ for (;sbbi != sbbe; ++sbbi) {
+ if (succ_visited.insert(*sbbi)) {
+ readEdgeOrRemember(getEdge(BB, *sbbi),edgetocalc,uncalculated,outcount);
+ }
+ }
+
+ // if exactly one edge weight was missing, calculate it and remove it from
+ // spanning tree
+ 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("%g", getEdgeWeight(edgetocalc)) << "\n");
+ SpanningTree.erase(edgetocalc);
+ }
+}
+
+void LoaderPass::readOrRememberEdge(ProfileInfo::Edge e,
+ unsigned weight, unsigned ei,
+ Function *F) {
+ if (weight != (unsigned)MissingValue) {
+ EdgeInformation[F][e] += weight;
+ DEBUG(errs()<<"--Read Edge Counter for " << e
+ <<" (# "<<ei<<"): "<<(unsigned)getEdgeWeight(e)<<"\n");
+ } else {
+ SpanningTree.insert(e);
+ }
+}
+
bool LoaderPass::runOnModule(Module &M) {
ProfileInfoLoader PIL("profile-loader", Filename, M);
@@ -95,6 +196,64 @@ bool LoaderPass::runOnModule(Module &M) {
errs() << "WARNING: profile information is inconsistent with "
<< "the current program!\n";
}
+ NumEdgesRead = ei;
+ }
+
+ ECs = PIL.getRawOptimalEdgeCounts();
+ if (ECs.size() > 0) {
+ unsigned ei = 0;
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ if (F->isDeclaration()) continue;
+ DEBUG(errs()<<"Working on "<<F->getNameStr()<<"\n");
+ if (ei < ECs.size()) {
+ readOrRememberEdge(getEdge(0,&F->getEntryBlock()), ECs[ei], ei, F);
+ ei++;
+ }
+ for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
+ TerminatorInst *TI = BB->getTerminator();
+ if (TI->getNumSuccessors() == 0) {
+ if (ei < ECs.size()) {
+ readOrRememberEdge(getEdge(BB,0), ECs[ei], ei, F); ei++;
+ }
+ }
+ for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
+ if (ei < ECs.size()) {
+ readOrRememberEdge(getEdge(BB,TI->getSuccessor(s)), ECs[ei], ei, F);
+ ei++;
+ }
+ }
+ }
+ while (SpanningTree.size() > 0) {
+#if 0
+ unsigned size = SpanningTree.size();
+#endif
+ BBisUnvisited.clear();
+ for (std::set<Edge>::iterator ei = SpanningTree.begin(),
+ ee = SpanningTree.end(); ei != ee; ++ei) {
+ BBisUnvisited.insert(ei->first);
+ BBisUnvisited.insert(ei->second);
+ }
+ while (BBisUnvisited.size() > 0) {
+ recurseBasicBlock(*BBisUnvisited.begin());
+ }
+#if 0
+ if (SpanningTree.size() == size) {
+ DEBUG(errs()<<"{");
+ for (std::set<Edge>::iterator ei = SpanningTree.begin(),
+ ee = SpanningTree.end(); ei != ee; ++ei) {
+ DEBUG(errs()<<"("<<(ei->first?ei->first->getName():"0")<<","
+ <<(ei->second?ei->second->getName():"0")<<"),");
+ }
+ assert(0 && "No edge calculated!");
+ }
+#endif
+ }
+ }
+ if (ei != ECs.size()) {
+ errs() << "WARNING: profile information is inconsistent with "
+ << "the current program!\n";
+ }
+ NumEdgesRead = ei;
}
BlockInformation.clear();
generated by cgit v1.1 at 2025-01-15 04:00:30 +0000