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

1 files changed, 208 insertions, 142 deletions

diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp
index e561aca210..509825172e 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 @@ namespace {
       // 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 @@ namespace {
     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);
-
-    // getGlobalNode - Just like getValueNode, except the global node itself is
-    // returned, not a scalar node pointing to a global.
-    //
-    DSNode *getGlobalNode(GlobalValue &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);
-
-    // 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);
+    /// 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);
+
+    /// 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);
+
+    /// getGlobalNode - Just like getValueNode, except the global node itself is
+    /// returned, not a scalar node pointing to a global.
+    ///
+    DSNodeHandle &getGlobalNode(GlobalValue &V);
+
+    /// 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 @@ DSNode *GraphBuilder::createNode(DSNode::NodeTy NodeType, const Type *Ty) {
 // 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 @@ DSNode *GraphBuilder::getGlobalNode(GlobalValue &V) {
   // 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 @@ DSNode *GraphBuilder::getGlobalNode(GlobalValue &V) {
 // 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();
-    }
-
-    DSNode *New = createNode(NT, Ty);
-    Node->addEdgeTo(Link, New);
-  }
 
-  return Node->getLink(Link);
-}
 
-// 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());  
+/// 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);
 
-  if (GEP.getNumOperands() == 1)
-    Ptr = getLink(Ptr, 0);  // All GEP's have an implicit 0 if nothing else.
+  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 Ptr;
+  // 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);
 }
 
+
 //===----------------------------------------------------------------------===//
 // 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 @@ void GraphBuilder::visitCallInst(CallInst &CI) {
   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 @@ void GraphBuilder::visitCallInst(CallInst &CI) {
 
   // 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.
+/// 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()));
+}
+
+
+
+
+//===----------------------------------------------------------------------===//
+// LocalDataStructures Implementation
+//===----------------------------------------------------------------------===//
+
+// releaseMemory - If the pass pipeline is done with this pass, we can release
+// our memory... here...
 //
-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;
-
-  // 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;
+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;
 }