ProfileEstimatorPass.cpp [plain text]
#define DEBUG_TYPE "profile-estimator"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ProfileInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
static cl::opt<double>
LoopWeight(
"profile-estimator-loop-weight", cl::init(10),
cl::value_desc("loop-weight"),
cl::desc("Number of loop executions used for profile-estimator")
);
namespace {
class ProfileEstimatorPass : public FunctionPass, public ProfileInfo {
double ExecCount;
LoopInfo *LI;
std::set<BasicBlock*> BBToVisit;
std::map<Loop*,double> LoopExitWeights;
std::map<Edge,double> MinimalWeight;
public:
static char ID; explicit ProfileEstimatorPass(const double execcount = 0)
: FunctionPass(ID), ExecCount(execcount) {
initializeProfileEstimatorPassPass(*PassRegistry::getPassRegistry());
if (execcount == 0) ExecCount = LoopWeight;
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<LoopInfo>();
}
virtual const char *getPassName() const {
return "Profiling information estimator";
}
virtual bool runOnFunction(Function &F);
virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
if (PI == &ProfileInfo::ID)
return (ProfileInfo*)this;
return this;
}
virtual void recurseBasicBlock(BasicBlock *BB);
void inline printEdgeWeight(Edge);
};
}
char ProfileEstimatorPass::ID = 0;
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 {
char &ProfileEstimatorPassID = ProfileEstimatorPass::ID;
FunctionPass *createProfileEstimatorPass() {
return new ProfileEstimatorPass();
}
Pass *createProfileEstimatorPass(const unsigned execcount) {
return new ProfileEstimatorPass(execcount);
}
}
static double ignoreMissing(double w) {
if (w == ProfileInfo::MissingValue) return 0;
return w;
}
static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
DEBUG(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n");
}
void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
DEBUG(dbgs() << "-- Weight of Edge " << E << ":"
<< format("%20.20g", getEdgeWeight(E)) << "\n");
}
void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
if (BBToVisit.find(BB) == BBToVisit.end()) return;
bool BBisHeader = LI->isLoopHeader(BB);
Loop* BBLoop = LI->getLoopFor(BB);
double BBWeight = 0;
std::set<BasicBlock*> ProcessedPreds;
for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
bbi != bbe; ++bbi ) {
Edge edge = getEdge(*bbi,BB);
double w = getEdgeWeight(edge);
if (ProcessedPreds.insert(*bbi).second) {
BBWeight += ignoreMissing(w);
}
if (BBisHeader && BBLoop->contains(*bbi)) {
printEdgeError(edge, "but is backedge, continuing");
continue;
}
if (w == MissingValue) {
printEdgeError(edge, "returning");
return;
}
}
if (getExecutionCount(BB) != MissingValue) {
BBWeight = getExecutionCount(BB);
}
SmallVector<Edge, 8> ExitEdges;
SmallVector<Edge, 8> Edges;
if (BBLoop) {
BBLoop->getExitEdges(ExitEdges);
}
if (BBisHeader) {
double incoming = BBWeight;
std::set<Edge> ProcessedExits;
for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
ee = ExitEdges.end(); ei != ee; ++ei) {
if (ProcessedExits.insert(*ei).second) {
double w = getEdgeWeight(*ei);
if (w == MissingValue) {
Edges.push_back(*ei);
if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
incoming -= MinimalWeight[*ei];
DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
}
} else {
incoming -= w;
}
}
}
if (Edges.size() == 0) {
BasicBlock *Latch = BBLoop->getLoopLatch();
if (Latch) {
Edge edge = getEdge(Latch,0);
EdgeInformation[BB->getParent()][edge] = BBWeight;
printEdgeWeight(edge);
edge = getEdge(Latch, BB);
EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount;
printEdgeWeight(edge);
}
}
double fraction = floor(incoming/Edges.size());
for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
ei != ee; ++ei) {
double w = 0;
if (ei != (ee-1)) {
w = fraction;
incoming -= fraction;
} else {
w = incoming;
}
EdgeInformation[BB->getParent()][*ei] += w;
if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
}
printEdgeWeight(*ei);
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;
}
}
BBWeight *= (ExecCount+1);
}
BlockInformation[BB->getParent()][BB] = BBWeight;
Edges.clear();
std::set<BasicBlock*> ProcessedSuccs;
succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
if (bbi == bbe) {
Edge edge = getEdge(BB,0);
EdgeInformation[BB->getParent()][edge] = BBWeight;
printEdgeWeight(edge);
}
for ( ; bbi != bbe; ++bbi ) {
if (ProcessedSuccs.insert(*bbi).second) {
Edge edge = getEdge(BB,*bbi);
double w = getEdgeWeight(edge);
if (w != MissingValue) {
BBWeight -= getEdgeWeight(edge);
} else {
Edges.push_back(edge);
if (MinimalWeight.find(edge) != MinimalWeight.end()) {
BBWeight -= MinimalWeight[edge];
DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[edge]) << " at " << edge << "\n");
}
}
}
}
double fraction = Edges.size() ? floor(BBWeight/Edges.size()) : 0.0;
for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
ei != ee; ++ei) {
if (ei != (ee-1)) {
EdgeInformation[BB->getParent()][*ei] += fraction;
BBWeight -= fraction;
} else {
EdgeInformation[BB->getParent()][*ei] += BBWeight;
}
if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
}
printEdgeWeight(*ei);
}
BBToVisit.erase(BB);
for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
bbi != bbe; ++bbi) {
recurseBasicBlock(*bbi);
}
}
bool ProfileEstimatorPass::runOnFunction(Function &F) {
if (F.isDeclaration()) return false;
LI = &getAnalysis<LoopInfo>();
FunctionInformation.erase(&F);
BlockInformation[&F].clear();
EdgeInformation[&F].clear();
BBToVisit.clear();
for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
BBToVisit.insert(bi);
MinimalWeight.clear();
DEBUG(dbgs() << "Working on function " << F.getName() << "\n");
BasicBlock *entry = &F.getEntryBlock();
BlockInformation[&F][entry] = pow(2.0, 32.0);
Edge edge = getEdge(0,entry);
EdgeInformation[&F][edge] = BlockInformation[&F][entry];
printEdgeWeight(edge);
bool cleanup = false;
recurseBasicBlock(entry);
while (BBToVisit.size() > 0 && !cleanup) {
unsigned size = BBToVisit.size();
for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(),
be = BBToVisit.end(); bi != be; ++bi) {
recurseBasicBlock(*bi);
if (BBToVisit.size() < size) break;
}
if (BBToVisit.size() == size) {
bool found = false;
for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end();
(BBI != BBE) && (!found); ++BBI) {
BasicBlock *BB = *BBI;
for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
(bbi != bbe) && (!found); ++bbi) {
Edge e = getEdge(*bbi,BB);
double w = getEdgeWeight(e);
if (w == MissingValue) {
Path P;
const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest);
if (Dest != *bbi) {
EdgeInformation[&F][e] = 0;
DEBUG(dbgs() << "Assuming edge weight: ");
printEdgeWeight(e);
found = true;
}
}
}
}
if (!found) {
cleanup = true;
DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n");
}
}
}
if (cleanup) {
FunctionInformation[&F] = 0;
BlockInformation[&F].clear();
EdgeInformation[&F].clear();
for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
const BasicBlock *BB = &(*FI);
BlockInformation[&F][BB] = 0;
const_pred_iterator predi = pred_begin(BB), prede = pred_end(BB);
if (predi == prede) {
Edge e = getEdge(0,BB);
setEdgeWeight(e,0);
}
for (;predi != prede; ++predi) {
Edge e = getEdge(*predi,BB);
setEdgeWeight(e,0);
}
succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB);
if (succi == succe) {
Edge e = getEdge(BB,0);
setEdgeWeight(e,0);
}
for (;succi != succe; ++succi) {
Edge e = getEdge(*succi,BB);
setEdgeWeight(e,0);
}
}
}
return false;
}