#include "llvm/Analysis/DataStructure.h"
#include "llvm/Analysis/DSGraph.h"
-#include "llvm/iMemory.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iOther.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
+#include "llvm/Instructions.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Target/TargetData.h"
-#include "Support/Statistic.h"
+#include "Support/CommandLine.h"
+#include "Support/Debug.h"
+#include "Support/Timer.h"
// FIXME: This should eventually be a FunctionPass that is automatically
// aggregated into a Pass.
//
#include "llvm/Module.h"
-using std::map;
-using std::vector;
-
static RegisterAnalysis<LocalDataStructures>
X("datastructure", "Local Data Structure Analysis");
namespace {
+ cl::opt<bool>
+ DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden,
+ cl::desc("Disable direct call optimization in "
+ "DSGraph construction"));
+ cl::opt<bool>
+ DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden,
+ cl::desc("Disable field sensitivity in DSGraphs"));
+
//===--------------------------------------------------------------------===//
// GraphBuilder Class
//===--------------------------------------------------------------------===//
/// graph by performing a single pass over the function in question.
///
class GraphBuilder : InstVisitor<GraphBuilder> {
+ Function &F;
DSGraph &G;
- vector<DSNode*> &Nodes;
DSNodeHandle &RetNode; // Node that gets returned...
- map<Value*, DSNodeHandle> &ScalarMap;
- vector<DSCallSite> &FunctionCalls;
+ DSGraph::ScalarMapTy &ScalarMap;
+ std::vector<DSCallSite> &FunctionCalls;
public:
- GraphBuilder(DSGraph &g, vector<DSNode*> &nodes, DSNodeHandle &retNode,
- map<Value*, DSNodeHandle> &SM,
- vector<DSCallSite> &fc)
- : G(g), Nodes(nodes), RetNode(retNode), ScalarMap(SM), FunctionCalls(fc) {
+ GraphBuilder(Function &f, DSGraph &g, DSNodeHandle &retNode,
+ DSGraph::ScalarMapTy &SM, std::vector<DSCallSite> &fc)
+ : F(f), G(g), RetNode(retNode), ScalarMap(SM),
+ FunctionCalls(fc) {
// Create scalar nodes for all pointer arguments...
- for (Function::aiterator I = G.getFunction().abegin(),
- E = G.getFunction().aend(); I != E; ++I)
+ for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
if (isPointerType(I->getType()))
getValueDest(*I);
- visit(G.getFunction()); // Single pass over the function
+ visit(F); // Single pass over the function
}
private:
// Visitor functions, used to handle each instruction type we encounter...
friend class InstVisitor<GraphBuilder>;
- void visitMallocInst(MallocInst &MI) { handleAlloc(MI, DSNode::HeapNode); }
- void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, DSNode::AllocaNode);}
- void handleAlloc(AllocationInst &AI, DSNode::NodeTy NT);
+ void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); }
+ void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); }
+ void handleAlloc(AllocationInst &AI, bool isHeap);
void visitPHINode(PHINode &PN);
void visitLoadInst(LoadInst &LI);
void visitStoreInst(StoreInst &SI);
void visitCallInst(CallInst &CI);
+ void visitInvokeInst(InvokeInst &II);
void visitSetCondInst(SetCondInst &SCI) {} // SetEQ & friends are ignored
- void visitFreeInst(FreeInst &FI) {} // Ignore free instructions
+ void visitFreeInst(FreeInst &FI);
void visitCastInst(CastInst &CI);
- void visitInstruction(Instruction &I) {}
+ void visitInstruction(Instruction &I);
+ void visitCallSite(CallSite CS);
private:
// Helper functions used to implement the visitation functions...
/// createNode - Create a new DSNode, ensuring that it is properly added to
/// the graph.
///
- DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty = 0) {
- DSNode *N = new DSNode(NodeType, Ty); // Create the node
- Nodes.push_back(N); // Add node to nodes list
+ DSNode *createNode(const Type *Ty = 0) {
+ DSNode *N = new DSNode(Ty, &G); // Create the node
+ if (DisableFieldSensitivity) {
+ N->foldNodeCompletely();
+ if (DSNode *FN = N->getForwardNode())
+ N = FN;
+ }
return N;
}
//===----------------------------------------------------------------------===//
// DSGraph constructor - Simply use the GraphBuilder to construct the local
// graph.
-DSGraph::DSGraph(Function &F, DSGraph *GG) : Func(&F), GlobalsGraph(GG) {
+DSGraph::DSGraph(Function &F, DSGraph *GG) : GlobalsGraph(GG) {
+ PrintAuxCalls = false;
+
+ DEBUG(std::cerr << " [Loc] Calculating graph for: " << F.getName() << "\n");
+
// Use the graph builder to construct the local version of the graph
- GraphBuilder B(*this, Nodes, RetNode, ScalarMap, FunctionCalls);
- markIncompleteNodes();
+ GraphBuilder B(F, *this, ReturnNodes[&F], ScalarMap, FunctionCalls);
+#ifndef NDEBUG
+ Timer::addPeakMemoryMeasurement();
+#endif
+
+ // Remove all integral constants from the scalarmap!
+ for (ScalarMapTy::iterator I = ScalarMap.begin(); I != ScalarMap.end();)
+ if (isa<ConstantIntegral>(I->first)) {
+ ScalarMapTy::iterator J = I++;
+ ScalarMap.erase(J);
+ } else
+ ++I;
+
+ markIncompleteNodes(DSGraph::MarkFormalArgs);
// Remove any nodes made dead due to merging...
- removeDeadNodes(true);
+ removeDeadNodes(DSGraph::KeepUnreachableGlobals);
}
// Helper method implementations...
//
-
/// getValueDest - Return the DSNode that the actual value points to.
///
DSNodeHandle GraphBuilder::getValueDest(Value &Val) {
if (V == Constant::getNullValue(V->getType()))
return 0; // Null doesn't point to anything, don't add to ScalarMap!
+ DSNodeHandle &NH = ScalarMap[V];
+ if (NH.getNode())
+ return NH; // Already have a node? Just return it...
+
+ // Otherwise we need to create a new node to point to.
+ // Check first for constant expressions that must be traversed to
+ // extract the actual value.
if (Constant *C = dyn_cast<Constant>(V))
if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
- return getValueDest(*CPR->getValue());
+ return NH = getValueDest(*CPR->getValue());
} else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
if (CE->getOpcode() == Instruction::Cast)
- return getValueDest(*CE->getOperand(0));
- if (CE->getOpcode() == Instruction::GetElementPtr) {
+ NH = getValueDest(*CE->getOperand(0));
+ else if (CE->getOpcode() == Instruction::GetElementPtr) {
visitGetElementPtrInst(*CE);
- std::map<Value*, DSNodeHandle>::iterator I = ScalarMap.find(CE);
+ DSGraph::ScalarMapTy::iterator I = ScalarMap.find(CE);
assert(I != ScalarMap.end() && "GEP didn't get processed right?");
- DSNodeHandle NH = I->second;
- ScalarMap.erase(I); // Remove constant from scalarmap
- return NH;
+ NH = I->second;
+ } else {
+ // This returns a conservative unknown node for any unhandled ConstExpr
+ return NH = createNode()->setUnknownNodeMarker();
+ }
+ if (NH.getNode() == 0) { // (getelementptr null, X) returns null
+ ScalarMap.erase(V);
+ return 0;
}
+ return NH;
- // This returns a conservative unknown node for any unhandled ConstExpr
- return createNode(DSNode::UnknownNode);
} else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(C)) {
// Random constants are unknown mem
- return createNode(DSNode::UnknownNode);
+ return NH = createNode()->setUnknownNodeMarker();
} else {
assert(0 && "Unknown constant type!");
}
- DSNodeHandle &NH = ScalarMap[V];
- if (NH.getNode())
- return NH; // Already have a node? Just return it...
-
// Otherwise we need to create a new node to point to...
DSNode *N;
if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
// Create a new global node for this global variable...
- N = createNode(DSNode::GlobalNode, GV->getType()->getElementType());
+ N = createNode(GV->getType()->getElementType());
N->addGlobal(GV);
} else {
// Otherwise just create a shadow node
- N = createNode(DSNode::ShadowNode);
+ N = createNode();
}
NH.setNode(N); // Remember that we are pointing to it...
DSNodeHandle &Link = Node.getLink(LinkNo);
if (!Link.getNode()) {
// If the link hasn't been created yet, make and return a new shadow node
- Link = createNode(DSNode::ShadowNode);
+ Link = createNode();
}
return Link;
}
/// Alloca & Malloc instruction implementation - Simply create a new memory
/// object, pointing the scalar to it.
///
-void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) {
- setDestTo(AI, createNode(NodeType));
+void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) {
+ DSNode *N = createNode();
+ if (isHeap)
+ N->setHeapNodeMarker();
+ else
+ N->setAllocaNodeMarker();
+ setDestTo(AI, N);
}
// PHINode - Make the scalar for the PHI node point to all of the things the
unsigned RawOffset = Offset+Value.getOffset();
// Loop over all of the elements of the array, merging them into the
- // zero'th element.
+ // zeroth element.
for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i)
// Merge all of the byte components of this array element
for (unsigned j = 0; j != ElSize; ++j)
if (Ptr.getNode() == 0) return;
// Make that the node is read from...
- Ptr.getNode()->NodeType |= DSNode::Read;
+ Ptr.getNode()->setReadMarker();
// Ensure a typerecord exists...
- Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset());
+ Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false);
if (isPointerType(LI.getType()))
setDestTo(LI, getLink(Ptr));
DSNodeHandle Dest = getValueDest(*SI.getOperand(1));
if (Dest.getNode() == 0) return;
- // Make that the node is written to...
- Dest.getNode()->NodeType |= DSNode::Modified;
+ // Mark that the node is written to...
+ Dest.getNode()->setModifiedMarker();
// Ensure a typerecord exists...
Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset());
}
void GraphBuilder::visitCallInst(CallInst &CI) {
+ visitCallSite(&CI);
+}
+
+void GraphBuilder::visitInvokeInst(InvokeInst &II) {
+ visitCallSite(&II);
+}
+
+void GraphBuilder::visitCallSite(CallSite CS) {
+ // Special case handling of certain libc allocation functions here.
+ if (Function *F = CS.getCalledFunction())
+ if (F->isExternal())
+ if (F->getName() == "calloc") {
+ setDestTo(*CS.getInstruction(),
+ createNode()->setHeapNodeMarker()->setModifiedMarker());
+ return;
+ } else if (F->getName() == "realloc") {
+ DSNodeHandle RetNH = getValueDest(*CS.getInstruction());
+ RetNH.mergeWith(getValueDest(**CS.arg_begin()));
+ DSNode *N = RetNH.getNode();
+ if (N) N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker();
+ return;
+ }
+
+
// Set up the return value...
DSNodeHandle RetVal;
- if (isPointerType(CI.getType()))
- RetVal = getValueDest(CI);
+ Instruction *I = CS.getInstruction();
+ if (isPointerType(I->getType()))
+ RetVal = getValueDest(*I);
- DSNodeHandle Callee = getValueDest(*CI.getOperand(0));
+ DSNode *Callee = 0;
+ if (DisableDirectCallOpt || !isa<Function>(CS.getCalledValue()))
+ Callee = getValueDest(*CS.getCalledValue()).getNode();
std::vector<DSNodeHandle> Args;
- Args.reserve(CI.getNumOperands()-1);
+ Args.reserve(CS.arg_end()-CS.arg_begin());
// Calculate the arguments vector...
- for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
- if (isPointerType(CI.getOperand(i)->getType()))
- Args.push_back(getValueDest(*CI.getOperand(i)));
+ for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
+ if (isPointerType((*I)->getType()))
+ Args.push_back(getValueDest(**I));
// Add a new function call entry...
- FunctionCalls.push_back(DSCallSite(CI, RetVal, Callee, Args));
+ if (Callee)
+ FunctionCalls.push_back(DSCallSite(CS, RetVal, Callee, Args));
+ else
+ FunctionCalls.push_back(DSCallSite(CS, RetVal, CS.getCalledFunction(),
+ Args));
+}
+
+void GraphBuilder::visitFreeInst(FreeInst &FI) {
+ // Mark that the node is written to...
+ DSNode *N = getValueDest(*FI.getOperand(0)).getNode();
+ N->setModifiedMarker();
+ N->setHeapNodeMarker();
}
/// Handle casts...
// to track the fact that the node points to SOMETHING, just something we
// don't know about. Make an "Unknown" node.
//
- setDestTo(CI, createNode(DSNode::UnknownNode));
+ setDestTo(CI, createNode()->setUnknownNodeMarker());
}
}
+// visitInstruction - For all other instruction types, if we have any arguments
+// that are of pointer type, make them have unknown composition bits, and merge
+// the nodes together.
+void GraphBuilder::visitInstruction(Instruction &Inst) {
+ DSNodeHandle CurNode;
+ if (isPointerType(Inst.getType()))
+ CurNode = getValueDest(Inst);
+ for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I)
+ if (isPointerType((*I)->getType()))
+ CurNode.mergeWith(getValueDest(**I));
+
+ if (CurNode.getNode())
+ CurNode.getNode()->setUnknownNodeMarker();
+}
+
//===----------------------------------------------------------------------===//
// our memory... here...
//
void LocalDataStructures::releaseMemory() {
- for (std::map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
- E = DSInfo.end(); I != E; ++I)
- delete I->second;
+ for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
+ E = DSInfo.end(); I != E; ++I) {
+ I->second->getReturnNodes().erase(I->first);
+ if (I->second->getReturnNodes().empty())
+ delete I->second;
+ }
// Empty map so next time memory is released, data structures are not
// re-deleted.
projects / oota-llvm.git / blobdiff