#define DEBUG_TYPE "insert-path-profiling"
#include "llvm/DerivedTypes.h"
#include "ProfilingUtils.h"
#include "llvm/Analysis/PathNumbering.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/InstrTypes.h"
#include "llvm/Instructions.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/TypeBuilder.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Instrumentation.h"
#include <vector>
#define HASH_THRESHHOLD 100000
using namespace llvm;
namespace {
class BLInstrumentationNode;
class BLInstrumentationEdge;
class BLInstrumentationDag;
class BLInstrumentationNode : public BallLarusNode {
public:
BLInstrumentationNode(BasicBlock* BB);
Value* getStartingPathNumber();
void setStartingPathNumber(Value* pathNumber);
Value* getEndingPathNumber();
void setEndingPathNumber(Value* pathNumber);
PHINode* getPathPHI();
void setPathPHI(PHINode* pathPHI);
private:
Value* _startingPathNumber; Value* _endingPathNumber; PHINode* _pathPHI; };
class BLInstrumentationEdge : public BallLarusEdge {
public:
BLInstrumentationEdge(BLInstrumentationNode* source,
BLInstrumentationNode* target);
void setTarget(BallLarusNode* node);
bool isInSpanningTree() const;
void setIsInSpanningTree(bool isInSpanningTree);
bool isInitialization() const;
void setIsInitialization(bool isInitialization);
bool isCounterIncrement() const;
void setIsCounterIncrement(bool isCounterIncrement);
long getIncrement() const;
void setIncrement(long increment);
bool hasInstrumentation();
void setHasInstrumentation(bool hasInstrumentation);
unsigned getSuccessorNumber();
private:
long long _increment;
bool _isInSpanningTree;
bool _isInitialization;
bool _isCounterIncrement;
bool _hasInstrumentation;
};
class BLInstrumentationDag : public BallLarusDag {
public:
BLInstrumentationDag(Function &F);
BallLarusEdge* getExitRootEdge();
BLEdgeVector getCallPhonyEdges();
GlobalVariable* getCounterArray();
void setCounterArray(GlobalVariable* c);
void calculateChordIncrements();
void splitUpdate(BLInstrumentationEdge* formerEdge, BasicBlock* newBlock);
void calculateSpanningTree();
void pushInitialization();
void pushCounters();
void unlinkPhony();
void generateDotGraph();
protected:
virtual BallLarusNode* createNode(BasicBlock* BB);
virtual BallLarusEdge* createEdge(
BallLarusNode* source, BallLarusNode* target, unsigned edgeNumber);
private:
BLEdgeVector _treeEdges; BLEdgeVector _chordEdges; GlobalVariable* _counterArray;
void unlinkEdge(BallLarusEdge* edge);
void makeEdgeSpanning(BLInstrumentationEdge* edge);
void pushInitializationFromEdge(BLInstrumentationEdge* edge);
void pushCountersFromEdge(BLInstrumentationEdge* edge);
void calculateChordIncrementsDfs(
long weight, BallLarusNode* v, BallLarusEdge* e);
int calculateChordIncrementsDir(BallLarusEdge* e, BallLarusEdge* f);
};
class PathProfiler : public ModulePass {
private:
LLVMContext* Context;
unsigned currentFunctionNumber;
Constant* llvmIncrementHashFunction;
Constant* llvmDecrementHashFunction;
bool runOnModule(Module &M);
void runOnFunction(std::vector<Constant*> &ftInit, Function &F, Module &M);
ConstantInt* createIncrementConstant(long incr, int bitsize);
ConstantInt* createIncrementConstant(BLInstrumentationEdge* edge);
BasicBlock::iterator getInsertionPoint(
BasicBlock* block, Value* pathNumber);
void pushValueIntoNode(
BLInstrumentationNode* source, BLInstrumentationNode* target);
void pushValueIntoPHI(
BLInstrumentationNode* target, BLInstrumentationNode* source);
void insertNumberIncrement(BLInstrumentationNode* node, Value* addition,
bool atBeginning);
void insertCounterIncrement(
Value* incValue,
BasicBlock::iterator insertPoint,
BLInstrumentationDag* dag,
bool increment = true);
void preparePHI(BLInstrumentationNode* node);
void insertInstrumentationStartingAt(
BLInstrumentationEdge* edge,
BLInstrumentationDag* dag);
bool splitCritical(BLInstrumentationEdge* edge, BLInstrumentationDag* dag);
void insertInstrumentation( BLInstrumentationDag& dag, Module &M);
public:
static char ID; PathProfiler() : ModulePass(ID) {
initializePathProfilerPass(*PassRegistry::getPassRegistry());
}
virtual const char *getPassName() const {
return "Path Profiler";
}
};
}
static cl::opt<bool> DotPathDag("path-profile-pathdag", cl::Hidden,
cl::desc("Output the path profiling DAG for each function."));
char PathProfiler::ID = 0;
INITIALIZE_PASS(PathProfiler, "insert-path-profiling",
"Insert instrumentation for Ball-Larus path profiling",
false, false)
ModulePass *llvm::createPathProfilerPass() { return new PathProfiler(); }
namespace llvm {
class PathProfilingFunctionTable {};
template<bool xcompile> class TypeBuilder<PathProfilingFunctionTable,
xcompile> {
public:
static StructType *get(LLVMContext& C) {
return( StructType::get(
TypeBuilder<types::i<32>, xcompile>::get(C), TypeBuilder<types::i<32>, xcompile>::get(C), TypeBuilder<types::i<8>*, xcompile>::get(C), NULL));
}
};
typedef TypeBuilder<PathProfilingFunctionTable, true>
ftEntryTypeBuilder;
raw_ostream& operator<<(raw_ostream& os,
const BLInstrumentationEdge& edge)
LLVM_ATTRIBUTE_USED;
raw_ostream& operator<<(raw_ostream& os,
const BLInstrumentationEdge& edge) {
os << "[" << edge.getSource()->getName() << " -> "
<< edge.getTarget()->getName() << "] init: "
<< (edge.isInitialization() ? "yes" : "no")
<< " incr:" << edge.getIncrement() << " cinc: "
<< (edge.isCounterIncrement() ? "yes" : "no");
return(os);
}
}
BLInstrumentationNode::BLInstrumentationNode(BasicBlock* BB) :
BallLarusNode(BB),
_startingPathNumber(NULL), _endingPathNumber(NULL), _pathPHI(NULL) {}
BLInstrumentationEdge::BLInstrumentationEdge(BLInstrumentationNode* source,
BLInstrumentationNode* target)
: BallLarusEdge(source, target, 0),
_increment(0), _isInSpanningTree(false), _isInitialization(false),
_isCounterIncrement(false), _hasInstrumentation(false) {}
void BLInstrumentationEdge::setTarget(BallLarusNode* node) {
_target = node;
}
bool BLInstrumentationEdge::isInSpanningTree() const {
return(_isInSpanningTree);
}
void BLInstrumentationEdge::setIsInSpanningTree(bool isInSpanningTree) {
_isInSpanningTree = isInSpanningTree;
}
bool BLInstrumentationEdge::isInitialization() const {
return(_isInitialization);
}
void BLInstrumentationEdge::setIsInitialization(bool isInitialization) {
_isInitialization = isInitialization;
}
bool BLInstrumentationEdge::isCounterIncrement() const {
return(_isCounterIncrement);
}
void BLInstrumentationEdge::setIsCounterIncrement(bool isCounterIncrement) {
_isCounterIncrement = isCounterIncrement;
}
long BLInstrumentationEdge::getIncrement() const {
return(_increment);
}
void BLInstrumentationEdge::setIncrement(long increment) {
_increment = increment;
}
bool BLInstrumentationEdge::hasInstrumentation() {
return(_hasInstrumentation);
}
void BLInstrumentationEdge::setHasInstrumentation(bool hasInstrumentation) {
_hasInstrumentation = hasInstrumentation;
}
unsigned BLInstrumentationEdge::getSuccessorNumber() {
BallLarusNode* sourceNode = getSource();
BallLarusNode* targetNode = getTarget();
BasicBlock* source = sourceNode->getBlock();
BasicBlock* target = targetNode->getBlock();
if(source == NULL || target == NULL)
return(0);
TerminatorInst* terminator = source->getTerminator();
unsigned i;
for(i=0; i < terminator->getNumSuccessors(); i++) {
if(terminator->getSuccessor(i) == target)
break;
}
return(i);
}
BLInstrumentationDag::BLInstrumentationDag(Function &F) : BallLarusDag(F),
_counterArray(0) {
}
BallLarusEdge* BLInstrumentationDag::getExitRootEdge() {
BLEdgeIterator erEdge = getExit()->succBegin();
return(*erEdge);
}
BLEdgeVector BLInstrumentationDag::getCallPhonyEdges () {
BLEdgeVector callEdges;
for( BLEdgeIterator edge = _edges.begin(), end = _edges.end();
edge != end; edge++ ) {
if( (*edge)->getType() == BallLarusEdge::CALLEDGE_PHONY )
callEdges.push_back(*edge);
}
return callEdges;
}
GlobalVariable* BLInstrumentationDag::getCounterArray() {
return _counterArray;
}
void BLInstrumentationDag::setCounterArray(GlobalVariable* c) {
_counterArray = c;
}
void BLInstrumentationDag::calculateChordIncrements() {
calculateChordIncrementsDfs(0, getRoot(), NULL);
BLInstrumentationEdge* chord;
for(BLEdgeIterator chordEdge = _chordEdges.begin(),
end = _chordEdges.end(); chordEdge != end; chordEdge++) {
chord = (BLInstrumentationEdge*) *chordEdge;
chord->setIncrement(chord->getIncrement() + chord->getWeight());
}
}
void BLInstrumentationDag::splitUpdate(BLInstrumentationEdge* formerEdge,
BasicBlock* newBlock) {
BallLarusNode* oldTarget = formerEdge->getTarget();
BallLarusNode* newNode = addNode(newBlock);
formerEdge->setTarget(newNode);
newNode->addPredEdge(formerEdge);
DEBUG(dbgs() << " Edge split: " << *formerEdge << "\n");
oldTarget->removePredEdge(formerEdge);
BallLarusEdge* newEdge = addEdge(newNode, oldTarget,0);
if( formerEdge->getType() == BallLarusEdge::BACKEDGE ||
formerEdge->getType() == BallLarusEdge::SPLITEDGE) {
newEdge->setType(formerEdge->getType());
newEdge->setPhonyRoot(formerEdge->getPhonyRoot());
newEdge->setPhonyExit(formerEdge->getPhonyExit());
formerEdge->setType(BallLarusEdge::NORMAL);
formerEdge->setPhonyRoot(NULL);
formerEdge->setPhonyExit(NULL);
}
}
void BLInstrumentationDag::calculateSpanningTree() {
std::stack<BallLarusNode*> dfsStack;
for(BLNodeIterator nodeIt = _nodes.begin(), end = _nodes.end();
nodeIt != end; nodeIt++) {
(*nodeIt)->setColor(BallLarusNode::WHITE);
}
dfsStack.push(getRoot());
while(dfsStack.size() > 0) {
BallLarusNode* node = dfsStack.top();
dfsStack.pop();
if(node->getColor() == BallLarusNode::WHITE)
continue;
BallLarusNode* nextNode;
bool forward = true;
BLEdgeIterator succEnd = node->succEnd();
node->setColor(BallLarusNode::WHITE);
for(BLEdgeIterator edge = node->succBegin(), predEnd = node->predEnd();
edge != predEnd; edge++) {
if(edge == succEnd) {
edge = node->predBegin();
forward = false;
}
if ((*edge)->getType() == BallLarusEdge::SPLITEDGE)
continue;
nextNode = forward? (*edge)->getTarget(): (*edge)->getSource();
if(nextNode->getColor() != BallLarusNode::WHITE) {
nextNode->setColor(BallLarusNode::WHITE);
makeEdgeSpanning((BLInstrumentationEdge*)(*edge));
}
}
}
for(BLEdgeIterator edge = _edges.begin(), end = _edges.end();
edge != end; edge++) {
BLInstrumentationEdge* instEdge = (BLInstrumentationEdge*) (*edge);
if(!instEdge->isInSpanningTree() && (*edge)->getType()
!= BallLarusEdge::SPLITEDGE)
_chordEdges.push_back(instEdge);
}
}
void BLInstrumentationDag::pushInitialization() {
BLInstrumentationEdge* exitRootEdge =
(BLInstrumentationEdge*) getExitRootEdge();
exitRootEdge->setIsInitialization(true);
pushInitializationFromEdge(exitRootEdge);
}
void BLInstrumentationDag::pushCounters() {
BLInstrumentationEdge* exitRootEdge =
(BLInstrumentationEdge*) getExitRootEdge();
exitRootEdge->setIsCounterIncrement(true);
pushCountersFromEdge(exitRootEdge);
}
void BLInstrumentationDag::unlinkPhony() {
BallLarusEdge* edge;
for(BLEdgeIterator next = _edges.begin(),
end = _edges.end(); next != end; next++) {
edge = (*next);
if( edge->getType() == BallLarusEdge::BACKEDGE_PHONY ||
edge->getType() == BallLarusEdge::SPLITEDGE_PHONY ||
edge->getType() == BallLarusEdge::CALLEDGE_PHONY ) {
unlinkEdge(edge);
}
}
}
void BLInstrumentationDag::generateDotGraph() {
std::string errorInfo;
std::string functionName = getFunction().getName().str();
std::string filename = "pathdag." + functionName + ".dot";
DEBUG (dbgs() << "Writing '" << filename << "'...\n");
raw_fd_ostream dotFile(filename.c_str(), errorInfo);
if (!errorInfo.empty()) {
errs() << "Error opening '" << filename.c_str() <<"' for writing!";
errs() << "\n";
return;
}
dotFile << "digraph " << functionName << " {\n";
for( BLEdgeIterator edge = _edges.begin(), end = _edges.end();
edge != end; edge++) {
std::string sourceName = (*edge)->getSource()->getName();
std::string targetName = (*edge)->getTarget()->getName();
dotFile << "\t\"" << sourceName.c_str() << "\" -> \""
<< targetName.c_str() << "\" ";
long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
switch( (*edge)->getType() ) {
case BallLarusEdge::NORMAL:
dotFile << "[label=" << inc << "] [color=black];\n";
break;
case BallLarusEdge::BACKEDGE:
dotFile << "[color=cyan];\n";
break;
case BallLarusEdge::BACKEDGE_PHONY:
dotFile << "[label=" << inc
<< "] [color=blue];\n";
break;
case BallLarusEdge::SPLITEDGE:
dotFile << "[color=violet];\n";
break;
case BallLarusEdge::SPLITEDGE_PHONY:
dotFile << "[label=" << inc << "] [color=red];\n";
break;
case BallLarusEdge::CALLEDGE_PHONY:
dotFile << "[label=" << inc << "] [color=green];\n";
break;
}
}
dotFile << "}\n";
}
BallLarusNode* BLInstrumentationDag::createNode(BasicBlock* BB) {
return( new BLInstrumentationNode(BB) );
}
BallLarusEdge* BLInstrumentationDag::createEdge(BallLarusNode* source,
BallLarusNode* target, unsigned edgeNumber) {
return( new BLInstrumentationEdge((BLInstrumentationNode*)source,
(BLInstrumentationNode*)target) );
}
Value* BLInstrumentationNode::getStartingPathNumber(){
return(_startingPathNumber);
}
void BLInstrumentationNode::setStartingPathNumber(Value* pathNumber) {
DEBUG(dbgs() << " SPN-" << getName() << " <-- " << (pathNumber ?
pathNumber->getName() :
"unused") << "\n");
_startingPathNumber = pathNumber;
}
Value* BLInstrumentationNode::getEndingPathNumber(){
return(_endingPathNumber);
}
void BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) {
DEBUG(dbgs() << " EPN-" << getName() << " <-- "
<< (pathNumber ? pathNumber->getName() : "unused") << "\n");
_endingPathNumber = pathNumber;
}
PHINode* BLInstrumentationNode::getPathPHI() {
return(_pathPHI);
}
void BLInstrumentationNode::setPathPHI(PHINode* pathPHI) {
_pathPHI = pathPHI;
}
void BLInstrumentationDag::unlinkEdge(BallLarusEdge* edge) {
if(edge == getExitRootEdge())
DEBUG(dbgs() << " Removing exit->root edge\n");
edge->getSource()->removeSuccEdge(edge);
edge->getTarget()->removePredEdge(edge);
}
void BLInstrumentationDag::makeEdgeSpanning(BLInstrumentationEdge* edge) {
edge->setIsInSpanningTree(true);
_treeEdges.push_back(edge);
}
void BLInstrumentationDag::pushInitializationFromEdge(
BLInstrumentationEdge* edge) {
BallLarusNode* target;
target = edge->getTarget();
if( target->getNumberPredEdges() > 1 || target == getExit() ) {
return;
} else {
for(BLEdgeIterator next = target->succBegin(),
end = target->succEnd(); next != end; next++) {
BLInstrumentationEdge* intoEdge = (BLInstrumentationEdge*) *next;
if (intoEdge->getType() == BallLarusEdge::SPLITEDGE)
continue;
intoEdge->setIncrement(intoEdge->getIncrement() +
edge->getIncrement());
intoEdge->setIsInitialization(true);
pushInitializationFromEdge(intoEdge);
}
edge->setIncrement(0);
edge->setIsInitialization(false);
}
}
void BLInstrumentationDag::pushCountersFromEdge(BLInstrumentationEdge* edge) {
BallLarusNode* source;
source = edge->getSource();
if(source->getNumberSuccEdges() > 1 || source == getRoot()
|| edge->isInitialization()) {
return;
} else {
for(BLEdgeIterator previous = source->predBegin(),
end = source->predEnd(); previous != end; previous++) {
BLInstrumentationEdge* fromEdge = (BLInstrumentationEdge*) *previous;
if (fromEdge->getType() == BallLarusEdge::SPLITEDGE)
continue;
fromEdge->setIncrement(fromEdge->getIncrement() +
edge->getIncrement());
fromEdge->setIsCounterIncrement(true);
pushCountersFromEdge(fromEdge);
}
edge->setIncrement(0);
edge->setIsCounterIncrement(false);
}
}
void BLInstrumentationDag::calculateChordIncrementsDfs(long weight,
BallLarusNode* v, BallLarusEdge* e) {
BLInstrumentationEdge* f;
for(BLEdgeIterator treeEdge = _treeEdges.begin(),
end = _treeEdges.end(); treeEdge != end; treeEdge++) {
f = (BLInstrumentationEdge*) *treeEdge;
if(e != f && v == f->getTarget()) {
calculateChordIncrementsDfs(
calculateChordIncrementsDir(e,f)*(weight) +
f->getWeight(), f->getSource(), f);
}
if(e != f && v == f->getSource()) {
calculateChordIncrementsDfs(
calculateChordIncrementsDir(e,f)*(weight) +
f->getWeight(), f->getTarget(), f);
}
}
for(BLEdgeIterator chordEdge = _chordEdges.begin(),
end = _chordEdges.end(); chordEdge != end; chordEdge++) {
f = (BLInstrumentationEdge*) *chordEdge;
if(v == f->getSource() || v == f->getTarget()) {
f->setIncrement(f->getIncrement() +
calculateChordIncrementsDir(e,f)*weight);
}
}
}
int BLInstrumentationDag::calculateChordIncrementsDir(BallLarusEdge* e,
BallLarusEdge* f) {
if( e == NULL)
return(1);
else if(e->getSource() == f->getTarget()
|| e->getTarget() == f->getSource())
return(1);
return(-1);
}
ConstantInt* PathProfiler::createIncrementConstant(long incr,
int bitsize) {
return(ConstantInt::get(IntegerType::get(*Context, 32), incr));
}
ConstantInt* PathProfiler::createIncrementConstant(
BLInstrumentationEdge* edge) {
return(createIncrementConstant(edge->getIncrement(), 32));
}
BasicBlock::iterator PathProfiler::getInsertionPoint(BasicBlock* block, Value*
pathNumber) {
if(pathNumber == NULL || isa<ConstantInt>(pathNumber)
|| (((Instruction*)(pathNumber))->getParent()) != block) {
return(block->getFirstInsertionPt());
} else {
Instruction* pathNumberInst = (Instruction*) (pathNumber);
BasicBlock::iterator insertPoint;
BasicBlock::iterator end = block->end();
for(insertPoint = block->begin();
insertPoint != end; insertPoint++) {
Instruction* insertInst = &(*insertPoint);
if(insertInst == pathNumberInst)
return(++insertPoint);
}
return(insertPoint);
}
}
void PathProfiler::preparePHI(BLInstrumentationNode* node) {
BasicBlock* block = node->getBlock();
BasicBlock::iterator insertPoint = block->getFirstInsertionPt();
pred_iterator PB = pred_begin(node->getBlock()),
PE = pred_end(node->getBlock());
PHINode* phi = PHINode::Create(Type::getInt32Ty(*Context),
std::distance(PB, PE), "pathNumber",
insertPoint );
node->setPathPHI(phi);
node->setStartingPathNumber(phi);
node->setEndingPathNumber(phi);
for(pred_iterator predIt = PB; predIt != PE; predIt++) {
BasicBlock* pred = (*predIt);
if(pred != NULL)
phi->addIncoming(createIncrementConstant((long)-1, 32), pred);
}
}
void PathProfiler::pushValueIntoNode(BLInstrumentationNode* source,
BLInstrumentationNode* target) {
if(target->getBlock() == NULL)
return;
if(target->getNumberPredEdges() <= 1) {
assert(target->getStartingPathNumber() == NULL &&
"Target already has path number");
target->setStartingPathNumber(source->getEndingPathNumber());
target->setEndingPathNumber(source->getEndingPathNumber());
DEBUG(dbgs() << " Passing path number"
<< (source->getEndingPathNumber() ? "" : " (null)")
<< " value through.\n");
} else {
if(target->getPathPHI() == NULL) {
DEBUG(dbgs() << " Initializing PHI node for block '"
<< target->getName() << "'\n");
preparePHI(target);
}
pushValueIntoPHI(target, source);
DEBUG(dbgs() << " Passing number value into PHI for block '"
<< target->getName() << "'\n");
}
}
void PathProfiler::pushValueIntoPHI(BLInstrumentationNode* target,
BLInstrumentationNode* source) {
PHINode* phi = target->getPathPHI();
assert(phi != NULL && " Tried to push value into node with PHI, but node"
" actually had no PHI.");
phi->removeIncomingValue(source->getBlock(), false);
phi->addIncoming(source->getEndingPathNumber(), source->getBlock());
}
void PathProfiler::insertNumberIncrement(BLInstrumentationNode* node,
Value* addition, bool atBeginning) {
BasicBlock* block = node->getBlock();
assert(node->getStartingPathNumber() != NULL);
assert(node->getEndingPathNumber() != NULL);
BasicBlock::iterator insertPoint;
if( atBeginning )
insertPoint = block->getFirstInsertionPt();
else
insertPoint = block->getTerminator();
DEBUG(errs() << " Creating addition instruction.\n");
Value* newpn = BinaryOperator::Create(Instruction::Add,
node->getStartingPathNumber(),
addition, "pathNumber", insertPoint);
node->setEndingPathNumber(newpn);
if( atBeginning )
node->setStartingPathNumber(newpn);
}
void PathProfiler::insertCounterIncrement(Value* incValue,
BasicBlock::iterator insertPoint,
BLInstrumentationDag* dag,
bool increment) {
if( dag->getNumberOfPaths() <= HASH_THRESHHOLD ) {
std::vector<Value*> gepIndices(2);
gepIndices[0] = Constant::getNullValue(Type::getInt32Ty(*Context));
gepIndices[1] = incValue;
GetElementPtrInst* pcPointer =
GetElementPtrInst::Create(dag->getCounterArray(), gepIndices,
"counterInc", insertPoint);
LoadInst* oldPc = new LoadInst(pcPointer, "oldPC", insertPoint);
ICmpInst* isMax = new ICmpInst(insertPoint, CmpInst::ICMP_ULT, oldPc,
createIncrementConstant(0xffffffff, 32),
"isMax");
SelectInst* inc =
SelectInst::Create( isMax, createIncrementConstant(increment?1:-1,32),
createIncrementConstant(0,32),
"pathInc", insertPoint);
BinaryOperator* newPc = BinaryOperator::Create(Instruction::Add,
oldPc, inc, "newPC",
insertPoint);
new StoreInst(newPc, pcPointer, insertPoint);
} else { std::vector<Value*> args(2);
args[0] = ConstantInt::get(Type::getInt32Ty(*Context),
currentFunctionNumber);
args[1] = incValue;
CallInst::Create(
increment ? llvmIncrementHashFunction : llvmDecrementHashFunction,
args, "", insertPoint);
}
}
void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge* edge,
BLInstrumentationDag* dag) {
edge->setHasInstrumentation(true);
DEBUG(dbgs() << "\nInstrumenting edge: " << (*edge) << "\n");
splitCritical(edge, dag);
BLInstrumentationNode* sourceNode = (BLInstrumentationNode*)edge->getSource();
BLInstrumentationNode* targetNode = (BLInstrumentationNode*)edge->getTarget();
BLInstrumentationNode* instrumentNode;
BLInstrumentationNode* nextSourceNode;
bool atBeginning = false;
if( sourceNode->getBlock() && sourceNode->getNumberSuccEdges() <= 1) {
DEBUG(dbgs() << " Potential instructions to be placed in: "
<< sourceNode->getName() << " (at end)\n");
instrumentNode = sourceNode;
nextSourceNode = targetNode; }
else if( targetNode->getNumberPredEdges() == 1 ) {
DEBUG(dbgs() << " Potential instructions to be placed in: "
<< targetNode->getName() << " (at beginning)\n");
pushValueIntoNode(sourceNode, targetNode);
instrumentNode = targetNode;
nextSourceNode = NULL; atBeginning = true;
}
else {
errs() << "Instrumenting could not split a critical edge.\n";
DEBUG(dbgs() << " Couldn't split edge " << (*edge) << ".\n");
return;
}
if( edge->getType() == BallLarusEdge::BACKEDGE ||
edge->getType() == BallLarusEdge::SPLITEDGE ) {
BLInstrumentationEdge* top =
(BLInstrumentationEdge*) edge->getPhonyRoot();
BLInstrumentationEdge* bottom =
(BLInstrumentationEdge*) edge->getPhonyExit();
assert( top->isInitialization() && " Top phony edge did not"
" contain a path number initialization.");
assert( bottom->isCounterIncrement() && " Bottom phony edge"
" did not contain a path counter increment.");
if( !instrumentNode->getEndingPathNumber() ) {
instrumentNode->setStartingPathNumber(createIncrementConstant(0,32));
instrumentNode->setEndingPathNumber(createIncrementConstant(0,32));
}
BasicBlock::iterator insertPoint = atBeginning ?
instrumentNode->getBlock()->getFirstInsertionPt() :
instrumentNode->getBlock()->getTerminator();
if( bottom->getIncrement() ) {
Value* newpn =
BinaryOperator::Create(Instruction::Add,
instrumentNode->getStartingPathNumber(),
createIncrementConstant(bottom),
"pathNumber", insertPoint);
instrumentNode->setEndingPathNumber(newpn);
}
insertCounterIncrement(instrumentNode->getEndingPathNumber(),
insertPoint, dag);
if( atBeginning )
instrumentNode->setStartingPathNumber(createIncrementConstant(top));
instrumentNode->setEndingPathNumber(createIncrementConstant(top));
if( top->isCounterIncrement() ) {
insertCounterIncrement(instrumentNode->getEndingPathNumber(),
instrumentNode->getBlock()->getTerminator(),dag);
instrumentNode->setEndingPathNumber(0);
}
}
else {
BasicBlock::iterator insertPoint = atBeginning ?
instrumentNode->getBlock()->getFirstInsertionPt() :
instrumentNode->getBlock()->getTerminator();
if( edge->isInitialization() ) { instrumentNode->setEndingPathNumber(createIncrementConstant(edge));
} else if( edge->getIncrement() ) { Value* newpn =
BinaryOperator::Create(Instruction::Add,
instrumentNode->getStartingPathNumber(),
createIncrementConstant(edge),
"pathNumber", insertPoint);
instrumentNode->setEndingPathNumber(newpn);
if( atBeginning )
instrumentNode->setStartingPathNumber(newpn);
}
if( edge->isCounterIncrement() ) {
insertCounterIncrement(instrumentNode->getEndingPathNumber(),
insertPoint, dag);
instrumentNode->setEndingPathNumber(0);
}
}
if (nextSourceNode && instrumentNode->getEndingPathNumber())
pushValueIntoNode(instrumentNode, nextSourceNode);
for( BLEdgeIterator next = targetNode->succBegin(),
end = targetNode->succEnd(); next != end; next++ ) {
if( !((BLInstrumentationEdge*)(*next))->hasInstrumentation() )
insertInstrumentationStartingAt((BLInstrumentationEdge*)*next,dag);
else
DEBUG(dbgs() << " Edge " << *(BLInstrumentationEdge*)(*next)
<< " already instrumented.\n");
}
}
void PathProfiler::insertInstrumentation(
BLInstrumentationDag& dag, Module &M) {
BLInstrumentationEdge* exitRootEdge =
(BLInstrumentationEdge*) dag.getExitRootEdge();
insertInstrumentationStartingAt(exitRootEdge, &dag);
BLEdgeVector callEdges = dag.getCallPhonyEdges();
for( BLEdgeIterator edge = callEdges.begin(),
end = callEdges.end(); edge != end; edge++ ) {
BLInstrumentationNode* node =
(BLInstrumentationNode*)(*edge)->getSource();
BasicBlock::iterator insertPoint = node->getBlock()->getFirstInsertionPt();
while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call )
insertPoint++;
DEBUG(dbgs() << "\nInstrumenting method call block '"
<< node->getBlock()->getName() << "'\n");
DEBUG(dbgs() << " Path number initialized: "
<< ((node->getStartingPathNumber()) ? "yes" : "no") << "\n");
Value* newpn;
if( node->getStartingPathNumber() ) {
long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
if ( inc )
newpn = BinaryOperator::Create(Instruction::Add,
node->getStartingPathNumber(),
createIncrementConstant(inc,32),
"pathNumber", insertPoint);
else
newpn = node->getStartingPathNumber();
} else {
newpn = (Value*)createIncrementConstant(
((BLInstrumentationEdge*)(*edge))->getIncrement(), 32);
}
insertCounterIncrement(newpn, insertPoint, &dag);
insertCounterIncrement(newpn, node->getBlock()->getTerminator(),
&dag, false);
}
}
void PathProfiler::runOnFunction(std::vector<Constant*> &ftInit,
Function &F, Module &M) {
BLInstrumentationDag dag = BLInstrumentationDag(F);
dag.init();
dag.calculatePathNumbers();
dag.calculateSpanningTree();
dag.calculateChordIncrements();
dag.pushInitialization();
dag.pushCounters();
dag.unlinkPhony();
if (DotPathDag)
dag.generateDotGraph ();
if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) {
Type* t = ArrayType::get(Type::getInt32Ty(*Context),
dag.getNumberOfPaths());
dag.setCounterArray(new GlobalVariable(M, t, false,
GlobalValue::InternalLinkage,
Constant::getNullValue(t), ""));
}
insertInstrumentation(dag, M);
unsigned type;
Type* voidPtr = TypeBuilder<types::i<8>*, true>::get(*Context);
if( dag.getNumberOfPaths() <= HASH_THRESHHOLD )
type = ProfilingArray;
else
type = ProfilingHash;
std::vector<Constant*> entryArray(3);
entryArray[0] = createIncrementConstant(type,32);
entryArray[1] = createIncrementConstant(dag.getNumberOfPaths(),32);
entryArray[2] = dag.getCounterArray() ?
ConstantExpr::getBitCast(dag.getCounterArray(), voidPtr) :
Constant::getNullValue(voidPtr);
StructType* at = ftEntryTypeBuilder::get(*Context);
ConstantStruct* functionEntry =
(ConstantStruct*)ConstantStruct::get(at, entryArray);
ftInit.push_back(functionEntry);
}
#define PRINT_MODULE dbgs() << \
"\n\n============= MODULE BEGIN ===============\n" << M << \
"\n============== MODULE END ================\n"
bool PathProfiler::runOnModule(Module &M) {
Context = &M.getContext();
DEBUG(dbgs()
<< "****************************************\n"
<< "****************************************\n"
<< "** **\n"
<< "** PATH PROFILING INSTRUMENTATION **\n"
<< "** **\n"
<< "****************************************\n"
<< "****************************************\n");
Function *Main = M.getFunction("main");
if (!Main)
Main = M.getFunction("MAIN__");
if (!Main) {
errs() << "WARNING: cannot insert path profiling into a module"
<< " with no main function!\n";
return false;
}
llvmIncrementHashFunction = M.getOrInsertFunction(
"llvm_increment_path_count",
Type::getVoidTy(*Context), Type::getInt32Ty(*Context), Type::getInt32Ty(*Context), NULL );
llvmDecrementHashFunction = M.getOrInsertFunction(
"llvm_decrement_path_count",
Type::getVoidTy(*Context), Type::getInt32Ty(*Context), Type::getInt32Ty(*Context), NULL );
std::vector<Constant*> ftInit;
unsigned functionNumber = 0;
for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) {
if (F->isDeclaration())
continue;
DEBUG(dbgs() << "Function: " << F->getName() << "\n");
functionNumber++;
currentFunctionNumber = functionNumber;
runOnFunction(ftInit, *F, M);
}
Type *t = ftEntryTypeBuilder::get(*Context);
ArrayType* ftArrayType = ArrayType::get(t, ftInit.size());
Constant* ftInitConstant = ConstantArray::get(ftArrayType, ftInit);
DEBUG(dbgs() << " ftArrayType:" << *ftArrayType << "\n");
GlobalVariable* functionTable =
new GlobalVariable(M, ftArrayType, false, GlobalValue::InternalLinkage,
ftInitConstant, "functionPathTable");
Type *eltType = ftArrayType->getTypeAtIndex((unsigned)0);
InsertProfilingInitCall(Main, "llvm_start_path_profiling", functionTable,
PointerType::getUnqual(eltType));
DEBUG(PRINT_MODULE);
return true;
}
bool PathProfiler::splitCritical(BLInstrumentationEdge* edge,
BLInstrumentationDag* dag) {
unsigned succNum = edge->getSuccessorNumber();
BallLarusNode* sourceNode = edge->getSource();
BallLarusNode* targetNode = edge->getTarget();
BasicBlock* sourceBlock = sourceNode->getBlock();
BasicBlock* targetBlock = targetNode->getBlock();
if(sourceBlock == NULL || targetBlock == NULL
|| sourceNode->getNumberSuccEdges() <= 1
|| targetNode->getNumberPredEdges() == 1 ) {
return(false);
}
TerminatorInst* terminator = sourceBlock->getTerminator();
if( SplitCriticalEdge(terminator, succNum, this, false)) {
BasicBlock* newBlock = terminator->getSuccessor(succNum);
dag->splitUpdate(edge, newBlock);
return(true);
} else
return(false);
}