Checkin some major reworks of data structure analysis. This is not done,
nor does it work very well, but I need to get it checked in before I break
the tree unintentionally.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3996 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp
index e561aca..5098251 100644
--- a/lib/Analysis/DataStructure/Local.cpp
+++ b/lib/Analysis/DataStructure/Local.cpp
@@ -1,4 +1,4 @@
-//===- ComputeLocal.cpp - Compute a local data structure graph for a fn ---===//
+//===- Local.cpp - Compute a local data structure graph for a function ----===//
//
// Compute the local version of the data structure graph for a function. The
// external interface to this file is the DSGraph constructor.
@@ -6,30 +6,55 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DataStructure.h"
-#include "llvm/Function.h"
#include "llvm/iMemory.h"
#include "llvm/iTerminators.h"
#include "llvm/iPHINode.h"
#include "llvm/iOther.h"
#include "llvm/Constants.h"
-#include "llvm/GlobalVariable.h"
#include "llvm/DerivedTypes.h"
+#include "llvm/Function.h"
+#include "llvm/GlobalVariable.h"
#include "llvm/Support/InstVisitor.h"
+#include "llvm/Target/TargetData.h"
+#include "Support/Statistic.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");
-//===----------------------------------------------------------------------===//
-// GraphBuilder Class
-//===----------------------------------------------------------------------===//
-//
-// This class is the builder class that constructs the local data structure
-// graph by performing a single pass over the function in question.
-//
+using namespace DataStructureAnalysis;
+
+namespace DataStructureAnalysis {
+ // FIXME: Do something smarter with target data!
+ TargetData TD("temp-td");
+ unsigned PointerSize(TD.getPointerSize());
+
+ // isPointerType - Return true if this type is big enough to hold a pointer.
+ bool isPointerType(const Type *Ty) {
+ if (isa<PointerType>(Ty))
+ return true;
+ else if (Ty->isPrimitiveType() && Ty->isInteger())
+ return Ty->getPrimitiveSize() >= PointerSize;
+ return false;
+ }
+}
+
namespace {
+ //===--------------------------------------------------------------------===//
+ // GraphBuilder Class
+ //===--------------------------------------------------------------------===//
+ //
+ /// This class is the builder class that constructs the local data structure
+ /// graph by performing a single pass over the function in question.
+ ///
class GraphBuilder : InstVisitor<GraphBuilder> {
DSGraph &G;
vector<DSNode*> &Nodes;
@@ -46,8 +71,8 @@
// Create scalar nodes for all pointer arguments...
for (Function::aiterator I = G.getFunction().abegin(),
E = G.getFunction().aend(); I != E; ++I)
- if (isa<PointerType>(I->getType()))
- getValueNode(*I);
+ if (isPointerType(I->getType()))
+ getValueDest(*I);
visit(G.getFunction()); // Single pass over the function
@@ -71,51 +96,51 @@
void visitCallInst(CallInst &CI);
void visitSetCondInst(SetCondInst &SCI) {} // SetEQ & friends are ignored
void visitFreeInst(FreeInst &FI) {} // Ignore free instructions
- void visitInstruction(Instruction &I); // Visit unsafe ptr instruction
+ void visitCastInst(CastInst &CI);
+ void visitInstruction(Instruction &I) {}
private:
// Helper functions used to implement the visitation functions...
- // createNode - Create a new DSNode, ensuring that it is properly added to
- // the graph.
- //
+ /// createNode - Create a new DSNode, ensuring that it is properly added to
+ /// the graph.
+ ///
DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty);
- // getValueNode - Return a DSNode that corresponds the the specified LLVM
- // value. This either returns the already existing node, or creates a new
- // one and adds it to the graph, if none exists.
- //
- DSNode *getValueNode(Value &V);
+ /// getValueNode - Return a DSNode that corresponds the the specified LLVM
+ /// value. This either returns the already existing node, or creates a new
+ /// one and adds it to the graph, if none exists.
+ ///
+ DSNodeHandle getValueNode(Value &V);
- // getGlobalNode - Just like getValueNode, except the global node itself is
- // returned, not a scalar node pointing to a global.
- //
- DSNode *getGlobalNode(GlobalValue &V);
+ /// getValueDest - Return the DSNode that the actual value points to. This
+ /// is basically the same thing as: getLink(getValueNode(V), 0)
+ ///
+ DSNodeHandle &getValueDest(Value &V);
- // getLink - This method is used to either return the specified link in the
- // specified node if one exists. If a link does not already exist (it's
- // null), then we create a new node, link it, then return it.
- //
- DSNode *getLink(DSNode *Node, unsigned Link);
+ /// getGlobalNode - Just like getValueNode, except the global node itself is
+ /// returned, not a scalar node pointing to a global.
+ ///
+ DSNodeHandle &getGlobalNode(GlobalValue &V);
- // getSubscriptedNode - Perform the basic getelementptr functionality that
- // must be factored out of gep, load and store while they are all MAI's.
- //
- DSNode *getSubscriptedNode(GetElementPtrInst &GEP, DSNode *Ptr);
+ /// getLink - This method is used to return the specified link in the
+ /// specified node if one exists. If a link does not already exist (it's
+ /// null), then we create a new node, link it, then return it. We must
+ /// specify the type of the Node field we are accessing so that we know what
+ /// type should be linked to if we need to create a new node.
+ ///
+ DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link,
+ const Type *FieldTy);
};
}
//===----------------------------------------------------------------------===//
// DSGraph constructor - Simply use the GraphBuilder to construct the local
// graph.
-DSGraph::DSGraph(Function &F, GlobalDSGraph* GlobalsG)
- : Func(F), RetNode(0), GlobalsGraph(GlobalsG) {
- if (GlobalsGraph != this) {
- GlobalsGraph->addReference(this);
- // Use the graph builder to construct the local version of the graph
- GraphBuilder B(*this, Nodes, RetNode, ValueMap, FunctionCalls);
- markIncompleteNodes();
- }
+DSGraph::DSGraph(Function &F) : Func(&F) {
+ // Use the graph builder to construct the local version of the graph
+ GraphBuilder B(*this, Nodes, RetNode, ValueMap, FunctionCalls);
+ markIncompleteNodes();
}
@@ -137,9 +162,9 @@
// getGlobalNode - Just like getValueNode, except the global node itself is
// returned, not a scalar node pointing to a global.
//
-DSNode *GraphBuilder::getGlobalNode(GlobalValue &V) {
+DSNodeHandle &GraphBuilder::getGlobalNode(GlobalValue &V) {
DSNodeHandle &NH = ValueMap[&V];
- if (NH) return NH; // Already have a node? Just return it...
+ if (NH.getNode()) return NH; // Already have a node? Just return it...
// Create a new global node for this global variable...
DSNode *G = createNode(DSNode::GlobalNode, V.getType()->getElementType());
@@ -149,8 +174,8 @@
// each use. For functions and other global variables, this is unneccesary,
// so avoid excessive merging by cloning these nodes on demand.
//
- NH = G;
- return G;
+ NH.setNode(G);
+ return NH;
}
@@ -158,126 +183,145 @@
// This either returns the already existing node, or creates a new one and adds
// it to the graph, if none exists.
//
-DSNode *GraphBuilder::getValueNode(Value &V) {
- assert(isa<PointerType>(V.getType()) && "Should only use pointer scalars!");
- if (!isa<GlobalValue>(V)) {
- DSNodeHandle &NH = ValueMap[&V];
- if (NH) return NH; // Already have a node? Just return it...
- }
+DSNodeHandle GraphBuilder::getValueNode(Value &V) {
+ assert(isPointerType(V.getType()) && "Should only use pointer scalars!");
+ // Do not share the pointer value to globals... this would cause way too much
+ // false merging.
+ //
+ DSNodeHandle &NH = ValueMap[&V];
+ if (!isa<GlobalValue>(V) && NH.getNode())
+ return NH; // Already have a node? Just return it...
// Otherwise we need to create a new scalar node...
DSNode *N = createNode(DSNode::ScalarNode, V.getType());
// If this is a global value, create the global pointed to.
if (GlobalValue *GV = dyn_cast<GlobalValue>(&V)) {
- DSNode *G = getGlobalNode(*GV);
- N->addEdgeTo(G);
+ N->addEdgeTo(0, getGlobalNode(*GV));
+ return DSNodeHandle(N, 0);
} else {
- ValueMap[&V] = N;
+ NH.setOffset(0);
+ NH.setNode(N);
}
- return N;
+ return NH;
+}
+
+/// getValueDest - Return the DSNode that the actual value points to. This
+/// is basically the same thing as: getLink(getValueNode(V), 0)
+///
+DSNodeHandle &GraphBuilder::getValueDest(Value &V) {
+ return getLink(getValueNode(V), 0, V.getType());
}
-// getLink - This method is used to either return the specified link in the
-// specified node if one exists. If a link does not already exist (it's
-// null), then we create a new node, link it, then return it.
-//
-DSNode *GraphBuilder::getLink(DSNode *Node, unsigned Link) {
- assert(Link < Node->getNumLinks() && "Link accessed out of range!");
- if (Node->getLink(Link) == 0) {
- DSNode::NodeTy NT;
- const Type *Ty;
- switch (Node->getType()->getPrimitiveID()) {
- case Type::PointerTyID:
- Ty = cast<PointerType>(Node->getType())->getElementType();
- NT = DSNode::ShadowNode;
- break;
- case Type::ArrayTyID:
- Ty = cast<ArrayType>(Node->getType())->getElementType();
- NT = DSNode::SubElement;
- break;
- case Type::StructTyID:
- Ty = cast<StructType>(Node->getType())->getContainedType(Link);
- NT = DSNode::SubElement;
- break;
- default:
- assert(0 && "Unexpected type to dereference!");
- abort();
- }
+/// getLink - This method is used to return the specified link in the
+/// specified node if one exists. If a link does not already exist (it's
+/// null), then we create a new node, link it, then return it. We must
+/// specify the type of the Node field we are accessing so that we know what
+/// type should be linked to if we need to create a new node.
+///
+DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node,
+ unsigned LinkNo, const Type *FieldTy) {
+ DSNodeHandle &Node = const_cast<DSNodeHandle&>(node);
- DSNode *New = createNode(NT, Ty);
- Node->addEdgeTo(Link, New);
- }
+ DSNodeHandle *Link = Node.getLink(LinkNo);
+ if (Link) return *Link;
+
+ // If the link hasn't been created yet, make and return a new shadow node of
+ // the appropriate type for FieldTy...
+ //
- return Node->getLink(Link);
+ // If we are indexing with a typed pointer, then the thing we are pointing
+ // to is of the pointed type. If we are pointing to it with an integer
+ // (because of cast to an integer), we represent it with a void type.
+ //
+ const Type *ReqTy;
+ if (const PointerType *Ptr = dyn_cast<PointerType>(FieldTy))
+ ReqTy = Ptr->getElementType();
+ else
+ ReqTy = Type::VoidTy;
+
+ DSNode *N = createNode(DSNode::ShadowNode, ReqTy);
+ Node.setLink(LinkNo, N);
+ return *Node.getLink(LinkNo);
}
-// getSubscriptedNode - Perform the basic getelementptr functionality that must
-// be factored out of gep, load and store while they are all MAI's.
-//
-DSNode *GraphBuilder::getSubscriptedNode(GetElementPtrInst &GEP, DSNode *Ptr) {
- for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i)
- if (GEP.getOperand(i)->getType() == Type::UIntTy)
- Ptr = getLink(Ptr, 0);
- else if (GEP.getOperand(i)->getType() == Type::UByteTy)
- Ptr = getLink(Ptr, cast<ConstantUInt>(GEP.getOperand(i))->getValue());
-
- if (GEP.getNumOperands() == 1)
- Ptr = getLink(Ptr, 0); // All GEP's have an implicit 0 if nothing else.
-
- return Ptr;
-}
//===----------------------------------------------------------------------===//
// Specific instruction type handler implementations...
//
-// Alloca & Malloc instruction implementation - Simply create a new memory
-// object, pointing the scalar to it.
-//
+/// Alloca & Malloc instruction implementation - Simply create a new memory
+/// object, pointing the scalar to it.
+///
void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) {
- DSNode *Scalar = getValueNode(AI);
DSNode *New = createNode(NodeType, AI.getAllocatedType());
- Scalar->addEdgeTo(New); // Make the scalar point to the new node...
+
+ // Make the scalar point to the new node...
+ getValueNode(AI).addEdgeTo(New);
}
// PHINode - Make the scalar for the PHI node point to all of the things the
// incoming values point to... which effectively causes them to be merged.
//
void GraphBuilder::visitPHINode(PHINode &PN) {
- if (!isa<PointerType>(PN.getType())) return; // Only pointer PHIs
+ if (!isPointerType(PN.getType())) return; // Only pointer PHIs
- DSNode *Scalar = getValueNode(PN);
- DSNode *ScalarDest = getLink(Scalar, 0);
+ DSNodeHandle &ScalarDest = getValueDest(PN);
for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
- ScalarDest->mergeWith(getLink(getValueNode(*PN.getIncomingValue(i)), 0));
+ if (!isa<ConstantPointerNull>(PN.getIncomingValue(i)))
+ ScalarDest.mergeWith(getValueDest(*PN.getIncomingValue(i)));
}
void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) {
- DSNode *Ptr = getSubscriptedNode(GEP, getValueNode(*GEP.getOperand(0)));
- getValueNode(GEP)->addEdgeTo(Ptr);
+ DSNodeHandle Value = getValueDest(*GEP.getOperand(0));
+
+ unsigned Offset = 0;
+ const Type *CurTy = GEP.getOperand(0)->getType();
+
+ for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i)
+ if (GEP.getOperand(i)->getType() == Type::LongTy) {
+ if (GEP.getOperand(i) != Constant::getNullValue(Type::LongTy)) {
+ std::cerr << "Array indexing not handled yet!\n";
+ }
+ CurTy = cast<SequentialType>(CurTy)->getElementType();
+ } else if (GEP.getOperand(i)->getType() == Type::UByteTy) {
+ unsigned FieldNo = cast<ConstantUInt>(GEP.getOperand(i))->getValue();
+ const StructType *STy = cast<StructType>(CurTy);
+ Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo];
+ CurTy = STy->getContainedType(FieldNo);
+ }
+
+ // Add in the offset calculated...
+ Value.setOffset(Value.getOffset()+Offset);
+
+ // Value is now the pointer we want to GEP to be...
+ getValueNode(GEP).addEdgeTo(Value);
}
void GraphBuilder::visitLoadInst(LoadInst &LI) {
- DSNode *Ptr = getValueNode(*LI.getOperand(0));
- if (!isa<PointerType>(LI.getType())) return; // only loads OF pointers
- getValueNode(LI)->addEdgeTo(getLink(Ptr, 0));
+ DSNodeHandle &Ptr = getValueDest(*LI.getOperand(0));
+ if (isPointerType(LI.getType()))
+ getValueNode(LI).addEdgeTo(getLink(Ptr, 0, LI.getType()));
}
void GraphBuilder::visitStoreInst(StoreInst &SI) {
- DSNode *DestPtr = getValueNode(*SI.getOperand(1));
- if (!isa<PointerType>(SI.getOperand(0)->getType())) return;
- DSNode *Value = getValueNode(*SI.getOperand(0));
- DestPtr->addEdgeTo(getLink(Value, 0));
+ DSNodeHandle &Dest = getValueDest(*SI.getOperand(1));
+
+ // Avoid adding edges from null, or processing non-"pointer" stores
+ if (isPointerType(SI.getOperand(0)->getType()) &&
+ !isa<ConstantPointerNull>(SI.getOperand(0))) {
+ Dest.addEdgeTo(getValueDest(*SI.getOperand(0)));
+ }
}
void GraphBuilder::visitReturnInst(ReturnInst &RI) {
- if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType())) {
- DSNode *Value = getLink(getValueNode(*RI.getOperand(0)), 0);
- Value->mergeWith(RetNode);
+ if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType()) &&
+ !isa<ConstantPointerNull>(RI.getOperand(0))) {
+ DSNodeHandle &Value = getValueDest(*RI.getOperand(0));
+ Value.mergeWith(RetNode);
RetNode = Value;
}
}
@@ -288,13 +332,13 @@
vector<DSNodeHandle> &Args = FunctionCalls.back();
// Set up the return value...
- if (isa<PointerType>(CI.getType()))
- Args.push_back(getLink(getValueNode(CI), 0));
+ if (isPointerType(CI.getType()))
+ Args.push_back(getLink(getValueNode(CI), 0, CI.getType()));
else
- Args.push_back(0);
+ Args.push_back(DSNodeHandle());
unsigned Start = 0;
- // Special case for direct call, avoid creating spurious scalar node...
+ // Special case for a direct call, avoid creating spurious scalar node...
if (GlobalValue *GV = dyn_cast<GlobalValue>(CI.getOperand(0))) {
Args.push_back(getGlobalNode(*GV));
Start = 1;
@@ -302,21 +346,43 @@
// Pass the arguments in...
for (unsigned i = Start, e = CI.getNumOperands(); i != e; ++i)
- if (isa<PointerType>(CI.getOperand(i)->getType()))
- Args.push_back(getLink(getValueNode(*CI.getOperand(i)), 0));
+ if (isPointerType(CI.getOperand(i)->getType()))
+ Args.push_back(getLink(getValueNode(*CI.getOperand(i)), 0,
+ CI.getOperand(i)->getType()));
}
-// visitInstruction - All safe instructions have been processed above, this case
-// is where unsafe ptr instructions land.
-//
-void GraphBuilder::visitInstruction(Instruction &I) {
- // If the return type is a pointer, mark the pointed node as being a cast node
- if (isa<PointerType>(I.getType()))
- getLink(getValueNode(I), 0)->NodeType |= DSNode::CastNode;
+/// Handle casts...
+void GraphBuilder::visitCastInst(CastInst &CI) {
+ if (isPointerType(CI.getType()) && isPointerType(CI.getOperand(0)->getType()))
+ getValueNode(CI).addEdgeTo(getLink(getValueNode(*CI.getOperand(0)), 0,
+ CI.getOperand(0)->getType()));
+}
- // If any operands are pointers, mark the pointed nodes as being a cast node
- for (Instruction::op_iterator i = I.op_begin(), E = I.op_end(); i!=E; ++i)
- if (isa<PointerType>(i->get()->getType()))
- getLink(getValueNode(*i->get()), 0)->NodeType |= DSNode::CastNode;
+
+
+
+//===----------------------------------------------------------------------===//
+// LocalDataStructures Implementation
+//===----------------------------------------------------------------------===//
+
+// releaseMemory - If the pass pipeline is done with this pass, we can release
+// 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;
+
+ // Empty map so next time memory is released, data structures are not
+ // re-deleted.
+ DSInfo.clear();
+}
+
+bool LocalDataStructures::run(Module &M) {
+ // Calculate all of the graphs...
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+ if (!I->isExternal())
+ DSInfo.insert(std::make_pair(I, new DSGraph(*I)));
+ return false;
}