#include "llvm/Support/InstVisitor.h"
#include "llvm/Target/TargetData.h"
#include "Support/Statistic.h"
+#include "Support/Timer.h"
+#include "Support/CommandLine.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
//===--------------------------------------------------------------------===//
///
class GraphBuilder : InstVisitor<GraphBuilder> {
DSGraph &G;
- vector<DSNode*> &Nodes;
+ std::vector<DSNode*> &Nodes;
DSNodeHandle &RetNode; // Node that gets returned...
- map<Value*, DSNodeHandle> &ScalarMap;
- vector<DSCallSite> &FunctionCalls;
+ hash_map<Value*, DSNodeHandle> &ScalarMap;
+ std::vector<DSCallSite> &FunctionCalls;
public:
- GraphBuilder(DSGraph &g, vector<DSNode*> &nodes, DSNodeHandle &retNode,
- map<Value*, DSNodeHandle> &SM,
- vector<DSCallSite> &fc)
+ GraphBuilder(DSGraph &g, std::vector<DSNode*> &nodes, DSNodeHandle &retNode,
+ hash_map<Value*, DSNodeHandle> &SM,
+ std::vector<DSCallSite> &fc)
: G(g), Nodes(nodes), RetNode(retNode), ScalarMap(SM), FunctionCalls(fc) {
// Create scalar nodes for all pointer arguments...
void visitStoreInst(StoreInst &SI);
void visitCallInst(CallInst &CI);
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);
private:
// Helper functions used to implement the visitation functions...
/// 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 *N = new DSNode(NodeType, Ty, &G); // Create the node
+ if (DisableFieldSensitivity)
+ N->foldNodeCompletely();
return N;
}
PrintAuxCalls = false;
// Use the graph builder to construct the local version of the graph
GraphBuilder B(*this, Nodes, RetNode, ScalarMap, FunctionCalls);
- markIncompleteNodes();
+#ifndef NDEBUG
+ Timer::addPeakMemoryMeasurement();
+#endif
+
+ // Remove all integral constants from the scalarmap!
+ for (hash_map<Value*, DSNodeHandle>::iterator I = ScalarMap.begin();
+ I != ScalarMap.end();)
+ if (isa<ConstantIntegral>(I->first)) {
+ hash_map<Value*, DSNodeHandle>::iterator J = I++;
+ ScalarMap.erase(J);
+ } else
+ ++I;
+
+ markIncompleteNodes(DSGraph::MarkFormalArgs);
// Remove any nodes made dead due to merging...
- removeDeadNodes();
+ 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);
+ hash_map<Value*, DSNodeHandle>::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(DSNode::UnknownNode);
}
+ 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(DSNode::UnknownNode);
} 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)) {
Ptr.getNode()->NodeType |= DSNode::Read;
// 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...
+ // Mark that the node is written to...
Dest.getNode()->NodeType |= DSNode::Modified;
// Ensure a typerecord exists...
if (isPointerType(CI.getType()))
RetVal = getValueDest(CI);
- DSNodeHandle Callee = getValueDest(*CI.getOperand(0));
+ DSNode *Callee = 0;
+ if (DisableDirectCallOpt || !isa<Function>(CI.getOperand(0)))
+ Callee = getValueDest(*CI.getOperand(0)).getNode();
std::vector<DSNodeHandle> Args;
Args.reserve(CI.getNumOperands()-1);
Args.push_back(getValueDest(*CI.getOperand(i)));
// Add a new function call entry...
- FunctionCalls.push_back(DSCallSite(CI, RetVal, Callee, Args));
+ if (Callee)
+ FunctionCalls.push_back(DSCallSite(CI, RetVal, Callee, Args));
+ else
+ FunctionCalls.push_back(DSCallSite(CI, RetVal,
+ cast<Function>(CI.getOperand(0)), Args));
+}
+
+void GraphBuilder::visitFreeInst(FreeInst &FI) {
+ // Mark that the node is written to...
+ getValueDest(*FI.getOperand(0)).getNode()->NodeType
+ |= DSNode::Modified | DSNode::HeapNode;
}
/// Handle casts...
}
+// 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()->NodeType |= DSNode::UnknownNode;
+}
+
//===----------------------------------------------------------------------===//
// our memory... here...
//
void LocalDataStructures::releaseMemory() {
- for (std::map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
+ for (hash_map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
E = DSInfo.end(); I != E; ++I)
delete I->second;
projects / oota-llvm.git / blobdiff