Reimplement data structure analysis

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2868 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 0 insertions, 1601 deletions

diff --git a/lib/Analysis/DataStructure/ComputeClosure.cpp b/lib/Analysis/DataStructure/ComputeClosure.cpp
deleted file mode 100644
index 0f94b9141c..0000000000
--- a/lib/Analysis/DataStructure/ComputeClosure.cpp
+++ /dev/null
@@ -1,258 +0,0 @@
-//===- ComputeClosure.cpp - Implement interprocedural closing of graphs ---===//
-//
-// Compute the interprocedural closure of a data structure graph
-//
-//===----------------------------------------------------------------------===//
-
-// DEBUG_IP_CLOSURE - Define this to debug the act of linking up graphs
-//#define DEBUG_IP_CLOSURE 1
-
-#include "llvm/Analysis/DataStructure.h"
-#include "llvm/Function.h"
-#include "llvm/iOther.h"
-#include "Support/STLExtras.h"
-#include <algorithm>
-using std::cerr;
-
-// Make all of the pointers that point to Val also point to N.
-//
-static void copyEdgesFromTo(PointerVal Val, DSNode *N) {
-  unsigned ValIdx = Val.Index;
-  unsigned NLinks = N->getNumLinks();
-
-  const std::vector<PointerValSet*> &PVSsToUpdate(Val.Node->getReferrers());
-  for (unsigned i = 0, e = PVSsToUpdate.size(); i != e; ++i) {
-    // Loop over all of the pointers pointing to Val...
-    PointerValSet &PVS = *PVSsToUpdate[i];
-    for (unsigned j = 0, je = PVS.size(); j != je; ++j) {
-      if (PVS[j].Node == Val.Node && PVS[j].Index >= ValIdx && 
-          PVS[j].Index < ValIdx+NLinks)
-        PVS.add(PointerVal(N, PVS[j].Index-ValIdx));
-    }
-  }
-}
-
-static void ResolveNodesTo(const PointerValSet &FromVals,
-                           const PointerValSet &ToVals) {
-  // Only resolve the first pointer, although there many be many pointers here.
-  // The problem is that the inlined function might return one of the arguments
-  // to the function, and if so, extra values can be added to the arg or call
-  // node that point to what the other one got resolved to.  Since these will
-  // be added to the end of the PVS pointed in, we just ignore them.
-  //
-  assert(!FromVals.empty() && "From should have at least a shadow node!");
-  const PointerVal &FromPtr = FromVals[0];
-
-  assert(FromPtr.Index == 0 &&
-         "Resolved node return pointer should be index 0!");
-  DSNode *N = FromPtr.Node;
-
-  // Make everything that pointed to the shadow node also point to the values in
-  // ToVals...
-  //
-  for (unsigned i = 0, e = ToVals.size(); i != e; ++i)
-    copyEdgesFromTo(ToVals[i], N);
-
-  // Make everything that pointed to the shadow node now also point to the
-  // values it is equivalent to...
-  const std::vector<PointerValSet*> &PVSToUpdate(N->getReferrers());
-  for (unsigned i = 0, e = PVSToUpdate.size(); i != e; ++i)
-    PVSToUpdate[i]->add(ToVals);
-}
-
-
-// ResolveNodeTo - The specified node is now known to point to the set of values
-// in ToVals, instead of the old shadow node subgraph that it was pointing to.
-//
-static void ResolveNodeTo(DSNode *Node, const PointerValSet &ToVals) {
-  assert(Node->getNumLinks() == 1 && "Resolved node can only be a scalar!!");
-
-  const PointerValSet &PVS = Node->getLink(0);
-  ResolveNodesTo(PVS, ToVals);
-}
-
-// isResolvableCallNode - Return true if node is a call node and it is a call
-// node that we can inline...
-//
-static bool isResolvableCallNode(CallDSNode *CN) {
-  // Only operate on call nodes with direct function calls
-  if (CN->getArgValues(0).size() == 1 &&
-      isa<GlobalDSNode>(CN->getArgValues(0)[0].Node)) {
-    GlobalDSNode *GDN = cast<GlobalDSNode>(CN->getArgValues(0)[0].Node);
-    Function *F = cast<Function>(GDN->getGlobal());
-
-    // Only work on call nodes with direct calls to methods with bodies.
-    return !F->isExternal();
-  }
-  return false;
-}
-
-#include "Support/CommandLine.h"
-static cl::Int InlineLimit("dsinlinelimit", "Max number of graphs to inline when computing ds closure", cl::Hidden, 100);
-
-// computeClosure - Replace all of the resolvable call nodes with the contents
-// of their corresponding method data structure graph...
-//
-void FunctionDSGraph::computeClosure(const DataStructure &DS) {
-  // Note that this cannot be a real vector because the keys will be changing
-  // as nodes are eliminated!
-  //
-  typedef std::pair<std::vector<PointerValSet>, CallInst *> CallDescriptor;
-  std::vector<std::pair<CallDescriptor, PointerValSet> > CallMap;
-
-  unsigned NumInlines = 0;
-
-  // Loop over the resolvable call nodes...
-  std::vector<CallDSNode*>::iterator NI;
-  NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
-  while (NI != CallNodes.end()) {
-    CallDSNode *CN = *NI;
-    GlobalDSNode *FGDN = cast<GlobalDSNode>(CN->getArgValues(0)[0].Node);
-    Function *F = cast<Function>(FGDN->getGlobal());
-
-    if ((int)NumInlines++ == InlineLimit) {      // CUTE hack huh?
-      cerr << "Infinite (?) recursion halted\n";
-      cerr << "Not inlining: " << F->getName() << "\n";
-      CN->dump();
-      return;
-    }
-
-    CallNodes.erase(NI);                 // Remove the call node from the graph
-
-    unsigned CallNodeOffset = NI-CallNodes.begin();
-
-    // Find out if we have already incorporated this node... if so, it will be
-    // in the CallMap...
-    //
-    
-#if 0
-    cerr << "\nSearching for: " << (void*)CN->getCall() << ": ";
-    for (unsigned X = 0; X != CN->getArgs().size(); ++X) {
-      cerr << " " << X << " is\n";
-      CN->getArgs().first[X].print(cerr);
-    }
-#endif
-
-    const std::vector<PointerValSet> &Args = CN->getArgs();
-    PointerValSet *CMI = 0;
-    for (unsigned i = 0, e = CallMap.size(); i != e; ++i) {
-#if 0
-      cerr << "Found: " << (void*)CallMap[i].first.second << ": ";
-      for (unsigned X = 0; X != CallMap[i].first.first.size(); ++X) {
-        cerr << " " << X << " is\n"; CallMap[i].first.first[X].print(cerr);
-      }
-#endif
-
-      // Look to see if the function call takes a superset of the values we are
-      // providing as input
-      // 
-      CallDescriptor &CD = CallMap[i].first;
-      if (CD.second == CN->getCall() && CD.first.size() == Args.size()) {
-        bool FoundMismatch = false;
-        for (unsigned j = 0, je = Args.size(); j != je; ++j) {
-          PointerValSet ArgSet = CD.first[j];
-          if (ArgSet.add(Args[j])) {
-            FoundMismatch = true; break;
-          }            
-        }
-
-        if (!FoundMismatch) { CMI = &CallMap[i].second; break; }
-      }
-    }
-
-    // Hold the set of values that correspond to the incorporated methods
-    // return set.
-    //
-    PointerValSet RetVals;
-
-    if (CMI) {
-      // We have already inlined an identical function call!
-      RetVals = *CMI;
-    } else {
-      // Get the datastructure graph for the new method.  Note that we are not
-      // allowed to modify this graph because it will be the cached graph that
-      // is returned by other users that want the local datastructure graph for
-      // a method.
-      //
-      const FunctionDSGraph &NewFunction = DS.getDSGraph(F);
-
-      // StartNode - The first node of the incorporated graph, last node of the
-      // preexisting data structure graph...
-      //
-      unsigned StartAllocNode = AllocNodes.size();
-
-      // Incorporate a copy of the called function graph into the current graph,
-      // allowing us to do local transformations to local graph to link
-      // arguments to call values, and call node to return value...
-      //
-      std::vector<PointerValSet> Args;
-      RetVals = cloneFunctionIntoSelf(NewFunction, false, Args);
-      CallMap.push_back(make_pair(CallDescriptor(CN->getArgs(), CN->getCall()),
-                                  RetVals));
-
-      // If the call node has arguments, process them now!
-      assert(Args.size() == CN->getNumArgs()-1 &&
-             "Call node doesn't match function?");
-
-      for (unsigned i = 0, e = Args.size(); i != e; ++i) {
-        // Now we make all of the nodes inside of the incorporated method
-        // point to the real arguments values, not to the shadow nodes for the
-        // argument.
-        ResolveNodesTo(Args[i], CN->getArgValues(i+1));
-      }
-
-      // Loop through the nodes, deleting alloca nodes in the inlined function.
-      // Since the memory has been released, we cannot access their pointer
-      // fields (with defined results at least), so it is not possible to use
-      // any pointers to the alloca.  Drop them now, and remove the alloca's
-      // since they are dead (we just removed all links to them).
-      //
-      for (unsigned i = StartAllocNode; i != AllocNodes.size(); ++i)
-        if (AllocNodes[i]->isAllocaNode()) {
-          AllocDSNode *NDS = AllocNodes[i];
-          NDS->removeAllIncomingEdges();          // These edges are invalid now
-          delete NDS;                             // Node is dead
-          AllocNodes.erase(AllocNodes.begin()+i); // Remove slot in Nodes array
-          --i;                                    // Don't skip the next node
-        }
-    }
-
-    // If the function returns a pointer value...  Resolve values pointing to
-    // the shadow nodes pointed to by CN to now point the values in RetVals...
-    //
-    if (CN->getNumLinks()) ResolveNodeTo(CN, RetVals);
-
-    // Now the call node is completely destructable.  Eliminate it now.
-    delete CN;
-
-    bool Changed = true;
-    while (Changed) {
-      // Eliminate shadow nodes that are not distinguishable from some other
-      // node in the graph...
-      //
-      Changed = UnlinkUndistinguishableNodes();
-
-      // Eliminate shadow nodes that are now extraneous due to linking...
-      Changed |= RemoveUnreachableNodes();
-    }
-
-    //if (F == Func) return;  // Only do one self inlining
-    
-    // Move on to the next call node...
-    NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
-  }
-
-  // Drop references to globals...
-  CallMap.clear();
-
-  bool Changed = true;
-  while (Changed) {
-    // Eliminate shadow nodes that are not distinguishable from some other
-    // node in the graph...
-    //
-    Changed = UnlinkUndistinguishableNodes();
-
-    // Eliminate shadow nodes that are now extraneous due to linking...
-    Changed |= RemoveUnreachableNodes();
-  }
-}
diff --git a/lib/Analysis/DataStructure/EliminateNodes.cpp b/lib/Analysis/DataStructure/EliminateNodes.cpp
deleted file mode 100644
index 7d8eb9b251..0000000000
--- a/lib/Analysis/DataStructure/EliminateNodes.cpp
+++ /dev/null
@@ -1,373 +0,0 @@
-//===- EliminateNodes.cpp - Prune unneccesary nodes in the graph ----------===//
-//
-// This file contains two node optimizations:
-//   1. UnlinkUndistinguishableNodes - Often, after unification, shadow
-//      nodes are left around that should not exist anymore.  An example is when
-//      a shadow gets unified with a 'new' node, the following graph gets
-//      generated:  %X -> Shadow, %X -> New.  Since all of the edges to the
-//      shadow node also all go to the New node, we can eliminate the shadow.
-//
-//   2. RemoveUnreachableNodes - Remove shadow and allocation nodes that are not
-//      reachable from some other node in the graph.  Unreachable nodes are left
-//      lying around often because a method only refers to some allocations with
-//      scalar values or an alloca, then when it is inlined, these references
-//      disappear and the nodes become homeless and prunable.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/DataStructureGraph.h"
-#include "llvm/Value.h"
-#include "Support/STLExtras.h"
-#include <algorithm>
-using std::vector;
-
-//#define DEBUG_NODE_ELIMINATE 1
-
-static void DestroyFirstNodeOfPair(DSNode *N1, DSNode *N2) {
-#ifdef DEBUG_NODE_ELIMINATE
-  std::cerr << "Found Indistinguishable Node:\n";
-  N1->print(std::cerr);
-#endif
-
-  // The nodes can be merged.  Make sure that N2 contains all of the
-  // outgoing edges (fields) that N1 does...
-  //
-  assert(N1->getNumLinks() == N2->getNumLinks() &&
-         "Same type, diff # fields?");
-  for (unsigned i = 0, e = N1->getNumLinks(); i != e; ++i)
-    N2->getLink(i).add(N1->getLink(i));
-  
-  // Now make sure that all of the nodes that point to N1 also point to the node
-  // that we are merging it with...
-  //
-  const vector<PointerValSet*> &Refs = N1->getReferrers();
-  for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
-    PointerValSet &PVS = *Refs[i];
-
-    bool RanOnce = false;
-    for (unsigned j = 0, je = PVS.size(); j != je; ++j)
-      if (PVS[j].Node == N1) {
-        RanOnce = true;
-        PVS.add(PointerVal(N2, PVS[j].Index));
-      }
-
-    assert(RanOnce && "Node on user set but cannot find the use!");
-  }
-
-  N1->mergeInto(N2);
-  N1->removeAllIncomingEdges();
-  delete N1;
-}
-
-// isIndistinguishableNode - A node is indistinguishable if some other node
-// has exactly the same incoming links to it and if the node considers itself
-// to be the same as the other node...
-//
-static bool isIndistinguishableNode(DSNode *DN) {
-  if (DN->getReferrers().empty()) {       // No referrers...
-    if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN)) {
-      delete DN;
-      return true;  // Node is trivially dead
-    } else
-      return false;
-  }
-  
-  // Pick a random referrer... Ptr is the things that the referrer points to.
-  // Since DN is in the Ptr set, look through the set seeing if there are any
-  // other nodes that are exactly equilivant to DN (with the exception of node
-  // type), but are not DN.  If anything exists, then DN is indistinguishable.
-  //
-
-  DSNode *IndFrom = 0;
-  const vector<PointerValSet*> &Refs = DN->getReferrers();
-  for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
-    const PointerValSet &Ptr = *Refs[R];
-
-    for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
-      DSNode *N2 = Ptr[i].Node;
-      if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
-          DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {
-
-        IndFrom = N2;
-        R = RE-1;
-        break;
-      }
-    }
-  }
-
-  // If we haven't found an equivalent node to merge with, see if one of the
-  // nodes pointed to by this node is equivalent to this one...
-  //
-  if (IndFrom == 0) {
-    unsigned NumOutgoing = DN->getNumOutgoingLinks();
-    for (DSNode::iterator I = DN->begin(), E = DN->end(); I != E; ++I) {
-      DSNode *Linked = *I;
-      if (Linked != DN && Linked->getNumOutgoingLinks() == NumOutgoing &&
-          DN->getType() == Linked->getType() && DN->isEquivalentTo(Linked)) {
-#if 0
-        // Make sure the leftover node contains links to everything we do...
-        for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
-          Linked->getLink(i).add(DN->getLink(i));
-#endif
-
-        IndFrom = Linked;
-        break;
-      }
-    }
-  }
-
-
-  // If DN is indistinguishable from some other node, merge them now...
-  if (IndFrom == 0)
-    return false;     // Otherwise, nothing found, perhaps next time....
-
-  DestroyFirstNodeOfPair(DN, IndFrom);
-  return true;
-}
-
-template<typename NodeTy>
-static bool removeIndistinguishableNodes(vector<NodeTy*> &Nodes) {
-  bool Changed = false;
-  vector<NodeTy*>::iterator I = Nodes.begin();
-  while (I != Nodes.end()) {
-    if (isIndistinguishableNode(*I)) {
-      I = Nodes.erase(I);
-      Changed = true;
-    } else {
-      ++I;
-    }
-  }
-  return Changed;
-}
-
-template<typename NodeTy>
-static bool removeIndistinguishableNodePairs(vector<NodeTy*> &Nodes) {
-  bool Changed = false;
-  vector<NodeTy*>::iterator I = Nodes.begin();
-  while (I != Nodes.end()) {
-    NodeTy *N1 = *I++;
-    for (vector<NodeTy*>::iterator I2 = I, I2E = Nodes.end();
-         I2 != I2E; ++I2) {
-      NodeTy *N2 = *I2;
-      if (N1->isEquivalentTo(N2)) {
-        DestroyFirstNodeOfPair(N1, N2);
-        --I;
-        I = Nodes.erase(I);
-        Changed = true;
-        break;
-      }
-    }
-  }
-  return Changed;
-}
-
-
-
-// UnlinkUndistinguishableNodes - Eliminate shadow nodes that are not
-// distinguishable from some other node in the graph...
-//
-bool FunctionDSGraph::UnlinkUndistinguishableNodes() {
-  // Loop over all of the shadow nodes, checking to see if they are
-  // indistinguishable from some other node.  If so, eliminate the node!
-  //
-  return
-    removeIndistinguishableNodes(AllocNodes) |
-    removeIndistinguishableNodes(ShadowNodes) |
-    removeIndistinguishableNodePairs(CallNodes) |
-    removeIndistinguishableNodePairs(GlobalNodes);
-}
-
-static void MarkReferredNodesReachable(DSNode *N,
-                                       vector<ShadowDSNode*> &ShadowNodes,
-                                       vector<bool> &ReachableShadowNodes,
-                                       vector<AllocDSNode*>  &AllocNodes,
-                                       vector<bool> &ReachableAllocNodes);
-
-static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS,
-                                            vector<ShadowDSNode*> &ShadowNodes,
-                                            vector<bool> &ReachableShadowNodes,
-                                            vector<AllocDSNode*>  &AllocNodes,
-                                            vector<bool> &ReachableAllocNodes) {
-  for (unsigned i = 0, e = PVS.size(); i != e; ++i)
-    if (isa<ShadowDSNode>(PVS[i].Node) || isa<AllocDSNode>(PVS[i].Node))
-      MarkReferredNodesReachable(PVS[i].Node, ShadowNodes, ReachableShadowNodes,
-                                 AllocNodes, ReachableAllocNodes);
-}
-
-static void MarkReferredNodesReachable(DSNode *N,
-                                       vector<ShadowDSNode*> &ShadowNodes,
-                                       vector<bool> &ReachableShadowNodes,
-                                       vector<AllocDSNode*>  &AllocNodes,
-                                       vector<bool> &ReachableAllocNodes) {
-  assert(ShadowNodes.size() == ReachableShadowNodes.size());
-  assert(AllocNodes.size()  == ReachableAllocNodes.size());
-
-  if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(N)) {
-    vector<ShadowDSNode*>::iterator I =
-      std::find(ShadowNodes.begin(), ShadowNodes.end(), Shad);
-    unsigned i = I-ShadowNodes.begin();
-    if (ReachableShadowNodes[i]) return;  // Recursion detected, abort...
-    ReachableShadowNodes[i] = true;
-  } else if (AllocDSNode *Alloc = dyn_cast<AllocDSNode>(N)) {
-    vector<AllocDSNode*>::iterator I =
-      std::find(AllocNodes.begin(), AllocNodes.end(), Alloc);
-    unsigned i = I-AllocNodes.begin();
-    if (ReachableAllocNodes[i]) return;  // Recursion detected, abort...
-    ReachableAllocNodes[i] = true;
-  }
-
-  for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i)
-    MarkReferredNodeSetReachable(N->getLink(i),
-                                 ShadowNodes, ReachableShadowNodes,
-                                 AllocNodes, ReachableAllocNodes);
-
-  const vector<PointerValSet> *Links = N->getAuxLinks();
-  if (Links)
-    for (unsigned i = 0, e = Links->size(); i != e; ++i)
-      MarkReferredNodeSetReachable((*Links)[i],
-                                   ShadowNodes, ReachableShadowNodes,
-                                   AllocNodes, ReachableAllocNodes);
-}
-
-void FunctionDSGraph::MarkEscapeableNodesReachable(
-                                       vector<bool> &ReachableShadowNodes,
-                                       vector<bool> &ReachableAllocNodes) {
-  // Mark all shadow nodes that have edges from other nodes as reachable.  
-  // Recursively mark any shadow nodes pointed to by the newly live shadow
-  // nodes as also alive.
-  //
-  for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
-    MarkReferredNodesReachable(GlobalNodes[i],
-                               ShadowNodes, ReachableShadowNodes,
-                               AllocNodes, ReachableAllocNodes);
-  
-  for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
-    MarkReferredNodesReachable(CallNodes[i],
-                               ShadowNodes, ReachableShadowNodes,
-                               AllocNodes, ReachableAllocNodes);
-  
-  // Mark all nodes in the return set as being reachable...
-  MarkReferredNodeSetReachable(RetNode,
-                               ShadowNodes, ReachableShadowNodes,
-                               AllocNodes, ReachableAllocNodes);
-}
-
-bool FunctionDSGraph::RemoveUnreachableNodes() {
-  bool Changed = false;
-  bool LocalChange = true;
-  
-  while (LocalChange) {
-    LocalChange = false;
-    // Reachable*Nodes - Contains true if there is an edge from a reachable
-    // node to the numbered node...
-    //
-    vector<bool> ReachableShadowNodes(ShadowNodes.size());
-    vector<bool> ReachableAllocNodes (AllocNodes.size());
-    
-    MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
-
-    // Mark all nodes in the value map as being reachable...
-    for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
-           E = ValueMap.end(); I != E; ++I)
-      MarkReferredNodeSetReachable(I->second,
-                                   ShadowNodes, ReachableShadowNodes,
-                                   AllocNodes, ReachableAllocNodes);
-
-    // At this point, all reachable shadow nodes have a true value in the
-    // Reachable vector.  This means that any shadow nodes without an entry in
-    // the reachable vector are not reachable and should be removed.  This is 
-    // a two part process, because we must drop all references before we delete
-    // the shadow nodes [in case cycles exist].
-    // 
-    for (unsigned i = 0; i != ShadowNodes.size(); ++i)
-      if (!ReachableShadowNodes[i]) {
-        // Track all unreachable nodes...
-#if DEBUG_NODE_ELIMINATE
-        std::cerr << "Unreachable node eliminated:\n";
-        ShadowNodes[i]->print(std::cerr);
-#endif
-        ShadowNodes[i]->removeAllIncomingEdges();
-        delete ShadowNodes[i];
-
-        // Remove from reachable...
-        ReachableShadowNodes.erase(ReachableShadowNodes.begin()+i);
-        ShadowNodes.erase(ShadowNodes.begin()+i);   // Remove node entry
-        --i;  // Don't skip the next node.
-        LocalChange = Changed = true;
-      }
-
-    for (unsigned i = 0; i != AllocNodes.size(); ++i)
-      if (!ReachableAllocNodes[i]) {
-        // Track all unreachable nodes...
-#if DEBUG_NODE_ELIMINATE
-        std::cerr << "Unreachable node eliminated:\n";
-        AllocNodes[i]->print(std::cerr);
-#endif
-        AllocNodes[i]->removeAllIncomingEdges();
-        delete AllocNodes[i];
-
-        // Remove from reachable...
-        ReachableAllocNodes.erase(ReachableAllocNodes.begin()+i);
-        AllocNodes.erase(AllocNodes.begin()+i);   // Remove node entry
-        --i;  // Don't skip the next node.
-        LocalChange = Changed = true;
-      }
-  }
-
-  // Loop over the global nodes, removing nodes that have no edges into them or
-  // out of them.
-  // 
-  for (vector<GlobalDSNode*>::iterator I = GlobalNodes.begin();
-       I != GlobalNodes.end(); )
-    if ((*I)->getReferrers().empty()) {
-      GlobalDSNode *GDN = *I;
-      bool NoLinks = true;    // Make sure there are no outgoing links...
-      for (unsigned i = 0, e = GDN->getNumLinks(); i != e; ++i)
-        if (!GDN->getLink(i).empty()) {
-          NoLinks = false;
-          break;
-        }
-      if (NoLinks) {
-        delete GDN;
-        I = GlobalNodes.erase(I);                     // Remove the node...
-        Changed = true;
-      } else {
-        ++I;
-      }
-    } else {
-      ++I;
-    }
-  
-  return Changed;
-}
-
-
-
-
-// getEscapingAllocations - Add all allocations that escape the current
-// function to the specified vector.
-//
-void FunctionDSGraph::getEscapingAllocations(vector<AllocDSNode*> &Allocs) {
-  vector<bool> ReachableShadowNodes(ShadowNodes.size());
-  vector<bool> ReachableAllocNodes (AllocNodes.size());
-    
-  MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
-
-  for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
-    if (ReachableAllocNodes[i])
-      Allocs.push_back(AllocNodes[i]);
-}
-
-// getNonEscapingAllocations - Add all allocations that do not escape the
-// current function to the specified vector.
-//
-void FunctionDSGraph::getNonEscapingAllocations(vector<AllocDSNode*> &Allocs) {
-  vector<bool> ReachableShadowNodes(ShadowNodes.size());
-  vector<bool> ReachableAllocNodes (AllocNodes.size());
-    
-  MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
-
-  for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
-    if (!ReachableAllocNodes[i])
-      Allocs.push_back(AllocNodes[i]);
-}
diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp b/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
deleted file mode 100644
index be49eec177..0000000000
--- a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
+++ /dev/null
@@ -1,365 +0,0 @@
-//===- FunctionRepBuilder.cpp - Build the local datastructure graph -------===//
-//
-// Build the local datastructure graph for a single method.
-//
-//===----------------------------------------------------------------------===//
-
-#include "FunctionRepBuilder.h"
-#include "llvm/Function.h"
-#include "llvm/BasicBlock.h"
-#include "llvm/iMemory.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iOther.h"
-#include "llvm/iTerminators.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Constants.h"
-#include "Support/STLExtras.h"
-#include <algorithm>
-
-// synthesizeNode - Create a new shadow node that is to be linked into this
-// chain..
-// FIXME: This should not take a FunctionRepBuilder as an argument!
-//
-ShadowDSNode *DSNode::synthesizeNode(const Type *Ty,
-                                     FunctionRepBuilder *Rep) {
-  // If we are a derived shadow node, defer to our parent to synthesize the node
-  if (ShadowDSNode *Th = dyn_cast<ShadowDSNode>(this))
-    if (Th->getShadowParent())
-      return Th->getShadowParent()->synthesizeNode(Ty, Rep);
-
-  // See if we have already synthesized a node of this type...
-  for (unsigned i = 0, e = SynthNodes.size(); i != e; ++i)
-    if (SynthNodes[i].first == Ty) return SynthNodes[i].second;
-
-  // No we haven't.  Do so now and add it to our list of saved nodes...
-
-  ShadowDSNode *SN = Rep->makeSynthesizedShadow(Ty, this);
-  SynthNodes.push_back(std::make_pair(Ty, SN));
-
-  return SN;
-}
-
-ShadowDSNode *FunctionRepBuilder::makeSynthesizedShadow(const Type *Ty,
-                                                        DSNode *Parent) {
-  ShadowDSNode *Result = new ShadowDSNode(Ty, F->getFunction()->getParent(),
-                                          Parent);
-  ShadowNodes.push_back(Result);
-  return Result;
-}
-
-
-
-// visitOperand - If the specified instruction operand is a global value, add
-// a node for it...
-//
-void InitVisitor::visitOperand(Value *V) {
-  if (!Rep->ValueMap.count(V))                  // Only process it once...
-    if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
-      GlobalDSNode *N = new GlobalDSNode(GV);
-      Rep->GlobalNodes.push_back(N);
-      Rep->ValueMap[V].add(N);
-      Rep->addAllUsesToWorkList(GV);
-
-      // FIXME: If the global variable has fields, we should add critical
-      // shadow nodes to represent them!
-    }
-}
-
-
-// visitCallInst - Create a call node for the callinst, and create as shadow
-// node if the call returns a pointer value.  Check to see if the call node
-// uses any global variables...
-//
-void InitVisitor::visitCallInst(CallInst &CI) {
-  CallDSNode *C = new CallDSNode(&CI);
-  Rep->CallNodes.push_back(C);
-  Rep->CallMap[&CI] = C;
-      
-  if (const PointerType *PT = dyn_cast<PointerType>(CI.getType())) {
-    // Create a critical shadow node to represent the memory object that the
-    // return value points to...
-    ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(),
-                                          Func->getParent());
-    Rep->ShadowNodes.push_back(Shad);
-    
-    // The return value of the function is a pointer to the shadow value
-    // just created...
-    //
-    C->getLink(0).add(Shad);
-
-    // The call instruction returns a pointer to the shadow block...
-    Rep->ValueMap[&CI].add(Shad, &CI);
-    
-    // If the call returns a value with pointer type, add all of the users
-    // of the call instruction to the work list...
-    Rep->addAllUsesToWorkList(&CI);
-  }
-
-  // Loop over all of the operands of the call instruction (except the first
-  // one), to look for global variable references...
-  //
-  for_each(CI.op_begin(), CI.op_end(),
-           bind_obj(this, &InitVisitor::visitOperand));
-}
-
-
-// visitAllocationInst - Create an allocation node for the allocation.  Since
-// allocation instructions do not take pointer arguments, they cannot refer to
-// global vars...
-//
-void InitVisitor::visitAllocationInst(AllocationInst &AI) {
-  AllocDSNode *N = new AllocDSNode(&AI);
-  Rep->AllocNodes.push_back(N);
-  
-  Rep->ValueMap[&AI].add(N, &AI);
-  
-  // Add all of the users of the malloc instruction to the work list...
-  Rep->addAllUsesToWorkList(&AI);
-}
-
-
-// Visit all other instruction types.  Here we just scan, looking for uses of
-// global variables...
-//
-void InitVisitor::visitInstruction(Instruction &I) {
-  for_each(I.op_begin(), I.op_end(),
-           bind_obj(this, &InitVisitor::visitOperand));
-}
-
-
-// addAllUsesToWorkList - Add all of the instructions users of the specified
-// value to the work list for further processing...
-//
-void FunctionRepBuilder::addAllUsesToWorkList(Value *V) {
-  //cerr << "Adding all uses of " << V << "\n";
-  for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
-    Instruction *Inst = cast<Instruction>(*I);
-    // When processing global values, it's possible that the instructions on
-    // the use list are not all in this method.  Only add the instructions
-    // that _are_ in this method.
-    //
-    if (Inst->getParent()->getParent() == F->getFunction())
-      // Only let an instruction occur on the work list once...
-      if (std::find(WorkList.begin(), WorkList.end(), Inst) == WorkList.end())
-        WorkList.push_back(Inst);
-  }
-}
-
-
-
-
-void FunctionRepBuilder::initializeWorkList(Function *Func) {
-  // Add all of the arguments to the method to the graph and add all users to
-  // the worklists...
-  //
-  for (Function::aiterator I = Func->abegin(), E = Func->aend(); I != E; ++I) {
-    // Only process arguments that are of pointer type...
-    if (const PointerType *PT = dyn_cast<PointerType>(I->getType())) {
-      // Add a shadow value for it to represent what it is pointing to and add
-      // this to the value map...
-      ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(),
-                                            Func->getParent());
-      ShadowNodes.push_back(Shad);
-      ValueMap[I].add(PointerVal(Shad), I);
-      
-      // Make sure that all users of the argument are processed...
-      addAllUsesToWorkList(I);
-    }
-  }
-
-  // Iterate over the instructions in the method.  Create nodes for malloc and
-  // call instructions.  Add all uses of these to the worklist of instructions
-  // to process.
-  //
-  InitVisitor IV(this, Func);
-  IV.visit(Func);
-}
-
-
-
-
-PointerVal FunctionRepBuilder::getIndexedPointerDest(const PointerVal &InP,
-                                                     const MemAccessInst &MAI) {
-  unsigned Index = InP.Index;
-  const Type *SrcTy = MAI.getPointerOperand()->getType();
-
-  for (MemAccessInst::const_op_iterator I = MAI.idx_begin(),
-         E = MAI.idx_end(); I != E; ++I)
-    if ((*I)->getType() == Type::UByteTy) {     // Look for struct indices...
-      const StructType *STy = cast<StructType>(SrcTy);
-      unsigned StructIdx = cast<ConstantUInt>(I->get())->getValue();
-      for (unsigned i = 0; i != StructIdx; ++i)
-        Index += countPointerFields(STy->getContainedType(i));
-
-      // Advance SrcTy to be the new element type...
-      SrcTy = STy->getContainedType(StructIdx);
-    } else {
-      // Otherwise, stepping into array or initial pointer, just increment type
-      SrcTy = cast<SequentialType>(SrcTy)->getElementType();
-    }
-  
-  return PointerVal(InP.Node, Index);
-}
-
-static PointerValSet &getField(const PointerVal &DestPtr) {
-  assert(DestPtr.Node != 0);
-  return DestPtr.Node->getLink(DestPtr.Index);
-}
-
-
-// Reprocessing a GEP instruction is the result of the pointer operand
-// changing.  This means that the set of possible values for the GEP
-// needs to be expanded.
-//
-void FunctionRepBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) {
-  PointerValSet &GEPPVS = ValueMap[&GEP];   // PointerValSet to expand
-      
-  // Get the input pointer val set...
-  const PointerValSet &SrcPVS = ValueMap[GEP.getOperand(0)];
-      
-  bool Changed = false;  // Process each input value... propogating it.
-  for (unsigned i = 0, e = SrcPVS.size(); i != e; ++i) {
-    // Calculate where the resulting pointer would point based on an
-    // input of 'Val' as the pointer type... and add it to our outgoing
-    // value set.  Keep track of whether or not we actually changed
-    // anything.
-    //
-    Changed |= GEPPVS.add(getIndexedPointerDest(SrcPVS[i], GEP));
-  }
-
-  // If our current value set changed, notify all of the users of our
-  // value.
-  //
-  if (Changed) addAllUsesToWorkList(&GEP);        
-}
-
-void FunctionRepBuilder::visitReturnInst(ReturnInst &RI) {
-  RetNode.add(ValueMap[RI.getOperand(0)]);
-}
-
-void FunctionRepBuilder::visitLoadInst(LoadInst &LI) {
-  // Only loads that return pointers are interesting...
-  const PointerType *DestTy = dyn_cast<PointerType>(LI.getType());
-  if (DestTy == 0) return;
-
-  const PointerValSet &SrcPVS = ValueMap[LI.getOperand(0)];        
-  PointerValSet &LIPVS = ValueMap[&LI];
-
-  bool Changed = false;
-  for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) {
-    PointerVal Ptr = getIndexedPointerDest(SrcPVS[si], LI);
-    PointerValSet &Field = getField(Ptr);
-
-    if (Field.size()) {             // Field loaded wasn't null?
-      Changed |= LIPVS.add(Field);
-    } else {
-      // If we are loading a null field out of a shadow node, we need to
-      // synthesize a new shadow node and link it in...
-      //
-      ShadowDSNode *SynthNode =
-        Ptr.Node->synthesizeNode(DestTy->getElementType(), this);
-      Field.add(SynthNode);
-
-      Changed |= LIPVS.add(Field);
-    }
-  }
-
-  if (Changed) addAllUsesToWorkList(&LI);
-}
-
-void FunctionRepBuilder::visitStoreInst(StoreInst &SI) {
-  // The only stores that are interesting are stores the store pointers
-  // into data structures...
-  //
-  if (!isa<PointerType>(SI.getOperand(0)->getType())) return;
-  if (!ValueMap.count(SI.getOperand(0))) return;  // Src scalar has no values!
-        
-  const PointerValSet &SrcPVS = ValueMap[SI.getOperand(0)];
-  const PointerValSet &PtrPVS = ValueMap[SI.getOperand(1)];
-
-  for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) {
-    const PointerVal &SrcPtr = SrcPVS[si];
-    for (unsigned pi = 0, pe = PtrPVS.size(); pi != pe; ++pi) {
-      PointerVal Dest = getIndexedPointerDest(PtrPVS[pi], SI);
-
-#if 0
-      std::cerr << "Setting Dest:\n";
-      Dest.print(std::cerr);
-      std::cerr << "to point to Src:\n";
-      SrcPtr.print(std::cerr);
-#endif
-
-      // Add SrcPtr into the Dest field...
-      if (getField(Dest).add(SrcPtr)) {
-        // If we modified the dest field, then invalidate everyone that points
-        // to Dest.
-        const std::vector<Value*> &Ptrs = Dest.Node->getPointers();
-        for (unsigned i = 0, e = Ptrs.size(); i != e; ++i)
-          addAllUsesToWorkList(Ptrs[i]);
-      }
-    }
-  }
-}
-
-void FunctionRepBuilder::visitCallInst(CallInst &CI) {
-  CallDSNode *DSN = CallMap[&CI];
-  unsigned PtrNum = 0;
-  for (unsigned i = 0, e = CI.getNumOperands(); i != e; ++i)
-    if (isa<PointerType>(CI.getOperand(i)->getType()))
-      DSN->addArgValue(PtrNum++, ValueMap[CI.getOperand(i)]);
-}
-
-void FunctionRepBuilder::visitPHINode(PHINode &PN) {
-  assert(isa<PointerType>(PN.getType()) && "Should only update ptr phis");
-
-  PointerValSet &PN_PVS = ValueMap[&PN];
-  bool Changed = false;
-  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
-    Changed |= PN_PVS.add(ValueMap[PN.getIncomingValue(i)],
-                          PN.getIncomingValue(i));
-
-  if (Changed) addAllUsesToWorkList(&PN);
-}
-
-
-
-
-// FunctionDSGraph constructor - Perform the global analysis to determine
-// what the data structure usage behavior or a method looks like.
-//
-FunctionDSGraph::FunctionDSGraph(Function *F) : Func(F) {
-  FunctionRepBuilder Builder(this);
-  AllocNodes  = Builder.getAllocNodes();
-  ShadowNodes = Builder.getShadowNodes();
-  GlobalNodes = Builder.getGlobalNodes();
-  CallNodes   = Builder.getCallNodes();
-  RetNode     = Builder.getRetNode();
-  ValueMap    = Builder.getValueMap();
-
-  // Remove all entries in the value map that consist of global values pointing
-  // at things.  They can only point to their node, so there is no use keeping
-  // them.
-  //
-  for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
-         E = ValueMap.end(); I != E;)
-    if (isa<GlobalValue>(I->first)) {
-#if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER
-      I = ValueMap.erase(I);
-#else
-      ValueMap.erase(I);            // This is really lame.
-      I = ValueMap.begin();         // GCC's stdc++ lib doesn't return an it!
-#endif
-    } else
-      ++I;
-
-  bool Changed = true;
-  while (Changed) {
-    // Eliminate shadow nodes that are not distinguishable from some other
-    // node in the graph...
-    //
-    Changed = UnlinkUndistinguishableNodes();
-
-    // Eliminate shadow nodes that are now extraneous due to linking...
-    Changed |= RemoveUnreachableNodes();
-  }
-}
diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.h b/lib/Analysis/DataStructure/FunctionRepBuilder.h
deleted file mode 100644
index 9965759fec..0000000000
--- a/lib/Analysis/DataStructure/FunctionRepBuilder.h
+++ /dev/null
@@ -1,135 +0,0 @@
-//===- FunctionRepBuilder.h - Structures for graph building ------*- C++ -*--=//
-//
-// This file defines the FunctionRepBuilder and InitVisitor classes that are
-// used to build the local data structure graph for a method.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef DATA_STRUCTURE_METHOD_REP_BUILDER_H
-#define DATA_STRUCTURE_METHOD_REP_BUILDER_H
-
-#include "llvm/Analysis/DataStructure.h"
-#include "llvm/Support/InstVisitor.h"
-
-// DEBUG_DATA_STRUCTURE_CONSTRUCTION - Define this to 1 if you want debug output
-//#define DEBUG_DATA_STRUCTURE_CONSTRUCTION 1
-
-class FunctionRepBuilder;
-
-// InitVisitor - Used to initialize the worklists for data structure analysis.
-// Iterate over the instructions in the method, creating nodes for malloc and
-// call instructions.  Add all uses of these to the worklist of instructions
-// to process.
-//
-class InitVisitor : public InstVisitor<InitVisitor> {
-  FunctionRepBuilder *Rep;
-  Function *Func;
-public:
-  InitVisitor(FunctionRepBuilder *R, Function *F) : Rep(R), Func(F) {}
-
-  void visitCallInst(CallInst &CI);
-  void visitAllocationInst(AllocationInst &AI);
-  void visitInstruction(Instruction &I);
-
-  // visitOperand - If the specified instruction operand is a global value, add
-  // a node for it...
-  //
-  void visitOperand(Value *V);
-};
-
-
-// FunctionRepBuilder - This builder object creates the datastructure graph for
-// a method.
-//
-class FunctionRepBuilder : InstVisitor<FunctionRepBuilder> {
-  friend class InitVisitor;
-  FunctionDSGraph *F;
-  PointerValSet RetNode;
-
-  // ValueMap - Mapping between values we are processing and the possible
-  // datastructures that they may point to...
-  std::map<Value*, PointerValSet> ValueMap;
-
-  // CallMap - Keep track of which call nodes correspond to which call insns.
-  // The reverse mapping is stored in the CallDSNodes themselves.
-  //
-  std::map<CallInst*, CallDSNode*> CallMap;
-
-  // Worklist - Vector of (pointer typed) instructions to process still...
-  std::vector<Instruction *> WorkList;
-
-  // Nodes - Keep track of all of the resultant nodes, because there may not
-  // be edges connecting these to anything.
-  //
-  std::vector<AllocDSNode*>  AllocNodes;
-  std::vector<ShadowDSNode*> ShadowNodes;
-  std::vector<GlobalDSNode*> GlobalNodes;
-  std::vector<CallDSNode*>   CallNodes;
-
-  // addAllUsesToWorkList - Add all of the instructions users of the specified
-  // value to the work list for further processing...
-  //
-  void addAllUsesToWorkList(Value *V);
-
-public:
-  FunctionRepBuilder(FunctionDSGraph *f) : F(f) {
-    initializeWorkList(F->getFunction());
-    processWorkList();
-  }
-
-  const std::vector<AllocDSNode*>  &getAllocNodes() const { return AllocNodes; }
-  const std::vector<ShadowDSNode*> &getShadowNodes() const {return ShadowNodes;}
-  const std::vector<GlobalDSNode*> &getGlobalNodes() const {return GlobalNodes;}
-  const std::vector<CallDSNode*>   &getCallNodes() const { return CallNodes; }
-
-
-  ShadowDSNode *makeSynthesizedShadow(const Type *Ty, DSNode *Parent);
-
-  const PointerValSet &getRetNode() const { return RetNode; }
-
-  const std::map<Value*, PointerValSet> &getValueMap() const { return ValueMap; }
-private:
-  static PointerVal getIndexedPointerDest(const PointerVal &InP,
-                                          const MemAccessInst &MAI);
-
-  void initializeWorkList(Function *Func);
-  void processWorkList() {
-    // While the worklist still has instructions to process, process them!
-    while (!WorkList.empty()) {
-      Instruction *I = WorkList.back(); WorkList.pop_back();
-
-#ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION
-      std::cerr << "Processing worklist inst: " << I;
-#endif
-    
-      visit(*I); // Dispatch to a visitXXX function based on instruction type...
-#ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION
-      if (I->hasName() && ValueMap.count(I)) {
-        std::cerr << "Inst %" << I->getName() << " value is:\n";
-        ValueMap[I].print(std::cerr);
-      }
-#endif
-    }
-  }
-
-  //===--------------------------------------------------------------------===//
-  // Functions used to process the worklist of instructions...
-  //
-  // Allow the visitor base class to invoke these methods...
-  friend class InstVisitor<FunctionRepBuilder>;
-
-  void visitGetElementPtrInst(GetElementPtrInst &GEP);
-  void visitReturnInst(ReturnInst &RI);
-  void visitLoadInst(LoadInst &LI);
-  void visitStoreInst(StoreInst &SI);
-  void visitCallInst(CallInst &CI);
-  void visitPHINode(PHINode &PN);
-  void visitSetCondInst(SetCondInst &SCI) {}  // SetEQ & friends are ignored
-  void visitFreeInst(FreeInst &FI) {}         // Ignore free instructions
-  void visitInstruction(Instruction &I) {
-    std::cerr << "\n\n\nUNKNOWN INSTRUCTION type: " << I << "\n\n\n";
-    assert(0 && "Cannot proceed");
-  }
-};
-
-#endif
diff --git a/lib/Analysis/DataStructure/NodeImpl.cpp b/lib/Analysis/DataStructure/NodeImpl.cpp
deleted file mode 100644
index 1b3fb76505..0000000000
--- a/lib/Analysis/DataStructure/NodeImpl.cpp
+++ /dev/null
@@ -1,470 +0,0 @@
-//===- NodeImpl.cpp - Implement the data structure analysis nodes ---------===//
-//
-// Implement the LLVM data structure analysis library.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/DataStructureGraph.h"
-#include "llvm/Assembly/Writer.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Function.h"
-#include "llvm/iMemory.h"
-#include "llvm/iOther.h"
-#include "Support/STLExtras.h"
-#include <algorithm>
-#include <sstream>
-using std::map;
-using std::string;
-
-bool AllocDSNode::isEquivalentTo(DSNode *Node) const {
-  if (AllocDSNode *N = dyn_cast<AllocDSNode>(Node))
-    return getType() == Node->getType();
-  //&& isAllocaNode() == N->isAllocaNode();
-  return false;
-}
-
-void AllocDSNode::mergeInto(DSNode *Node) const {
-  // Make sure the merged node is variable size if this node is var size
-  AllocDSNode *N = cast<AllocDSNode>(Node);
-  N->isVarSize |= isVarSize;
-}
-
-bool GlobalDSNode::isEquivalentTo(DSNode *Node) const {
-  if (const GlobalDSNode *G = dyn_cast<GlobalDSNode>(Node)) {
-    if (G->Val != Val) return false;
-
-    // Check that the outgoing links are identical...
-    assert(getNumLinks() == G->getNumLinks() && "Not identical shape?");
-    for (unsigned i = 0, e = getNumLinks(); i != e; ++i)
-      if (getLink(i) != G->getLink(i))          // Check links
-        return false;
-    return true;
-  }
-  return false;
-}
-
-// Call node equivalency - Two call nodes are identical if all of the outgoing
-// links are the same, AND if all of the incoming links are identical.
-//
-bool CallDSNode::isEquivalentTo(DSNode *Node) const {
-  if (CallDSNode *C = dyn_cast<CallDSNode>(Node)) {
-    if (getReferrers().size() != C->getReferrers().size() ||
-        C->getType() != getType())
-      return false; // Quick check...
-
-    // Check that the outgoing links are identical...
-    assert(getNumLinks() == C->getNumLinks() && "Not identical shape?");
-    for (unsigned i = 0, e = getNumLinks(); i != e; ++i)
-      if (getLink(i) != C->getLink(i))          // Check links
-        return false;
-
-
-    std::vector<PointerValSet*> Refs1 = C->getReferrers();
-    std::vector<PointerValSet*> Refs2 = getReferrers();
-
-    sort(Refs1.begin(), Refs1.end());
-    sort(Refs2.begin(), Refs2.end());
-    if (Refs1 != Refs2) return false;               // Incoming edges different?
-
-    // Check that all outgoing links are the same...
-    return C->ArgLinks == ArgLinks;   // Check that the arguments are identical
-  }
-  return false;
-}
-
-// NodesAreEquivalent - Check to see if the nodes are equivalent in all ways
-// except node type.  Since we know N1 is a shadow node, N2 is allowed to be
-// any type.
-//
-bool ShadowDSNode::isEquivalentTo(DSNode *Node) const {
-  return getType() == Node->getType();
-}
-
-
-
-
-//===----------------------------------------------------------------------===//
-//  DSNode Class Implementation
-//
-
-static void MapPVS(PointerValSet &PVSOut, const PointerValSet &PVSIn,
-                   map<const DSNode*, DSNode*> &NodeMap, bool ReinitOk = false){
-  assert((ReinitOk || PVSOut.empty()) && "Value set already initialized!");
-
-  for (unsigned i = 0, e = PVSIn.size(); i != e; ++i)
-    PVSOut.add(PointerVal(NodeMap[PVSIn[i].Node], PVSIn[i].Index));
-}
-
-
-
-unsigned countPointerFields(const Type *Ty) {
-  switch (Ty->getPrimitiveID()) {
-  case Type::StructTyID: {
-    const StructType *ST = cast<StructType>(Ty);
-    unsigned Sum = 0;
-    for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i)
-      Sum += countPointerFields(ST->getContainedType(i));
-
-    return Sum;
-  }
-
-  case Type::ArrayTyID:
-    // All array elements are folded together...
-    return countPointerFields(cast<ArrayType>(Ty)->getElementType());
-
-  case Type::PointerTyID:
-    return 1;
-    
-  default:                     // Some other type, just treat it like a scalar
-    return 0;
-  }
-}
-
-DSNode::DSNode(enum NodeTy NT, const Type *T) : Ty(T), NodeType(NT) {
-  // Create field entries for all of the values in this type...
-  FieldLinks.resize(countPointerFields(getType()));
-}
-
-void DSNode::removeReferrer(PointerValSet *PVS) {
-  std::vector<PointerValSet*>::iterator I = std::find(Referrers.begin(),
-                                                      Referrers.end(), PVS);
-  assert(I != Referrers.end() && "PVS not pointing to node!");
-  Referrers.erase(I);
-}
-
-
-// removeAllIncomingEdges - Erase all edges in the graph that point to this node
-void DSNode::removeAllIncomingEdges() {
-  while (!Referrers.empty())
-    Referrers.back()->removePointerTo(this);
-}
-
-
-static void replaceIn(std::string &S, char From, const std::string &To) {
-  for (unsigned i = 0; i < S.size(); )
-    if (S[i] == From) {
-      S.replace(S.begin()+i, S.begin()+i+1,
-                To.begin(), To.end());
-      i += To.size();
-    } else {
-      ++i;
-    }
-}
-
-static void writeEdges(std::ostream &O, const void *SrcNode,
-                       const char *SrcNodePortName, int SrcNodeIdx,
-                       const PointerValSet &VS, const string &EdgeAttr = "") {
-  for (unsigned j = 0, je = VS.size(); j != je; ++j) {
-    O << "\t\tNode" << SrcNode << SrcNodePortName;
-    if (SrcNodeIdx != -1) O << SrcNodeIdx;
-
-    O << " -> Node" << VS[j].Node;
-    if (VS[j].Index)
-      O << ":g" << VS[j].Index;
-
-    if (!EdgeAttr.empty())
-      O << "[" << EdgeAttr << "]";
-    O << ";\n";
-  }
-}
-
-static string escapeLabel(const string &In) {
-  string Label(In);
-  replaceIn(Label, '\\', "\\\\\\\\");  // Escape caption...
-  replaceIn(Label, ' ', "\\ ");
-  replaceIn(Label, '{', "\\{");
-  replaceIn(Label, '}', "\\}");
-  return Label;
-}
-
-void DSNode::dump() const { print(std::cerr); }
-
-void DSNode::print(std::ostream &O) const {
-  string Caption = escapeLabel(getCaption());
-
-  O << "\t\tNode" << (void*)this << " [ label =\"{" << Caption;
-
-  const std::vector<PointerValSet> *Links = getAuxLinks();
-  if (Links && !Links->empty()) {
-    O << "|{";
-    for (unsigned i = 0; i < Links->size(); ++i) {
-      if (i) O << "|";
-      O << "<f" << i << ">";
-    }
-    O << "}";
-  }
-
-  if (!FieldLinks.empty()) {
-    O << "|{";
-    for (unsigned i = 0; i < FieldLinks.size(); ++i) {
-      if (i) O << "|";
-      O << "<g" << i << ">";
-    }
-    O << "}";
-  }
-  O << "}\"];\n";
-
-  if (Links)
-    for (unsigned i = 0; i < Links->size(); ++i)
-      writeEdges(O, this, ":f", i, (*Links)[i]);
-  for (unsigned i = 0; i < FieldLinks.size(); ++i)
-    writeEdges(O, this, ":g", i, FieldLinks[i]);
-}
-
-void DSNode::mapNode(map<const DSNode*, DSNode*> &NodeMap, const DSNode *Old) {
-  assert(FieldLinks.size() == Old->FieldLinks.size() &&
-         "Cloned nodes do not have the same number of links!");
-  for (unsigned j = 0, je = FieldLinks.size(); j != je; ++j)
-    MapPVS(FieldLinks[j], Old->FieldLinks[j], NodeMap);
-
-  // Map our SynthNodes...
-  assert(SynthNodes.empty() && "Synthnodes already mapped?");
-  SynthNodes.reserve(Old->SynthNodes.size());
-  for (unsigned i = 0, e = Old->SynthNodes.size(); i != e; ++i)
-    SynthNodes.push_back(std::make_pair(Old->SynthNodes[i].first,
-                    (ShadowDSNode*)NodeMap[Old->SynthNodes[i].second]));
-}
-
-AllocDSNode::AllocDSNode(AllocationInst *V, bool isvarsize)
-  : DSNode(NewNode, V->getType()->getElementType()), Allocation(V) {
-
-  // Is variable size if incoming flag says so, or if allocation is var size
-  // already.
-  isVarSize = isvarsize || !isa<Constant>(V->getArraySize());
-}
-
-bool AllocDSNode::isAllocaNode() const {
-  return isa<AllocaInst>(Allocation);
-}
-
-
-string AllocDSNode::getCaption() const {
-  std::stringstream OS;
-  OS << (isMallocNode() ? "new " : "alloca ");
-
-  WriteTypeSymbolic(OS, getType(),
-                    Allocation->getParent()->getParent()->getParent());
-  if (isVarSize)
-    OS << "[ ]";
-  return OS.str();
-}
-
-GlobalDSNode::GlobalDSNode(GlobalValue *V)
-  : DSNode(GlobalNode, V->getType()->getElementType()), Val(V) {
-}
-
-string GlobalDSNode::getCaption() const {
-  std::stringstream OS;
-  if (isa<Function>(Val))
-    OS << "fn ";
-  else
-    OS << "global ";
-
-  WriteTypeSymbolic(OS, getType(), Val->getParent());
-  return OS.str() + " %" + Val->getName();
-}
-
-
-ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M) : DSNode(ShadowNode, Ty) {
-  Mod = M;
-  ShadowParent = 0;
-}
-
-ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M, DSNode *ShadParent)
-  : DSNode(ShadowNode, Ty) {
-  Mod = M;
-  ShadowParent = ShadParent;
-}
-
-std::string ShadowDSNode::getCaption() const {
-  std::stringstream OS;
-  OS << "shadow ";
-  WriteTypeSymbolic(OS, getType(), Mod);
-  return OS.str();
-}
-
-CallDSNode::CallDSNode(CallInst *ci) : DSNode(CallNode, ci->getType()), CI(ci) {
-  unsigned NumPtrs = 0;
-  for (unsigned i = 0, e = ci->getNumOperands(); i != e; ++i)
-    if (isa<PointerType>(ci->getOperand(i)->getType()))
-      NumPtrs++;
-  ArgLinks.resize(NumPtrs);
-}
-
-string CallDSNode::getCaption() const {
-  std::stringstream OS;
-  if (const Function *CM = CI->getCalledFunction())
-    OS << "call " << CM->getName();
-  else
-    OS << "call <indirect>";
-  OS << ": ";
-  WriteTypeSymbolic(OS, getType(),
-                    CI->getParent()->getParent()->getParent());
-  return OS.str();
-}
-
-void CallDSNode::mapNode(map<const DSNode*, DSNode*> &NodeMap,
-                         const DSNode *O) {
-  const CallDSNode *Old = cast<CallDSNode>(O);
-  DSNode::mapNode(NodeMap, Old);  // Map base portions first...
-
-  assert(ArgLinks.size() == Old->ArgLinks.size() && "# Arguments changed!?");
-  for (unsigned i = 0, e = Old->ArgLinks.size(); i != e; ++i)
-    MapPVS(ArgLinks[i], Old->ArgLinks[i], NodeMap);
-}
-
-void FunctionDSGraph::printFunction(std::ostream &O,
-                                    const char *Label) const {
-  O << "\tsubgraph cluster_" << Label << "_Function" << (void*)this << " {\n";
-  O << "\t\tlabel=\"" << Label << " Function\\ " << Func->getName() << "\";\n";
-  for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
-    AllocNodes[i]->print(O);
-  for (unsigned i = 0, e = ShadowNodes.size(); i != e; ++i)
-    ShadowNodes[i]->print(O);
-  for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
-    GlobalNodes[i]->print(O);
-  for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
-    CallNodes[i]->print(O);
-
-  if (RetNode.size()) {
-    O << "\t\tNode" << (void*)this << Label
-      << " [shape=\"ellipse\", label=\"Returns\"];\n";
-    writeEdges(O, this, Label, -1, RetNode);
-  }
-
-  O << "\n";
-  for (std::map<Value*, PointerValSet>::const_iterator I = ValueMap.begin(),
-         E = ValueMap.end(); I != E; ++I) {
-    if (I->second.size()) {             // Only output nodes with edges...
-      std::stringstream OS;
-      WriteTypeSymbolic(OS, I->first->getType(), Func->getParent());
-
-      // Create node for I->first
-      O << "\t\tNode" << (void*)I->first << Label << " [shape=\""
-        << (isa<Argument>(I->first) ? "ellipse" : "box") << "\", label=\""
-        << escapeLabel(OS.str()) << "\\n%" << escapeLabel(I->first->getName())
-        << "\",fontsize=\"12.0\",color=\"gray70\"];\n";
-      
-      // add edges from I->first to all pointers in I->second
-      writeEdges(O, I->first, Label, -1, I->second,
-                 "weight=\"0.9\",color=\"gray70\"");
-    }
-  }
-  
-  O << "\t}\n";
-}
-
-// Copy constructor - Since we copy the nodes over, we have to be sure to go
-// through and fix pointers to point into the new graph instead of into the old
-// graph...
-//
-FunctionDSGraph::FunctionDSGraph(const FunctionDSGraph &DSG) : Func(DSG.Func) {
-  std::vector<PointerValSet> Args;
-  RetNode = cloneFunctionIntoSelf(DSG, true, Args);
-}
-
-
-// cloneFunctionIntoSelf - Clone the specified method graph into the current
-// method graph, returning the Return's set of the graph.   If ValueMap is set
-// to true, the ValueMap of the function is cloned into this function as well
-// as the data structure graph itself.  Regardless, the arguments value sets
-// of DSG are copied into Args.
-//
-PointerValSet FunctionDSGraph::cloneFunctionIntoSelf(const FunctionDSGraph &DSG,
-                                                     bool CloneValueMap,
-                                                  std::vector<PointerValSet> &Args) {
-  map<const DSNode*, DSNode*> NodeMap;  // Map from old graph to new graph...
-  unsigned StartAllocSize = AllocNodes.size();
-  AllocNodes.reserve(StartAllocSize+DSG.AllocNodes.size());
-  unsigned StartShadowSize = ShadowNodes.size();
-  ShadowNodes.reserve(StartShadowSize+DSG.ShadowNodes.size());
-  unsigned StartGlobalSize = GlobalNodes.size();
-  GlobalNodes.reserve(StartGlobalSize+DSG.GlobalNodes.size());
-  unsigned StartCallSize = CallNodes.size();
-  CallNodes.reserve(StartCallSize+DSG.CallNodes.size());
-
-  // Clone all of the alloc nodes similarly...
-  for (unsigned i = 0, e = DSG.AllocNodes.size(); i != e; ++i) {
-    AllocDSNode *New = cast<AllocDSNode>(DSG.AllocNodes[i]->clone());
-    NodeMap[DSG.AllocNodes[i]] = New;
-    AllocNodes.push_back(New);
-  }
-
-  // Clone all of the shadow nodes similarly...
-  for (unsigned i = 0, e = DSG.ShadowNodes.size(); i != e; ++i) {
-    ShadowDSNode *New = cast<ShadowDSNode>(DSG.ShadowNodes[i]->clone());
-    NodeMap[DSG.ShadowNodes[i]] = New;
-    ShadowNodes.push_back(New);
-  }
-
-  // Clone all of the global nodes...
-  for (unsigned i = 0, e = DSG.GlobalNodes.size(); i != e; ++i) {
-    GlobalDSNode *New = cast<GlobalDSNode>(DSG.GlobalNodes[i]->clone());
-    NodeMap[DSG.GlobalNodes[i]] = New;
-    GlobalNodes.push_back(New);
-  }
-
-  // Clone all of the call nodes...
-  for (unsigned i = 0, e = DSG.CallNodes.size(); i != e; ++i) {
-    CallDSNode *New = cast<CallDSNode>(DSG.CallNodes[i]->clone());
-    NodeMap[DSG.CallNodes[i]] = New;
-    CallNodes.push_back(New);
-  }
-
-  // Convert all of the links over in the nodes now that the map has been filled
-  // in all the way...
-  //
-  for (unsigned i = 0, e = DSG.AllocNodes.size(); i != e; ++i)
-    AllocNodes[i+StartAllocSize]->mapNode(NodeMap, DSG.AllocNodes[i]);
-  for (unsigned i = 0, e = DSG.ShadowNodes.size(); i != e; ++i)
-    ShadowNodes[i+StartShadowSize]->mapNode(NodeMap, DSG.ShadowNodes[i]);
-  for (unsigned i = 0, e = DSG.GlobalNodes.size(); i != e; ++i)
-    GlobalNodes[i+StartGlobalSize]->mapNode(NodeMap, DSG.GlobalNodes[i]);
-  for (unsigned i = 0, e = DSG.CallNodes.size(); i != e; ++i)
-    CallNodes[i+StartCallSize]->mapNode(NodeMap, DSG.CallNodes[i]);
-
-  // Convert over the arguments...
-  Function *OF = DSG.getFunction();
-  for (Function::aiterator I = OF->abegin(), E = OF->aend(); I != E; ++I)
-    if (isa<PointerType>(I->getType())) {
-      PointerValSet ArgPVS;
-      assert(DSG.getValueMap().find(I) != DSG.getValueMap().end());
-      MapPVS(ArgPVS, DSG.getValueMap().find(I)->second, NodeMap);
-      assert(!ArgPVS.empty() && "Argument has no links!");
-      Args.push_back(ArgPVS);
-    }
-
-
-  if (CloneValueMap) {
-    // Convert value map... the values themselves stay the same, just the nodes
-    // have to change...
-    //
-    for (std::map<Value*,PointerValSet>::const_iterator I =DSG.ValueMap.begin(),
-           E = DSG.ValueMap.end(); I != E; ++I)
-      MapPVS(ValueMap[I->first], I->second, NodeMap, true);
-  }
-
-  // Convert over return node...
-  PointerValSet RetVals;
-  MapPVS(RetVals, DSG.RetNode, NodeMap);
-  return RetVals;
-}
-
-
-FunctionDSGraph::~FunctionDSGraph() {
-  RetNode.clear();
-  ValueMap.clear();
-  for_each(AllocNodes.begin(), AllocNodes.end(),
-           std::mem_fun(&DSNode::dropAllReferences));
-  for_each(ShadowNodes.begin(), ShadowNodes.end(),
-           std::mem_fun(&DSNode::dropAllReferences));
-  for_each(GlobalNodes.begin(), GlobalNodes.end(),
-           std::mem_fun(&DSNode::dropAllReferences));
-  for_each(CallNodes.begin(), CallNodes.end(),
-           std::mem_fun(&DSNode::dropAllReferences));
-  for_each(AllocNodes.begin(),  AllocNodes.end(),  deleter<DSNode>);
-  for_each(ShadowNodes.begin(), ShadowNodes.end(), deleter<DSNode>);
-  for_each(GlobalNodes.begin(), GlobalNodes.end(), deleter<DSNode>);
-  for_each(CallNodes.begin(),   CallNodes.end(),   deleter<DSNode>);
-}
-