Remove DSA from release_19 branch.

llvm-svn: 33089

6 files changed, 0 insertions, 2073 deletions

diff --git a/llvm/include/llvm/Analysis/DataStructure/CallTargets.h b/llvm/include/llvm/Analysis/DataStructure/CallTargets.h
deleted file mode 100644
index d4f56e8c801f..000000000000
--- a/llvm/include/llvm/Analysis/DataStructure/CallTargets.h
+++ /dev/null
@@ -1,54 +0,0 @@
-//=- llvm/Analysis/CallTargets.h - Resolve Indirect Call Targets --*- C++ -*-=//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This pass uses DSA to map targets of all calls, and reports on if it
-// thinks it knows all targets of a given call.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_CALLTARGETS_H
-#define LLVM_ANALYSIS_CALLTARGETS_H
-
-#include "llvm/Pass.h"
-#include "llvm/Support/CallSite.h"
-
-#include <set>
-#include <list>
-
-namespace llvm {
-
-  class CallTargetFinder : public ModulePass {
-    std::map<CallSite, std::vector<Function*> > IndMap;
-    std::set<CallSite> CompleteSites;
-    std::list<CallSite> AllSites;
-
-    void findIndTargets(Module &M);
-  public:
-    virtual bool runOnModule(Module &M);
-
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-
-    virtual void print(std::ostream &O, const Module *M) const;
-
-    // Given a CallSite, get an iterator of callees
-    std::vector<Function*>::iterator begin(CallSite cs);
-    std::vector<Function*>::iterator end(CallSite cs);
-
-    // Iterate over CallSites in program
-    std::list<CallSite>::iterator cs_begin();
-    std::list<CallSite>::iterator cs_end();
-
-    // Do we think we have complete knowledge of this site?
-    // That is, do we think there are no missing callees
-    bool isComplete(CallSite cs) const;
-  };
-  
-}
-
-#endif
diff --git a/llvm/include/llvm/Analysis/DataStructure/DSGraph.h b/llvm/include/llvm/Analysis/DataStructure/DSGraph.h
deleted file mode 100644
index eb4388b6ad9a..000000000000
--- a/llvm/include/llvm/Analysis/DataStructure/DSGraph.h
+++ /dev/null
@@ -1,581 +0,0 @@
-//===- DSGraph.h - Represent a collection of data structures ----*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This header defines the data structure graph (DSGraph) and the
-// ReachabilityCloner class.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSGRAPH_H
-#define LLVM_ANALYSIS_DSGRAPH_H
-
-#include "llvm/Analysis/DataStructure/DSNode.h"
-#include "llvm/ADT/hash_map"
-#include "llvm/ADT/EquivalenceClasses.h"
-#include <list>
-
-namespace llvm {
-
-class GlobalValue;
-
-//===----------------------------------------------------------------------===//
-/// DSScalarMap - An instance of this class is used to keep track of all of
-/// which DSNode each scalar in a function points to.  This is specialized to
-/// keep track of globals with nodes in the function, and to keep track of the
-/// unique DSNodeHandle being used by the scalar map.
-///
-/// This class is crucial to the efficiency of DSA with some large SCC's.  In
-/// these cases, the cost of iterating over the scalar map dominates the cost
-/// of DSA.  In all of these cases, the DSA phase is really trying to identify
-/// globals or unique node handles active in the function.
-///
-class DSScalarMap {
-  typedef hash_map<Value*, DSNodeHandle> ValueMapTy;
-  ValueMapTy ValueMap;
-
-  typedef hash_set<GlobalValue*> GlobalSetTy;
-  GlobalSetTy GlobalSet;
-
-  EquivalenceClasses<GlobalValue*> &GlobalECs;
-public:
-  DSScalarMap(EquivalenceClasses<GlobalValue*> &ECs) : GlobalECs(ECs) {}
-
-  EquivalenceClasses<GlobalValue*> &getGlobalECs() const { return GlobalECs; }
-
-  // Compatibility methods: provide an interface compatible with a map of
-  // Value* to DSNodeHandle's.
-  typedef ValueMapTy::const_iterator const_iterator;
-  typedef ValueMapTy::iterator iterator;
-  iterator begin() { return ValueMap.begin(); }
-  iterator end()   { return ValueMap.end(); }
-  const_iterator begin() const { return ValueMap.begin(); }
-  const_iterator end() const { return ValueMap.end(); }
-
-  GlobalValue *getLeaderForGlobal(GlobalValue *GV) const {
-    EquivalenceClasses<GlobalValue*>::iterator ECI = GlobalECs.findValue(GV);
-    if (ECI == GlobalECs.end()) return GV;
-    return *GlobalECs.findLeader(ECI);
-  }
-
-
-  iterator find(Value *V) {
-    iterator I = ValueMap.find(V);
-    if (I != ValueMap.end()) return I;
-
-    if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
-      // If this is a global, check to see if it is equivalenced to something
-      // in the map.
-      GlobalValue *Leader = getLeaderForGlobal(GV);
-      if (Leader != GV)
-        I = ValueMap.find((Value*)Leader);
-    }
-    return I;
-  }
-  const_iterator find(Value *V) const {
-    const_iterator I = ValueMap.find(V);
-    if (I != ValueMap.end()) return I;
-
-    if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
-      // If this is a global, check to see if it is equivalenced to something
-      // in the map.
-      GlobalValue *Leader = getLeaderForGlobal(GV);
-      if (Leader != GV)
-        I = ValueMap.find((Value*)Leader);
-    }
-    return I;
-  }
-
-  /// getRawEntryRef - This method can be used by clients that are aware of the
-  /// global value equivalence class in effect.
-  DSNodeHandle &getRawEntryRef(Value *V) {
-    std::pair<iterator,bool> IP =
-      ValueMap.insert(std::make_pair(V, DSNodeHandle()));
-     if (IP.second)   // Inserted the new entry into the map.
-       if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
-         GlobalSet.insert(GV);
-     return IP.first->second;
-  }
-
-  unsigned count(Value *V) const { return ValueMap.find(V) != ValueMap.end(); }
-
-  void erase(Value *V) { erase(ValueMap.find(V)); }
-
-  void eraseIfExists(Value *V) {
-    iterator I = find(V);
-    if (I != end()) erase(I);
-  }
-
-  /// replaceScalar - When an instruction needs to be modified, this method can
-  /// be used to update the scalar map to remove the old and insert the new.
-  ///
-  void replaceScalar(Value *Old, Value *New) {
-    iterator I = find(Old);
-    assert(I != end() && "Old value is not in the map!");
-    ValueMap.insert(std::make_pair(New, I->second));
-    erase(I);
-  }
-
-  /// copyScalarIfExists - If Old exists in the scalar map, make New point to
-  /// whatever Old did.
-  void copyScalarIfExists(Value *Old, Value *New) {
-    iterator I = find(Old);
-    if (I != end())
-      ValueMap.insert(std::make_pair(New, I->second));
-  }
-
-  /// operator[] - Return the DSNodeHandle for the specified value, creating a
-  /// new null handle if there is no entry yet.
-  DSNodeHandle &operator[](Value *V) {
-    iterator I = ValueMap.find(V);
-    if (I != ValueMap.end())
-      return I->second;   // Return value if already exists.
-
-    if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
-      return AddGlobal(GV);
-
-    return ValueMap.insert(std::make_pair(V, DSNodeHandle())).first->second;
-  }
-
-  void erase(iterator I) {
-    assert(I != ValueMap.end() && "Cannot erase end!");
-    if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first))
-      GlobalSet.erase(GV);
-    ValueMap.erase(I);
-  }
-
-  void clear() {
-    ValueMap.clear();
-    GlobalSet.clear();
-  }
-
-  /// spliceFrom - Copy all entries from RHS, then clear RHS.
-  ///
-  void spliceFrom(DSScalarMap &RHS);
-
-  // Access to the global set: the set of all globals currently in the
-  // scalar map.
-  typedef GlobalSetTy::const_iterator global_iterator;
-  global_iterator global_begin() const { return GlobalSet.begin(); }
-  global_iterator global_end() const { return GlobalSet.end(); }
-  unsigned global_size() const { return GlobalSet.size(); }
-  unsigned global_count(GlobalValue *GV) const { return GlobalSet.count(GV); }
-private:
-  DSNodeHandle &AddGlobal(GlobalValue *GV);
-};
-
-
-//===----------------------------------------------------------------------===//
-/// DSGraph - The graph that represents a function.
-///
-class DSGraph {
-public:
-  // Public data-type declarations...
-  typedef DSScalarMap ScalarMapTy;
-  typedef hash_map<Function*, DSNodeHandle> ReturnNodesTy;
-  typedef ilist<DSNode> NodeListTy;
-
-  /// NodeMapTy - This data type is used when cloning one graph into another to
-  /// keep track of the correspondence between the nodes in the old and new
-  /// graphs.
-  typedef hash_map<const DSNode*, DSNodeHandle> NodeMapTy;
-
-  // InvNodeMapTy - This data type is used to represent the inverse of a node
-  // map.
-  typedef hash_multimap<DSNodeHandle, const DSNode*> InvNodeMapTy;
-private:
-  DSGraph *GlobalsGraph;   // Pointer to the common graph of global objects
-  bool PrintAuxCalls;      // Should this graph print the Aux calls vector?
-
-  NodeListTy Nodes;
-  ScalarMapTy ScalarMap;
-
-  // ReturnNodes - A return value for every function merged into this graph.
-  // Each DSGraph may have multiple functions merged into it at any time, which
-  // is used for representing SCCs.
-  //
-  ReturnNodesTy ReturnNodes;
-
-  // FunctionCalls - This list maintains a single entry for each call
-  // instruction in the current graph.  The first entry in the vector is the
-  // scalar that holds the return value for the call, the second is the function
-  // scalar being invoked, and the rest are pointer arguments to the function.
-  // This vector is built by the Local graph and is never modified after that.
-  //
-  std::list<DSCallSite> FunctionCalls;
-
-  // AuxFunctionCalls - This vector contains call sites that have been processed
-  // by some mechanism.  In pratice, the BU Analysis uses this vector to hold
-  // the _unresolved_ call sites, because it cannot modify FunctionCalls.
-  //
-  std::list<DSCallSite> AuxFunctionCalls;
-
-  /// TD - This is the target data object for the machine this graph is
-  /// constructed for.
-  const TargetData &TD;
-
-  void operator=(const DSGraph &); // DO NOT IMPLEMENT
-  DSGraph(const DSGraph&);         // DO NOT IMPLEMENT
-public:
-  // Create a new, empty, DSGraph.
-  DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &td)
-    : GlobalsGraph(0), PrintAuxCalls(false), ScalarMap(ECs), TD(td) {}
-
-  // Compute the local DSGraph
-  DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &TD,
-          Function &F, DSGraph *GlobalsGraph);
-
-  // Copy ctor - If you want to capture the node mapping between the source and
-  // destination graph, you may optionally do this by specifying a map to record
-  // this into.
-  //
-  // Note that a copied graph does not retain the GlobalsGraph pointer of the
-  // source.  You need to set a new GlobalsGraph with the setGlobalsGraph
-  // method.
-  //
-  DSGraph(const DSGraph &DSG, EquivalenceClasses<GlobalValue*> &ECs,
-          unsigned CloneFlags = 0);
-  ~DSGraph();
-
-  DSGraph *getGlobalsGraph() const { return GlobalsGraph; }
-  void setGlobalsGraph(DSGraph *G) { GlobalsGraph = G; }
-
-  /// getGlobalECs - Return the set of equivalence classes that the global
-  /// variables in the program form.
-  EquivalenceClasses<GlobalValue*> &getGlobalECs() const {
-    return ScalarMap.getGlobalECs();
-  }
-
-  /// getTargetData - Return the TargetData object for the current target.
-  ///
-  const TargetData &getTargetData() const { return TD; }
-
-  /// setPrintAuxCalls - If you call this method, the auxillary call vector will
-  /// be printed instead of the standard call vector to the dot file.
-  ///
-  void setPrintAuxCalls() { PrintAuxCalls = true; }
-  bool shouldPrintAuxCalls() const { return PrintAuxCalls; }
-
-  /// node_iterator/begin/end - Iterate over all of the nodes in the graph.  Be
-  /// extremely careful with these methods because any merging of nodes could
-  /// cause the node to be removed from this list.  This means that if you are
-  /// iterating over nodes and doing something that could cause _any_ node to
-  /// merge, your node_iterators into this graph can be invalidated.
-  typedef NodeListTy::iterator node_iterator;
-  node_iterator node_begin() { return Nodes.begin(); }
-  node_iterator node_end()   { return Nodes.end(); }
-
-  typedef NodeListTy::const_iterator node_const_iterator;
-  node_const_iterator node_begin() const { return Nodes.begin(); }
-  node_const_iterator node_end()   const { return Nodes.end(); }
-
-  /// getFunctionNames - Return a space separated list of the name of the
-  /// functions in this graph (if any)
-  ///
-  std::string getFunctionNames() const;
-
-  /// addNode - Add a new node to the graph.
-  ///
-  void addNode(DSNode *N) { Nodes.push_back(N); }
-  void unlinkNode(DSNode *N) { Nodes.remove(N); }
-
-  /// getScalarMap - Get a map that describes what the nodes the scalars in this
-  /// function point to...
-  ///
-  ScalarMapTy &getScalarMap() { return ScalarMap; }
-  const ScalarMapTy &getScalarMap() const { return ScalarMap; }
-
-  /// getFunctionCalls - Return the list of call sites in the original local
-  /// graph...
-  ///
-  const std::list<DSCallSite> &getFunctionCalls() const { return FunctionCalls;}
-  std::list<DSCallSite> &getFunctionCalls() { return FunctionCalls;}
-
-  /// getAuxFunctionCalls - Get the call sites as modified by whatever passes
-  /// have been run.
-  ///
-  std::list<DSCallSite> &getAuxFunctionCalls() { return AuxFunctionCalls; }
-  const std::list<DSCallSite> &getAuxFunctionCalls() const {
-    return AuxFunctionCalls;
-  }
-
-  // Function Call iteration
-  typedef std::list<DSCallSite>::const_iterator fc_iterator;
-  fc_iterator fc_begin() const { return FunctionCalls.begin(); }
-  fc_iterator fc_end() const { return FunctionCalls.end(); }
-
-
-  // Aux Function Call iteration
-  typedef std::list<DSCallSite>::const_iterator afc_iterator;
-  afc_iterator afc_begin() const { return AuxFunctionCalls.begin(); }
-  afc_iterator afc_end() const { return AuxFunctionCalls.end(); }
-
-  /// getNodeForValue - Given a value that is used or defined in the body of the
-  /// current function, return the DSNode that it points to.
-  ///
-  DSNodeHandle &getNodeForValue(Value *V) { return ScalarMap[V]; }
-
-  const DSNodeHandle &getNodeForValue(Value *V) const {
-    ScalarMapTy::const_iterator I = ScalarMap.find(V);
-    assert(I != ScalarMap.end() &&
-           "Use non-const lookup function if node may not be in the map");
-    return I->second;
-  }
-
-  /// retnodes_* iterator methods: expose iteration over return nodes in the
-  /// graph, which are also the set of functions incorporated in this graph.
-  typedef ReturnNodesTy::const_iterator retnodes_iterator;
-  retnodes_iterator retnodes_begin() const { return ReturnNodes.begin(); }
-  retnodes_iterator retnodes_end() const { return ReturnNodes.end(); }
-
-
-  /// getReturnNodes - Return the mapping of functions to their return nodes for
-  /// this graph.
-  ///
-  const ReturnNodesTy &getReturnNodes() const { return ReturnNodes; }
-        ReturnNodesTy &getReturnNodes()       { return ReturnNodes; }
-
-  /// getReturnNodeFor - Return the return node for the specified function.
-  ///
-  DSNodeHandle &getReturnNodeFor(Function &F) {
-    ReturnNodesTy::iterator I = ReturnNodes.find(&F);
-    assert(I != ReturnNodes.end() && "F not in this DSGraph!");
-    return I->second;
-  }
-
-  const DSNodeHandle &getReturnNodeFor(Function &F) const {
-    ReturnNodesTy::const_iterator I = ReturnNodes.find(&F);
-    assert(I != ReturnNodes.end() && "F not in this DSGraph!");
-    return I->second;
-  }
-
-  /// containsFunction - Return true if this DSGraph contains information for
-  /// the specified function.
-  bool containsFunction(Function *F) const {
-    return ReturnNodes.count(F);
-  }
-
-  /// getGraphSize - Return the number of nodes in this graph.
-  ///
-  unsigned getGraphSize() const {
-    return Nodes.size();
-  }
-
-  /// addObjectToGraph - This method can be used to add global, stack, and heap
-  /// objects to the graph.  This can be used when updating DSGraphs due to the
-  /// introduction of new temporary objects.  The new object is not pointed to
-  /// and does not point to any other objects in the graph.  Note that this
-  /// method initializes the type of the DSNode to the declared type of the
-  /// object if UseDeclaredType is true, otherwise it leaves the node type as
-  /// void.
-  DSNode *addObjectToGraph(Value *Ptr, bool UseDeclaredType = true);
-
-
-  /// print - Print a dot graph to the specified ostream...
-  ///
-  void print(std::ostream &O) const;
-
-  /// dump - call print(std::cerr), for use from the debugger...
-  ///
-  void dump() const;
-
-  /// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
-  /// then cleanup.  For use from the debugger.
-  ///
-  void viewGraph() const;
-
-  void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
-
-  /// maskNodeTypes - Apply a mask to all of the node types in the graph.  This
-  /// is useful for clearing out markers like Incomplete.
-  ///
-  void maskNodeTypes(unsigned Mask) {
-    for (node_iterator I = node_begin(), E = node_end(); I != E; ++I)
-      I->maskNodeTypes(Mask);
-  }
-  void maskIncompleteMarkers() { maskNodeTypes(~DSNode::Incomplete); }
-
-  // markIncompleteNodes - Traverse the graph, identifying nodes that may be
-  // modified by other functions that have not been resolved yet.  This marks
-  // nodes that are reachable through three sources of "unknownness":
-  //   Global Variables, Function Calls, and Incoming Arguments
-  //
-  // For any node that may have unknown components (because something outside
-  // the scope of current analysis may have modified it), the 'Incomplete' flag
-  // is added to the NodeType.
-  //
-  enum MarkIncompleteFlags {
-    MarkFormalArgs = 1, IgnoreFormalArgs = 0,
-    IgnoreGlobals = 2, MarkGlobalsIncomplete = 0
-  };
-  void markIncompleteNodes(unsigned Flags);
-
-  // removeDeadNodes - Use a reachability analysis to eliminate subgraphs that
-  // are unreachable.  This often occurs because the data structure doesn't
-  // "escape" into it's caller, and thus should be eliminated from the caller's
-  // graph entirely.  This is only appropriate to use when inlining graphs.
-  //
-  enum RemoveDeadNodesFlags {
-    RemoveUnreachableGlobals = 1, KeepUnreachableGlobals = 0
-  };
-  void removeDeadNodes(unsigned Flags);
-
-  /// CloneFlags enum - Bits that may be passed into the cloneInto method to
-  /// specify how to clone the function graph.
-  enum CloneFlags {
-    StripAllocaBit        = 1 << 0, KeepAllocaBit     = 0,
-    DontCloneCallNodes    = 1 << 1, CloneCallNodes    = 0,
-    DontCloneAuxCallNodes = 1 << 2, CloneAuxCallNodes = 0,
-    StripModRefBits       = 1 << 3, KeepModRefBits    = 0,
-    StripIncompleteBit    = 1 << 4, KeepIncompleteBit = 0
-  };
-
-  void updateFromGlobalGraph();
-
-  /// computeNodeMapping - Given roots in two different DSGraphs, traverse the
-  /// nodes reachable from the two graphs, computing the mapping of nodes from
-  /// the first to the second graph.
-  ///
-  static void computeNodeMapping(const DSNodeHandle &NH1,
-                                 const DSNodeHandle &NH2, NodeMapTy &NodeMap,
-                                 bool StrictChecking = true);
-
-  /// computeGToGGMapping - Compute the mapping of nodes in the graph to nodes
-  /// in the globals graph.
-  void computeGToGGMapping(NodeMapTy &NodeMap);
-
-  /// computeGGToGMapping - Compute the mapping of nodes in the global
-  /// graph to nodes in this graph.
-  void computeGGToGMapping(InvNodeMapTy &InvNodeMap);
-
-  /// computeCalleeCallerMapping - Given a call from a function in the current
-  /// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the
-  /// mapping of nodes from the callee to nodes in the caller.
-  void computeCalleeCallerMapping(DSCallSite CS, const Function &Callee,
-                                  DSGraph &CalleeGraph, NodeMapTy &NodeMap);
-
-  /// spliceFrom - Logically perform the operation of cloning the RHS graph into
-  /// this graph, then clearing the RHS graph.  Instead of performing this as
-  /// two seperate operations, do it as a single, much faster, one.
-  ///
-  void spliceFrom(DSGraph &RHS);
-
-  /// cloneInto - Clone the specified DSGraph into the current graph.
-  ///
-  /// The CloneFlags member controls various aspects of the cloning process.
-  ///
-  void cloneInto(const DSGraph &G, unsigned CloneFlags = 0);
-
-  /// getFunctionArgumentsForCall - Given a function that is currently in this
-  /// graph, return the DSNodeHandles that correspond to the pointer-compatible
-  /// function arguments.  The vector is filled in with the return value (or
-  /// null if it is not pointer compatible), followed by all of the
-  /// pointer-compatible arguments.
-  void getFunctionArgumentsForCall(Function *F,
-                                   std::vector<DSNodeHandle> &Args) const;
-
-  /// mergeInGraph - This graph merges in the minimal number of
-  /// nodes from G2 into 'this' graph, merging the bindings specified by the
-  /// call site (in this graph) with the bindings specified by the vector in G2.
-  /// If the StripAlloca's argument is 'StripAllocaBit' then Alloca markers are
-  /// removed from nodes.
-  ///
-  void mergeInGraph(const DSCallSite &CS, std::vector<DSNodeHandle> &Args,
-                    const DSGraph &G2, unsigned CloneFlags);
-
-  /// mergeInGraph - This method is the same as the above method, but the
-  /// argument bindings are provided by using the formal arguments of F.
-  ///
-  void mergeInGraph(const DSCallSite &CS, Function &F, const DSGraph &Graph,
-                    unsigned CloneFlags);
-
-  /// getCallSiteForArguments - Get the arguments and return value bindings for
-  /// the specified function in the current graph.
-  ///
-  DSCallSite getCallSiteForArguments(Function &F) const;
-
-  /// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in
-  /// the context of this graph, return the DSCallSite for it.
-  DSCallSite getDSCallSiteForCallSite(CallSite CS) const;
-
-  // Methods for checking to make sure graphs are well formed...
-  void AssertNodeInGraph(const DSNode *N) const {
-    assert((!N || N->getParentGraph() == this) &&
-           "AssertNodeInGraph: Node is not in graph!");
-  }
-  void AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const;
-
-  void AssertCallSiteInGraph(const DSCallSite &CS) const;
-  void AssertCallNodesInGraph() const;
-  void AssertAuxCallNodesInGraph() const;
-
-  void AssertGraphOK() const;
-
-  /// removeTriviallyDeadNodes - After the graph has been constructed, this
-  /// method removes all unreachable nodes that are created because they got
-  /// merged with other nodes in the graph.  This is used as the first step of
-  /// removeDeadNodes.
-  ///
-  void removeTriviallyDeadNodes();
-};
-
-
-/// ReachabilityCloner - This class is used to incrementally clone and merge
-/// nodes from a non-changing source graph into a potentially mutating
-/// destination graph.  Nodes are only cloned over on demand, either in
-/// responds to a merge() or getClonedNH() call.  When a node is cloned over,
-/// all of the nodes reachable from it are automatically brought over as well.
-///
-class ReachabilityCloner {
-  DSGraph &Dest;
-  const DSGraph &Src;
-
-  /// BitsToKeep - These bits are retained from the source node when the
-  /// source nodes are merged into the destination graph.
-  unsigned BitsToKeep;
-  unsigned CloneFlags;
-
-  // NodeMap - A mapping from nodes in the source graph to the nodes that
-  // represent them in the destination graph.
-  DSGraph::NodeMapTy NodeMap;
-public:
-  ReachabilityCloner(DSGraph &dest, const DSGraph &src, unsigned cloneFlags)
-    : Dest(dest), Src(src), CloneFlags(cloneFlags) {
-    assert(&Dest != &Src && "Cannot clone from graph to same graph!");
-    BitsToKeep = ~DSNode::DEAD;
-    if (CloneFlags & DSGraph::StripAllocaBit)
-      BitsToKeep &= ~DSNode::AllocaNode;
-    if (CloneFlags & DSGraph::StripModRefBits)
-      BitsToKeep &= ~(DSNode::Modified | DSNode::Read);
-    if (CloneFlags & DSGraph::StripIncompleteBit)
-      BitsToKeep &= ~DSNode::Incomplete;
-  }
-
-  DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH);
-
-  void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH);
-
-  /// mergeCallSite - Merge the nodes reachable from the specified src call
-  /// site into the nodes reachable from DestCS.
-  ///
-  void mergeCallSite(DSCallSite &DestCS, const DSCallSite &SrcCS);
-
-  bool clonedAnyNodes() const { return !NodeMap.empty(); }
-
-  /// hasClonedNode - Return true if the specified node has been cloned from
-  /// the source graph into the destination graph.
-  bool hasClonedNode(const DSNode *N) {
-    return NodeMap.count(N);
-  }
-
-  void destroy() { NodeMap.clear(); }
-};
-
-} // End llvm namespace
-
-#endif
diff --git a/llvm/include/llvm/Analysis/DataStructure/DSGraphTraits.h b/llvm/include/llvm/Analysis/DataStructure/DSGraphTraits.h
deleted file mode 100644
index 789cf973d8ea..000000000000
--- a/llvm/include/llvm/Analysis/DataStructure/DSGraphTraits.h
+++ /dev/null
@@ -1,152 +0,0 @@
-//===- DSGraphTraits.h - Provide generic graph interface --------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file provides GraphTraits specializations for the DataStructure graph
-// nodes, allowing datastructure graphs to be processed by generic graph
-// algorithms.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSGRAPHTRAITS_H
-#define LLVM_ANALYSIS_DSGRAPHTRAITS_H
-
-#include "llvm/Analysis/DataStructure/DSGraph.h"
-#include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/iterator"
-#include "llvm/ADT/STLExtras.h"
-
-namespace llvm {
-
-template<typename NodeTy>
-class DSNodeIterator : public forward_iterator<const DSNode, ptrdiff_t> {
-  friend class DSNode;
-  NodeTy * const Node;
-  unsigned Offset;
-
-  typedef DSNodeIterator<NodeTy> _Self;
-
-  DSNodeIterator(NodeTy *N) : Node(N), Offset(0) {}   // begin iterator
-  DSNodeIterator(NodeTy *N, bool) : Node(N) {         // Create end iterator
-    if (N != 0) {
-      Offset = N->getNumLinks() << DS::PointerShift;
-      if (Offset == 0 && Node->getForwardNode() &&
-          Node->isDeadNode())        // Model Forward link
-        Offset += DS::PointerSize;
-    } else {
-      Offset = 0;
-    }
-  }
-public:
-  DSNodeIterator(const DSNodeHandle &NH)
-    : Node(NH.getNode()), Offset(NH.getOffset()) {}
-
-  bool operator==(const _Self& x) const {
-    return Offset == x.Offset;
-  }
-  bool operator!=(const _Self& x) const { return !operator==(x); }
-
-  const _Self &operator=(const _Self &I) {
-    assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
-    Offset = I.Offset;
-    return *this;
-  }
-
-  pointer operator*() const {
-    if (Node->isDeadNode())
-      return Node->getForwardNode();
-    else
-      return Node->getLink(Offset).getNode();
-  }
-  pointer operator->() const { return operator*(); }
-
-  _Self& operator++() {                // Preincrement
-    Offset += (1 << DS::PointerShift);
-    return *this;
-  }
-  _Self operator++(int) { // Postincrement
-    _Self tmp = *this; ++*this; return tmp;
-  }
-
-  unsigned getOffset() const { return Offset; }
-  const DSNode *getNode() const { return Node; }
-};
-
-// Provide iterators for DSNode...
-inline DSNode::iterator DSNode::begin() {
-  return DSNode::iterator(this);
-}
-inline DSNode::iterator DSNode::end() {
-  return DSNode::iterator(this, false);
-}
-inline DSNode::const_iterator DSNode::begin() const {
-  return DSNode::const_iterator(this);
-}
-inline DSNode::const_iterator DSNode::end() const {
-  return DSNode::const_iterator(this, false);
-}
-
-template <> struct GraphTraits<DSNode*> {
-  typedef DSNode NodeType;
-  typedef DSNode::iterator ChildIteratorType;
-
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
-  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
-};
-
-template <> struct GraphTraits<const DSNode*> {
-  typedef const DSNode NodeType;
-  typedef DSNode::const_iterator ChildIteratorType;
-
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
-  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
-};
-
-static       DSNode &dereference (      DSNode *N) { return *N; }
-
-template <> struct GraphTraits<DSGraph*> {
-  typedef DSNode NodeType;
-  typedef DSNode::iterator ChildIteratorType;
-
-  typedef std::pointer_to_unary_function<DSNode *, DSNode&> DerefFun;
-
-  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator;
-  static nodes_iterator nodes_begin(DSGraph *G) {
-    return map_iterator(G->node_begin(), DerefFun(dereference));
-  }
-  static nodes_iterator nodes_end(DSGraph *G) {
-    return map_iterator(G->node_end(), DerefFun(dereference));
-  }
-
-  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
-  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
-};
-
-template <> struct GraphTraits<const DSGraph*> {
-  typedef const DSNode NodeType;
-  typedef DSNode::const_iterator ChildIteratorType;
-
-  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  typedef DSGraph::node_const_iterator nodes_iterator;
-  static nodes_iterator nodes_begin(const DSGraph *G) {
-    return G->node_begin();
-  }
-  static nodes_iterator nodes_end(const DSGraph *G) {
-    return G->node_end();
-  }
-
-  static ChildIteratorType child_begin(const NodeType *N) { return N->begin(); }
-  static ChildIteratorType child_end(const NodeType *N) { return N->end(); }
-};
-
-} // End llvm namespace
-
-#endif
diff --git a/llvm/include/llvm/Analysis/DataStructure/DSNode.h b/llvm/include/llvm/Analysis/DataStructure/DSNode.h
deleted file mode 100644
index 45937a410622..000000000000
--- a/llvm/include/llvm/Analysis/DataStructure/DSNode.h
+++ /dev/null
@@ -1,507 +0,0 @@
-//===- DSNode.h - Node definition for datastructure graphs ------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Data structure graph nodes and some implementation of DSNodeHandle.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSNODE_H
-#define LLVM_ANALYSIS_DSNODE_H
-
-#include "llvm/Analysis/DataStructure/DSSupport.h"
-#include "llvm/ADT/hash_map"
-
-namespace llvm {
-
-template<typename BaseType>
-class DSNodeIterator;          // Data structure graph traversal iterator
-class TargetData;
-
-//===----------------------------------------------------------------------===//
-/// DSNode - Data structure node class
-///
-/// This class represents an untyped memory object of Size bytes.  It keeps
-/// track of any pointers that have been stored into the object as well as the
-/// different types represented in this object.
-///
-class DSNode {
-  /// NumReferrers - The number of DSNodeHandles pointing to this node... if
-  /// this is a forwarding node, then this is the number of node handles which
-  /// are still forwarding over us.
-  ///
-  unsigned NumReferrers;
-
-  /// ForwardNH - This NodeHandle contain the node (and offset into the node)
-  /// that this node really is.  When nodes get folded together, the node to be
-  /// eliminated has these fields filled in, otherwise ForwardNH.getNode() is
-  /// null.
-  ///
-  DSNodeHandle ForwardNH;
-
-  /// Next, Prev - These instance variables are used to keep the node on a
-  /// doubly-linked ilist in the DSGraph.
-  ///
-  DSNode *Next, *Prev;
-  friend struct ilist_traits<DSNode>;
-
-  /// Size - The current size of the node.  This should be equal to the size of
-  /// the current type record.
-  ///
-  unsigned Size;
-
-  /// ParentGraph - The graph this node is currently embedded into.
-  ///
-  DSGraph *ParentGraph;
-
-  /// Ty - Keep track of the current outer most type of this object, in addition
-  /// to whether or not it has been indexed like an array or not.  If the
-  /// isArray bit is set, the node cannot grow.
-  ///
-  const Type *Ty;                 // The type itself...
-
-  /// Links - Contains one entry for every sizeof(void*) bytes in this memory
-  /// object.  Note that if the node is not a multiple of size(void*) bytes
-  /// large, that there is an extra entry for the "remainder" of the node as
-  /// well.  For this reason, nodes of 1 byte in size do have one link.
-  ///
-  std::vector<DSNodeHandle> Links;
-
-  /// Globals - The list of global values that are merged into this node.
-  ///
-  std::vector<GlobalValue*> Globals;
-
-  void operator=(const DSNode &); // DO NOT IMPLEMENT
-  DSNode(const DSNode &);         // DO NOT IMPLEMENT
-public:
-  enum NodeTy {
-    ShadowNode  = 0,        // Nothing is known about this node...
-    AllocaNode  = 1 << 0,   // This node was allocated with alloca
-    HeapNode    = 1 << 1,   // This node was allocated with malloc
-    GlobalNode  = 1 << 2,   // This node was allocated by a global var decl
-    UnknownNode = 1 << 3,   // This node points to unknown allocated memory
-    Incomplete  = 1 << 4,   // This node may not be complete
-
-    Modified    = 1 << 5,   // This node is modified in this context
-    Read        = 1 << 6,   // This node is read in this context
-
-    Array       = 1 << 7,   // This node is treated like an array
-    //#ifndef NDEBUG
-    DEAD        = 1 << 8,   // This node is dead and should not be pointed to
-    //#endif
-
-    Composition = AllocaNode | HeapNode | GlobalNode | UnknownNode
-  };
-
-  /// NodeType - A union of the above bits.  "Shadow" nodes do not add any flags
-  /// to the nodes in the data structure graph, so it is possible to have nodes
-  /// with a value of 0 for their NodeType.
-  ///
-private:
-  unsigned short NodeType;
-public:
-
-  /// DSNode ctor - Create a node of the specified type, inserting it into the
-  /// specified graph.
-  ///
-  DSNode(const Type *T, DSGraph *G);
-
-  /// DSNode "copy ctor" - Copy the specified node, inserting it into the
-  /// specified graph.  If NullLinks is true, then null out all of the links,
-  /// but keep the same number of them.  This can be used for efficiency if the
-  /// links are just going to be clobbered anyway.
-  ///
-  DSNode(const DSNode &, DSGraph *G, bool NullLinks = false);
-
-  ~DSNode() {
-    dropAllReferences();
-    assert(hasNoReferrers() && "Referrers to dead node exist!");
-  }
-
-  // Iterator for graph interface... Defined in DSGraphTraits.h
-  typedef DSNodeIterator<DSNode> iterator;
-  typedef DSNodeIterator<const DSNode> const_iterator;
-  inline iterator begin();
-  inline iterator end();
-  inline const_iterator begin() const;
-  inline const_iterator end() const;
-
-  //===--------------------------------------------------
-  // Accessors
-
-  /// getSize - Return the maximum number of bytes occupied by this object...
-  ///
-  unsigned getSize() const { return Size; }
-
-  /// getType - Return the node type of this object...
-  ///
-  const Type *getType() const { return Ty; }
-
-  bool isArray() const { return NodeType & Array; }
-
-  /// hasNoReferrers - Return true if nothing is pointing to this node at all.
-  ///
-  bool hasNoReferrers() const { return getNumReferrers() == 0; }
-
-  /// getNumReferrers - This method returns the number of referrers to the
-  /// current node.  Note that if this node is a forwarding node, this will
-  /// return the number of nodes forwarding over the node!
-  unsigned getNumReferrers() const { return NumReferrers; }
-
-  DSGraph *getParentGraph() const { return ParentGraph; }
-  void setParentGraph(DSGraph *G) { ParentGraph = G; }
-
-
-  /// getTargetData - Get the target data object used to construct this node.
-  ///
-  const TargetData &getTargetData() const;
-
-  /// getForwardNode - This method returns the node that this node is forwarded
-  /// to, if any.
-  ///
-  DSNode *getForwardNode() const { return ForwardNH.getNode(); }
-
-  /// isForwarding - Return true if this node is forwarding to another.
-  ///
-  bool isForwarding() const { return !ForwardNH.isNull(); }
-
-  /// stopForwarding - When the last reference to this forwarding node has been
-  /// dropped, delete the node.
-  ///
-  void stopForwarding() {
-    assert(isForwarding() &&
-           "Node isn't forwarding, cannot stopForwarding()!");
-    ForwardNH.setTo(0, 0);
-    assert(ParentGraph == 0 &&
-           "Forwarding nodes must have been removed from graph!");
-    delete this;
-  }
-
-  /// hasLink - Return true if this memory object has a link in slot LinkNo
-  ///
-  bool hasLink(unsigned Offset) const {
-    assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
-           "Pointer offset not aligned correctly!");
-    unsigned Index = Offset >> DS::PointerShift;
-    assert(Index < Links.size() && "Link index is out of range!");
-    return Links[Index].getNode();
-  }
-
-  /// getLink - Return the link at the specified offset.
-  ///
-  DSNodeHandle &getLink(unsigned Offset) {
-    assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
-           "Pointer offset not aligned correctly!");
-    unsigned Index = Offset >> DS::PointerShift;
-    assert(Index < Links.size() && "Link index is out of range!");
-    return Links[Index];
-  }
-  const DSNodeHandle &getLink(unsigned Offset) const {
-    assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
-           "Pointer offset not aligned correctly!");
-    unsigned Index = Offset >> DS::PointerShift;
-    assert(Index < Links.size() && "Link index is out of range!");
-    return Links[Index];
-  }
-
-  /// getNumLinks - Return the number of links in a node...
-  ///
-  unsigned getNumLinks() const { return Links.size(); }
-
-  /// edge_* - Provide iterators for accessing outgoing edges.  Some outgoing
-  /// edges may be null.
-  typedef std::vector<DSNodeHandle>::iterator edge_iterator;
-  typedef std::vector<DSNodeHandle>::const_iterator const_edge_iterator;
-  edge_iterator edge_begin() { return Links.begin(); }
-  edge_iterator edge_end() { return Links.end(); }
-  const_edge_iterator edge_begin() const { return Links.begin(); }
-  const_edge_iterator edge_end() const { return Links.end(); }
-
-
-  /// mergeTypeInfo - This method merges the specified type into the current
-  /// node at the specified offset.  This may update the current node's type
-  /// record if this gives more information to the node, it may do nothing to
-  /// the node if this information is already known, or it may merge the node
-  /// completely (and return true) if the information is incompatible with what
-  /// is already known.
-  ///
-  /// This method returns true if the node is completely folded, otherwise
-  /// false.
-  ///
-  bool mergeTypeInfo(const Type *Ty, unsigned Offset,
-                     bool FoldIfIncompatible = true);
-
-  /// foldNodeCompletely - If we determine that this node has some funny
-  /// behavior happening to it that we cannot represent, we fold it down to a
-  /// single, completely pessimistic, node.  This node is represented as a
-  /// single byte with a single TypeEntry of "void" with isArray = true.
-  ///
-  void foldNodeCompletely();
-
-  /// isNodeCompletelyFolded - Return true if this node has been completely
-  /// folded down to something that can never be expanded, effectively losing
-  /// all of the field sensitivity that may be present in the node.
-  ///
-  bool isNodeCompletelyFolded() const;
-
-  /// setLink - Set the link at the specified offset to the specified
-  /// NodeHandle, replacing what was there.  It is uncommon to use this method,
-  /// instead one of the higher level methods should be used, below.
-  ///
-  void setLink(unsigned Offset, const DSNodeHandle &NH) {
-    assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
-           "Pointer offset not aligned correctly!");
-    unsigned Index = Offset >> DS::PointerShift;
-    assert(Index < Links.size() && "Link index is out of range!");
-    Links[Index] = NH;
-  }
-
-  /// getPointerSize - Return the size of a pointer for the current target.
-  ///
-  unsigned getPointerSize() const { return DS::PointerSize; }
-
-  /// addEdgeTo - Add an edge from the current node to the specified node.  This
-  /// can cause merging of nodes in the graph.
-  ///
-  void addEdgeTo(unsigned Offset, const DSNodeHandle &NH);
-
-  /// mergeWith - Merge this node and the specified node, moving all links to
-  /// and from the argument node into the current node, deleting the node
-  /// argument.  Offset indicates what offset the specified node is to be merged
-  /// into the current node.
-  ///
-  /// The specified node may be a null pointer (in which case, nothing happens).
-  ///
-  void mergeWith(const DSNodeHandle &NH, unsigned Offset);
-
-  /// addGlobal - Add an entry for a global value to the Globals list.  This
-  /// also marks the node with the 'G' flag if it does not already have it.
-  ///
-  void addGlobal(GlobalValue *GV);
-
-  /// removeGlobal - Remove the specified global that is explicitly in the
-  /// globals list.
-  void removeGlobal(GlobalValue *GV);
-
-  void mergeGlobals(const std::vector<GlobalValue*> &RHS);
-  void clearGlobals() { std::vector<GlobalValue*>().swap(Globals); }
-
-  /// getGlobalsList - Return the set of global leaders that are represented by
-  /// this node.  Note that globals that are in this equivalence class but are
-  /// not leaders are not returned: for that, use addFullGlobalsList().
-  const std::vector<GlobalValue*> &getGlobalsList() const { return Globals; }
-
-  /// addFullGlobalsList - Compute the full set of global values that are
-  /// represented by this node.  Unlike getGlobalsList(), this requires fair
-  /// amount of work to compute, so don't treat this method call as free.
-  void addFullGlobalsList(std::vector<GlobalValue*> &List) const;
-
-  /// addFullFunctionList - Identical to addFullGlobalsList, but only return the
-  /// functions in the full list.
-  void addFullFunctionList(std::vector<Function*> &List) const;
-
-  /// globals_iterator/begin/end - Provide iteration methods over the global
-  /// value leaders set that is merged into this node.  Like the getGlobalsList
-  /// method, these iterators do not return globals that are part of the
-  /// equivalence classes for globals in this node, but aren't leaders.
-  typedef std::vector<GlobalValue*>::const_iterator globals_iterator;
-  globals_iterator globals_begin() const { return Globals.begin(); }
-  globals_iterator globals_end() const { return Globals.end(); }
-
-
-  /// maskNodeTypes - Apply a mask to the node types bitfield.
-  ///
-  void maskNodeTypes(unsigned Mask) {
-    NodeType &= Mask;
-  }
-
-  void mergeNodeFlags(unsigned RHS) {
-    NodeType |= RHS;
-  }
-
-  /// getNodeFlags - Return all of the flags set on the node.  If the DEAD flag
-  /// is set, hide it from the caller.
-  ///
-  unsigned getNodeFlags() const { return NodeType & ~DEAD; }
-
-  bool isAllocaNode()  const { return NodeType & AllocaNode; }
-  bool isHeapNode()    const { return NodeType & HeapNode; }
-  bool isGlobalNode()  const { return NodeType & GlobalNode; }
-  bool isUnknownNode() const { return NodeType & UnknownNode; }
-
-  bool isModified() const   { return NodeType & Modified; }
-  bool isRead() const       { return NodeType & Read; }
-
-  bool isIncomplete() const { return NodeType & Incomplete; }
-  bool isComplete() const   { return !isIncomplete(); }
-  bool isDeadNode() const   { return NodeType & DEAD; }
-
-  DSNode *setAllocaNodeMarker()  { NodeType |= AllocaNode;  return this; }
-  DSNode *setHeapNodeMarker()    { NodeType |= HeapNode;    return this; }
-  DSNode *setGlobalNodeMarker()  { NodeType |= GlobalNode;  return this; }
-  DSNode *setUnknownNodeMarker() { NodeType |= UnknownNode; return this; }
-
-  DSNode *setIncompleteMarker() { NodeType |= Incomplete; return this; }
-  DSNode *setModifiedMarker()   { NodeType |= Modified;   return this; }
-  DSNode *setReadMarker()       { NodeType |= Read;       return this; }
-  DSNode *setArrayMarker()      { NodeType |= Array; return this; }
-
-  void makeNodeDead() {
-    Globals.clear();
-    assert(hasNoReferrers() && "Dead node shouldn't have refs!");
-    NodeType = DEAD;
-  }
-
-  /// forwardNode - Mark this node as being obsolete, and all references to it
-  /// should be forwarded to the specified node and offset.
-  ///
-  void forwardNode(DSNode *To, unsigned Offset);
-
-  void print(std::ostream &O, const DSGraph *G) const;
-  void dump() const;
-
-  void assertOK() const;
-
-  void dropAllReferences() {
-    Links.clear();
-    if (isForwarding())
-      ForwardNH.setTo(0, 0);
-  }
-
-  /// remapLinks - Change all of the Links in the current node according to the
-  /// specified mapping.
-  ///
-  void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap);
-
-  /// markReachableNodes - This method recursively traverses the specified
-  /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
-  /// adds to the set, which allows it to only traverse visited nodes once.
-  ///
-  void markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const;
-
-private:
-  friend class DSNodeHandle;
-
-  // static mergeNodes - Helper for mergeWith()
-  static void MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH);
-};
-
-//===----------------------------------------------------------------------===//
-// Define the ilist_traits specialization for the DSGraph ilist.
-//
-template<>
-struct ilist_traits<DSNode> {
-  static DSNode *getPrev(const DSNode *N) { return N->Prev; }
-  static DSNode *getNext(const DSNode *N) { return N->Next; }
-
-  static void setPrev(DSNode *N, DSNode *Prev) { N->Prev = Prev; }
-  static void setNext(DSNode *N, DSNode *Next) { N->Next = Next; }
-
-  static DSNode *createSentinel() { return new DSNode(0,0); }
-  static void destroySentinel(DSNode *N) { delete N; }
-  //static DSNode *createNode(const DSNode &V) { return new DSNode(V); }
-
-
-  void addNodeToList(DSNode *NTy) {}
-  void removeNodeFromList(DSNode *NTy) {}
-  void transferNodesFromList(iplist<DSNode, ilist_traits> &L2,
-                             ilist_iterator<DSNode> first,
-                             ilist_iterator<DSNode> last) {}
-};
-
-template<>
-struct ilist_traits<const DSNode> : public ilist_traits<DSNode> {};
-
-//===----------------------------------------------------------------------===//
-// Define inline DSNodeHandle functions that depend on the definition of DSNode
-//
-inline DSNode *DSNodeHandle::getNode() const {
-  // Disabling this assertion because it is failing on a "magic" struct
-  // in named (from bind).  The fourth field is an array of length 0,
-  // presumably used to create struct instances of different sizes.
-  // In a variable length struct, Offset could exceed Size when getNode()
-  // is called before such a node is folded. In this case, the DS Analysis now 
-  // correctly folds this node after calling getNode.
-  /*  assert((!N ||
-          N->isNodeCompletelyFolded() ||
-          (N->Size == 0 && Offset == 0) ||
-          (int(Offset) >= 0 && Offset < N->Size) ||
-          (int(Offset) < 0 && -int(Offset) < int(N->Size)) ||
-          N->isForwarding()) && "Node handle offset out of range!");
-  */
-  if (N == 0 || !N->isForwarding())
-    return N;
-
-  return HandleForwarding();
-}
-
-inline void DSNodeHandle::setTo(DSNode *n, unsigned NewOffset) const {
-  assert(!n || !n->isForwarding() && "Cannot set node to a forwarded node!");
-  if (N) getNode()->NumReferrers--;
-  N = n;
-  Offset = NewOffset;
-  if (N) {
-    N->NumReferrers++;
-    if (Offset >= N->Size) {
-      assert((Offset == 0 || N->Size == 1) &&
-             "Pointer to non-collapsed node with invalid offset!");
-      Offset = 0;
-    }
-  }
-  assert(!N || ((N->NodeType & DSNode::DEAD) == 0));
-  assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
-          N->isForwarding()) && "Node handle offset out of range!");
-}
-
-inline bool DSNodeHandle::hasLink(unsigned Num) const {
-  assert(N && "DSNodeHandle does not point to a node yet!");
-  return getNode()->hasLink(Num+Offset);
-}
-
-
-/// getLink - Treat this current node pointer as a pointer to a structure of
-/// some sort.  This method will return the pointer a mem[this+Num]
-///
-inline const DSNodeHandle &DSNodeHandle::getLink(unsigned Off) const {
-  assert(N && "DSNodeHandle does not point to a node yet!");
-  return getNode()->getLink(Offset+Off);
-}
-inline DSNodeHandle &DSNodeHandle::getLink(unsigned Off) {
-  assert(N && "DSNodeHandle does not point to a node yet!");
-  return getNode()->getLink(Off+Offset);
-}
-
-inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) {
-  assert(N && "DSNodeHandle does not point to a node yet!");
-  getNode()->setLink(Off+Offset, NH);
-}
-
-/// addEdgeTo - Add an edge from the current node to the specified node.  This
-/// can cause merging of nodes in the graph.
-///
-inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) {
-  assert(N && "DSNodeHandle does not point to a node yet!");
-  getNode()->addEdgeTo(Off+Offset, Node);
-}
-
-/// mergeWith - Merge the logical node pointed to by 'this' with the node
-/// pointed to by 'N'.
-///
-inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) const {
-  if (!isNull())
-    getNode()->mergeWith(Node, Offset);
-  else {   // No node to merge with, so just point to Node
-    Offset = 0;
-    DSNode *NN = Node.getNode();
-    setTo(NN, Node.getOffset());
-  }
-}
-
-} // End llvm namespace
-
-#endif
diff --git a/llvm/include/llvm/Analysis/DataStructure/DSSupport.h b/llvm/include/llvm/Analysis/DataStructure/DSSupport.h
deleted file mode 100644
index dc4c31f60a49..000000000000
--- a/llvm/include/llvm/Analysis/DataStructure/DSSupport.h
+++ /dev/null
@@ -1,338 +0,0 @@
-//===- DSSupport.h - Support for datastructure graphs -----------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Support for graph nodes, call sites, and types.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSSUPPORT_H
-#define LLVM_ANALYSIS_DSSUPPORT_H
-
-#include <functional>
-#include "llvm/ADT/hash_map"
-#include "llvm/ADT/hash_set"
-#include "llvm/Support/CallSite.h"
-
-namespace llvm {
-
-class Function;
-class CallInst;
-class Value;
-class GlobalValue;
-class Type;
-
-class DSNode;                  // Each node in the graph
-class DSGraph;                 // A graph for a function
-class ReachabilityCloner;
-
-namespace DS { // FIXME: After the paper, this should get cleaned up
-  enum { PointerShift = 2,     // 64bit ptrs = 3, 32 bit ptrs = 2
-         PointerSize = 1 << PointerShift
-  };
-
-  /// isPointerType - Return true if this first class type is big enough to hold
-  /// a pointer.
-  ///
-  bool isPointerType(const Type *Ty);
-}
-
-//===----------------------------------------------------------------------===//
-/// DSNodeHandle - Implement a "handle" to a data structure node that takes care
-/// of all of the add/un'refing of the node to prevent the backpointers in the
-/// graph from getting out of date.  This class represents a "pointer" in the
-/// graph, whose destination is an indexed offset into a node.
-///
-/// Note: some functions that are marked as inline in DSNodeHandle are actually
-/// defined in DSNode.h because they need knowledge of DSNode operation. Putting
-/// them in a CPP file wouldn't help making them inlined and keeping DSNode and
-/// DSNodeHandle (and friends) in one file complicates things.
-///
-class DSNodeHandle {
-  mutable DSNode *N;
-  mutable unsigned Offset;
-  void operator==(const DSNode *N);  // DISALLOW, use to promote N to nodehandle
-public:
-  // Allow construction, destruction, and assignment...
-  DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(0) {
-    setTo(n, offs);
-  }
-  DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) {
-    DSNode *NN = H.getNode();
-    setTo(NN, H.Offset);  // Must read offset AFTER the getNode()
-  }
-  ~DSNodeHandle() { setTo(0, 0); }
-  DSNodeHandle &operator=(const DSNodeHandle &H) {
-    if (&H == this) return *this;  // Don't set offset to 0 if self assigning.
-    DSNode *NN = H.getNode();  // Call getNode() before .Offset
-    setTo(NN, H.Offset);
-    return *this;
-  }
-
-  bool operator<(const DSNodeHandle &H) const {  // Allow sorting
-    return getNode() < H.getNode() || (N == H.N && Offset < H.Offset);
-  }
-  bool operator>(const DSNodeHandle &H) const { return H < *this; }
-  bool operator==(const DSNodeHandle &H) const { // Allow comparison
-    // getNode can change the offset, so we must call getNode() first.
-    return getNode() == H.getNode() && Offset == H.Offset;
-  }
-  bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
-
-  inline void swap(DSNodeHandle &NH) {
-    std::swap(Offset, NH.Offset);
-    std::swap(N, NH.N);
-  }
-
-  /// isNull - Check to see if getNode() == 0, without going through the trouble
-  /// of checking to see if we are forwarding...
-  ///
-  bool isNull() const { return N == 0; }
-
-  // Allow explicit conversion to DSNode...
-  inline DSNode *getNode() const;  // Defined inline in DSNode.h
-  unsigned getOffset() const {
-    assert(!isForwarding() && "This is a forwarding NH, call getNode() first!");
-    return Offset;
-  }
-
-  void setOffset(unsigned O) {
-    assert(!isForwarding() && "This is a forwarding NH, call getNode() first!");
-    //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
-    //       !N->ForwardNH.isNull()) && "Node handle offset out of range!");
-    //assert((!N || O < N->Size || (N->Size == 0 && O == 0) ||
-    //       !N->ForwardNH.isNull()) && "Node handle offset out of range!");
-    Offset = O;
-  }
-
-  inline void setTo(DSNode *N, unsigned O) const; // Defined inline in DSNode.h
-
-  void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
-  void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
-
-  /// mergeWith - Merge the logical node pointed to by 'this' with the node
-  /// pointed to by 'N'.
-  ///
-  void mergeWith(const DSNodeHandle &N) const;
-
-  /// hasLink - Return true if there is a link at the specified offset...
-  ///
-  inline bool hasLink(unsigned Num) const;
-
-  /// getLink - Treat this current node pointer as a pointer to a structure of
-  /// some sort.  This method will return the pointer a mem[this+Num]
-  ///
-  inline const DSNodeHandle &getLink(unsigned Num) const;
-  inline DSNodeHandle &getLink(unsigned Num);
-
-  inline void setLink(unsigned Num, const DSNodeHandle &NH);
-private:
-  DSNode *HandleForwarding() const;
-
-  /// isForwarding - Return true if this NodeHandle is forwarding to another
-  /// one.
-  bool isForwarding() const;
-};
-
-} // End llvm namespace
-
-namespace std {
-  template<>
-  inline void swap<llvm::DSNodeHandle>(llvm::DSNodeHandle &NH1, llvm::DSNodeHandle &NH2) { NH1.swap(NH2); }
-}
-
-namespace HASH_NAMESPACE {
-  // Provide a hash function for arbitrary pointers...
-  template <> struct hash<llvm::DSNodeHandle> {
-    inline size_t operator()(const llvm::DSNodeHandle &Val) const {
-      return hash<void*>()(Val.getNode()) ^ Val.getOffset();
-    }
-  };
-}
-
-namespace llvm {
-
-//===----------------------------------------------------------------------===//
-/// DSCallSite - Representation of a call site via its call instruction,
-/// the DSNode handle for the callee function (or function pointer), and
-/// the DSNode handles for the function arguments.
-///
-class DSCallSite {
-  CallSite     Site;                 // Actual call site
-  Function    *CalleeF;              // The function called (direct call)
-  DSNodeHandle CalleeN;              // The function node called (indirect call)
-  DSNodeHandle RetVal;               // Returned value
-  std::vector<DSNodeHandle> CallArgs;// The pointer arguments
-
-  static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
-                     const hash_map<const DSNode*, DSNode*> &NodeMap) {
-    if (DSNode *N = Src.getNode()) {
-      hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
-      assert(I != NodeMap.end() && "Node not in mapping!");
-      NH.setTo(I->second, Src.getOffset());
-    }
-  }
-
-  static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
-                     const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
-    if (DSNode *N = Src.getNode()) {
-      hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
-      assert(I != NodeMap.end() && "Node not in mapping!");
-
-      DSNode *NN = I->second.getNode(); // Call getNode before getOffset()
-      NH.setTo(NN, Src.getOffset()+I->second.getOffset());
-    }
-  }
-
-  static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
-                     ReachabilityCloner &RC);
-
-
-  DSCallSite();                         // DO NOT IMPLEMENT
-public:
-  /// Constructor.  Note - This ctor destroys the argument vector passed in.  On
-  /// exit, the argument vector is empty.
-  ///
-  DSCallSite(CallSite CS, const DSNodeHandle &rv, DSNode *Callee,
-             std::vector<DSNodeHandle> &Args)
-    : Site(CS), CalleeF(0), CalleeN(Callee), RetVal(rv) {
-    assert(Callee && "Null callee node specified for call site!");
-    Args.swap(CallArgs);
-  }
-  DSCallSite(CallSite CS, const DSNodeHandle &rv, Function *Callee,
-             std::vector<DSNodeHandle> &Args)
-    : Site(CS), CalleeF(Callee), RetVal(rv) {
-    assert(Callee && "Null callee function specified for call site!");
-    Args.swap(CallArgs);
-  }
-
-  DSCallSite(const DSCallSite &DSCS)   // Simple copy ctor
-    : Site(DSCS.Site), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN),
-      RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {}
-
-  /// Mapping copy constructor - This constructor takes a preexisting call site
-  /// to copy plus a map that specifies how the links should be transformed.
-  /// This is useful when moving a call site from one graph to another.
-  ///
-  template<typename MapTy>
-  DSCallSite(const DSCallSite &FromCall, MapTy &NodeMap) {
-    Site = FromCall.Site;
-    InitNH(RetVal, FromCall.RetVal, NodeMap);
-    InitNH(CalleeN, FromCall.CalleeN, NodeMap);
-    CalleeF = FromCall.CalleeF;
-
-    CallArgs.resize(FromCall.CallArgs.size());
-    for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
-      InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
-  }
-
-  const DSCallSite &operator=(const DSCallSite &RHS) {
-    Site     = RHS.Site;
-    CalleeF  = RHS.CalleeF;
-    CalleeN  = RHS.CalleeN;
-    RetVal   = RHS.RetVal;
-    CallArgs = RHS.CallArgs;
-    return *this;
-  }
-
-  /// isDirectCall - Return true if this call site is a direct call of the
-  /// function specified by getCalleeFunc.  If not, it is an indirect call to
-  /// the node specified by getCalleeNode.
-  ///
-  bool isDirectCall() const { return CalleeF != 0; }
-  bool isIndirectCall() const { return !isDirectCall(); }
-
-
-  // Accessor functions...
-  Function           &getCaller()     const;
-  CallSite            getCallSite()   const { return Site; }
-        DSNodeHandle &getRetVal()           { return RetVal; }
-  const DSNodeHandle &getRetVal()     const { return RetVal; }
-
-  DSNode *getCalleeNode() const {
-    assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode();
-  }
-  Function *getCalleeFunc() const {
-    assert(!CalleeN.getNode() && CalleeF); return CalleeF;
-  }
-
-  unsigned getNumPtrArgs() const { return CallArgs.size(); }
-
-  DSNodeHandle &getPtrArg(unsigned i) {
-    assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
-    return CallArgs[i];
-  }
-  const DSNodeHandle &getPtrArg(unsigned i) const {
-    assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
-    return CallArgs[i];
-  }
-
-  void addPtrArg(const DSNodeHandle &NH) {
-    CallArgs.push_back(NH);
-  }
-
-  void swap(DSCallSite &CS) {
-    if (this != &CS) {
-      std::swap(Site, CS.Site);
-      std::swap(RetVal, CS.RetVal);
-      std::swap(CalleeN, CS.CalleeN);
-      std::swap(CalleeF, CS.CalleeF);
-      std::swap(CallArgs, CS.CallArgs);
-    }
-  }
-
-  /// mergeWith - Merge the return value and parameters of the these two call
-  /// sites.
-  ///
-  void mergeWith(DSCallSite &CS) {
-    getRetVal().mergeWith(CS.getRetVal());
-    unsigned MinArgs = getNumPtrArgs();
-    if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs();
-
-    for (unsigned a = 0; a != MinArgs; ++a)
-      getPtrArg(a).mergeWith(CS.getPtrArg(a));
-
-    for (unsigned a = MinArgs, e = CS.getNumPtrArgs(); a != e; ++a)
-      CallArgs.push_back(CS.getPtrArg(a));
-  }
-
-  /// markReachableNodes - This method recursively traverses the specified
-  /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
-  /// adds to the set, which allows it to only traverse visited nodes once.
-  ///
-  void markReachableNodes(hash_set<const DSNode*> &Nodes) const;
-
-  bool operator<(const DSCallSite &CS) const {
-    if (isDirectCall()) {      // This must sort by callee first!
-      if (CS.isIndirectCall()) return true;
-      if (CalleeF < CS.CalleeF) return true;
-      if (CalleeF > CS.CalleeF) return false;
-    } else {
-      if (CS.isDirectCall()) return false;
-      if (CalleeN < CS.CalleeN) return true;
-      if (CalleeN > CS.CalleeN) return false;
-    }
-    if (RetVal < CS.RetVal) return true;
-    if (RetVal > CS.RetVal) return false;
-    return CallArgs < CS.CallArgs;
-  }
-
-  bool operator==(const DSCallSite &CS) const {
-    return CalleeF == CS.CalleeF && CalleeN == CS.CalleeN &&
-           RetVal == CS.RetVal && CallArgs == CS.CallArgs;
-  }
-};
-
-} // End llvm namespace
-
-namespace std {
-  template<>
-  inline void swap<llvm::DSCallSite>(llvm::DSCallSite &CS1,
-                                     llvm::DSCallSite &CS2) { CS1.swap(CS2); }
-}
-#endif
diff --git a/llvm/include/llvm/Analysis/DataStructure/DataStructure.h b/llvm/include/llvm/Analysis/DataStructure/DataStructure.h
deleted file mode 100644
index dccb62e02012..000000000000
--- a/llvm/include/llvm/Analysis/DataStructure/DataStructure.h
+++ /dev/null
@@ -1,441 +0,0 @@
-//===- DataStructure.h - Build data structure graphs ------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Implement the LLVM data structure analysis library.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
-#define LLVM_ANALYSIS_DATA_STRUCTURE_H
-
-#include "llvm/Pass.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/Support/CallSite.h"
-#include "llvm/ADT/hash_map"
-#include "llvm/ADT/hash_set"
-#include "llvm/ADT/EquivalenceClasses.h"
-
-namespace llvm {
-
-class Type;
-class Instruction;
-class GlobalValue;
-class DSGraph;
-class DSCallSite;
-class DSNode;
-class DSNodeHandle;
-
-FunctionPass *createDataStructureStatsPass();
-FunctionPass *createDataStructureGraphCheckerPass();
-
-
-// FIXME: move this stuff to a private header
-namespace DataStructureAnalysis {
-  /// isPointerType - Return true if this first class type is big enough to hold
-  /// a pointer.
-  ///
-  bool isPointerType(const Type *Ty);
-}
-
-
-// LocalDataStructures - The analysis that computes the local data structure
-// graphs for all of the functions in the program.
-//
-// FIXME: This should be a Function pass that can be USED by a Pass, and would
-// be automatically preserved.  Until we can do that, this is a Pass.
-//
-class LocalDataStructures : public ModulePass {
-  // DSInfo, one graph for each function
-  hash_map<Function*, DSGraph*> DSInfo;
-  DSGraph *GlobalsGraph;
-
-  /// GlobalECs - The equivalence classes for each global value that is merged
-  /// with other global values in the DSGraphs.
-  EquivalenceClasses<GlobalValue*> GlobalECs;
-public:
-  ~LocalDataStructures() { releaseMemory(); }
-
-  virtual bool runOnModule(Module &M);
-
-  bool hasGraph(const Function &F) const {
-    return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
-  }
-
-  /// getDSGraph - Return the data structure graph for the specified function.
-  ///
-  DSGraph &getDSGraph(const Function &F) const {
-    hash_map<Function*, DSGraph*>::const_iterator I =
-      DSInfo.find(const_cast<Function*>(&F));
-    assert(I != DSInfo.end() && "Function not in module!");
-    return *I->second;
-  }
-
-  DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
-
-  EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
-
-  /// print - Print out the analysis results...
-  ///
-  void print(std::ostream &O, const Module *M) const;
-
-  /// releaseMemory - if the pass pipeline is done with this pass, we can
-  /// release our memory...
-  ///
-  virtual void releaseMemory();
-
-  /// getAnalysisUsage - This obviously provides a data structure graph.
-  ///
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-    AU.addRequired<TargetData>();
-  }
-};
-
-
-/// BUDataStructures - The analysis that computes the interprocedurally closed
-/// data structure graphs for all of the functions in the program.  This pass
-/// only performs a "Bottom Up" propagation (hence the name).
-///
-class BUDataStructures : public ModulePass {
-protected:
-  // DSInfo, one graph for each function
-  hash_map<Function*, DSGraph*> DSInfo;
-  DSGraph *GlobalsGraph;
-  std::set<std::pair<Instruction*, Function*> > ActualCallees;
-
-  // This map is only maintained during construction of BU Graphs
-  std::map<std::vector<Function*>,
-           std::pair<DSGraph*, std::vector<DSNodeHandle> > > *IndCallGraphMap;
-
-  /// GlobalECs - The equivalence classes for each global value that is merged
-  /// with other global values in the DSGraphs.
-  EquivalenceClasses<GlobalValue*> GlobalECs;
-
-  std::map<CallSite, std::vector<Function*> > AlreadyInlined;
-
-public:
-  ~BUDataStructures() { releaseMyMemory(); }
-
-  virtual bool runOnModule(Module &M);
-
-  bool hasGraph(const Function &F) const {
-    return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
-  }
-
-  /// getDSGraph - Return the data structure graph for the specified function.
-  ///
-  DSGraph &getDSGraph(const Function &F) const {
-    hash_map<Function*, DSGraph*>::const_iterator I =
-      DSInfo.find(const_cast<Function*>(&F));
-    if (I != DSInfo.end())
-      return *I->second;
-    return const_cast<BUDataStructures*>(this)->
-                   CreateGraphForExternalFunction(F);
-  }
-  
-  /// DSGraphExists - Is the DSGraph computed for this function?
-  ///
-  bool doneDSGraph(const Function *F) const {
-    return (DSInfo.find(const_cast<Function*>(F)) != DSInfo.end());
-  }
-
-  DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
-
-  EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
-
-  DSGraph &CreateGraphForExternalFunction(const Function &F);
-
-  /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
-  /// These correspond to the interfaces defined in the AliasAnalysis class.
-  void deleteValue(Value *V);
-  void copyValue(Value *From, Value *To);
-
-  /// print - Print out the analysis results...
-  ///
-  void print(std::ostream &O, const Module *M) const;
-
-  // FIXME: Once the pass manager is straightened out, rename this to
-  // releaseMemory.
-  void releaseMyMemory();
-
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-    AU.addRequired<LocalDataStructures>();
-  }
-
-  typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy;
-  const ActualCalleesTy &getActualCallees() const {
-    return ActualCallees;
-  }
-
-  typedef ActualCalleesTy::const_iterator callee_iterator;
-  callee_iterator callee_begin(Instruction *I) const {
-    return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
-  }
-
-  callee_iterator callee_end(Instruction *I) const {
-    I = (Instruction*)((char*)I + 1);
-    return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
-  }
-
-private:
-  void calculateGraph(DSGraph &G);
-
-  DSGraph &getOrCreateGraph(Function *F);
-
-  unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
-                           unsigned &NextID,
-                           hash_map<Function*, unsigned> &ValMap);
-};
-
-
-/// TDDataStructures - Analysis that computes new data structure graphs
-/// for each function using the closed graphs for the callers computed
-/// by the bottom-up pass.
-///
-class TDDataStructures : public ModulePass {
-  // DSInfo, one graph for each function
-  hash_map<Function*, DSGraph*> DSInfo;
-  hash_set<Function*> ArgsRemainIncomplete;
-  DSGraph *GlobalsGraph;
-  BUDataStructures *BUInfo;
-
-  /// GlobalECs - The equivalence classes for each global value that is merged
-  /// with other global values in the DSGraphs.
-  EquivalenceClasses<GlobalValue*> GlobalECs;
-
-  /// CallerCallEdges - For a particular graph, we keep a list of these records
-  /// which indicates which graphs call this function and from where.
-  struct CallerCallEdge {
-    DSGraph *CallerGraph;        // The graph of the caller function.
-    const DSCallSite *CS;        // The actual call site.
-    Function *CalledFunction;    // The actual function being called.
-
-    CallerCallEdge(DSGraph *G, const DSCallSite *cs, Function *CF)
-      : CallerGraph(G), CS(cs), CalledFunction(CF) {}
-
-    bool operator<(const CallerCallEdge &RHS) const {
-      return CallerGraph < RHS.CallerGraph ||
-            (CallerGraph == RHS.CallerGraph && CS < RHS.CS);
-    }
-  };
-
-  std::map<DSGraph*, std::vector<CallerCallEdge> > CallerEdges;
-
-
-  // IndCallMap - We memoize the results of indirect call inlining operations
-  // that have multiple targets here to avoid N*M inlining.  The key to the map
-  // is a sorted set of callee functions, the value is the DSGraph that holds
-  // all of the caller graphs merged together, and the DSCallSite to merge with
-  // the arguments for each function.
-  std::map<std::vector<Function*>, DSGraph*> IndCallMap;
-
-public:
-  ~TDDataStructures() { releaseMyMemory(); }
-
-  virtual bool runOnModule(Module &M);
-
-  bool hasGraph(const Function &F) const {
-    return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
-  }
-
-  /// getDSGraph - Return the data structure graph for the specified function.
-  ///
-  DSGraph &getDSGraph(const Function &F) const {
-    hash_map<Function*, DSGraph*>::const_iterator I =
-      DSInfo.find(const_cast<Function*>(&F));
-    if (I != DSInfo.end()) return *I->second;
-    return const_cast<TDDataStructures*>(this)->
-        getOrCreateDSGraph(const_cast<Function&>(F));
-  }
-
-  DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
-  EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
-
-
-  /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
-  /// These correspond to the interfaces defined in the AliasAnalysis class.
-  void deleteValue(Value *V);
-  void copyValue(Value *From, Value *To);
-
-  /// print - Print out the analysis results...
-  ///
-  void print(std::ostream &O, const Module *M) const;
-
-  /// If the pass pipeline is done with this pass, we can release our memory...
-  ///
-  virtual void releaseMyMemory();
-
-  /// getAnalysisUsage - This obviously provides a data structure graph.
-  ///
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-    AU.addRequired<BUDataStructures>();
-  }
-
-private:
-  void markReachableFunctionsExternallyAccessible(DSNode *N,
-                                                  hash_set<DSNode*> &Visited);
-
-  void InlineCallersIntoGraph(DSGraph &G);
-  DSGraph &getOrCreateDSGraph(Function &F);
-  void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
-                        std::vector<DSGraph*> &PostOrder);
-};
-
-
-/// CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
-/// but we use take a completed call graph and inline all indirect callees into
-/// their callers graphs, making the result more useful for things like pool
-/// allocation.
-///
-struct CompleteBUDataStructures : public BUDataStructures {
-  virtual bool runOnModule(Module &M);
-
-  bool hasGraph(const Function &F) const {
-    return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
-  }
-
-  /// getDSGraph - Return the data structure graph for the specified function.
-  ///
-  DSGraph &getDSGraph(const Function &F) const {
-    hash_map<Function*, DSGraph*>::const_iterator I =
-      DSInfo.find(const_cast<Function*>(&F));
-    assert(I != DSInfo.end() && "Function not in module!");
-    return *I->second;
-  }
-
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-    AU.addRequired<BUDataStructures>();
-
-    // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
-    // globals graph has been implemented in the BU pass)
-    AU.addRequired<TDDataStructures>();
-  }
-
-  /// print - Print out the analysis results...
-  ///
-  void print(std::ostream &O, const Module *M) const;
-
-private:
-  unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack,
-                              unsigned &NextID,
-                              hash_map<DSGraph*, unsigned> &ValMap);
-  DSGraph &getOrCreateGraph(Function &F);
-  void processGraph(DSGraph &G);
-};
-
-
-/// EquivClassGraphs - This is the same as the complete bottom-up graphs, but
-/// with functions partitioned into equivalence classes and a single merged
-/// DS graph for all functions in an equivalence class.  After this merging,
-/// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
-///
-struct EquivClassGraphs : public ModulePass {
-  CompleteBUDataStructures *CBU;
-
-  DSGraph *GlobalsGraph;
-
-  // DSInfo - one graph for each function.
-  hash_map<const Function*, DSGraph*> DSInfo;
-
-  /// ActualCallees - The actual functions callable from indirect call sites.
-  ///
-  std::set<std::pair<Instruction*, Function*> > ActualCallees;
-
-  // Equivalence class where functions that can potentially be called via the
-  // same function pointer are in the same class.
-  EquivalenceClasses<Function*> FuncECs;
-
-  /// OneCalledFunction - For each indirect call, we keep track of one
-  /// target of the call.  This is used to find equivalence class called by
-  /// a call site.
-  std::map<DSNode*, Function *> OneCalledFunction;
-
-  /// GlobalECs - The equivalence classes for each global value that is merged
-  /// with other global values in the DSGraphs.
-  EquivalenceClasses<GlobalValue*> GlobalECs;
-
-public:
-  /// EquivClassGraphs - Computes the equivalence classes and then the
-  /// folded DS graphs for each class.
-  ///
-  virtual bool runOnModule(Module &M);
-
-  /// print - Print out the analysis results...
-  ///
-  void print(std::ostream &O, const Module *M) const;
-
-  EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
-
-  /// getDSGraph - Return the data structure graph for the specified function.
-  /// This returns the folded graph.  The folded graph is the same as the CBU
-  /// graph iff the function is in a singleton equivalence class AND all its
-  /// callees also have the same folded graph as the CBU graph.
-  ///
-  DSGraph &getDSGraph(const Function &F) const {
-    hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
-    assert(I != DSInfo.end() && "No graph computed for that function!");
-    return *I->second;
-  }
-
-  bool hasGraph(const Function &F) const {
-    return DSInfo.find(&F) != DSInfo.end();
-  }
-
-  /// ContainsDSGraphFor - Return true if we have a graph for the specified
-  /// function.
-  bool ContainsDSGraphFor(const Function &F) const {
-    return DSInfo.find(&F) != DSInfo.end();
-  }
-
-  /// getSomeCalleeForCallSite - Return any one callee function at
-  /// a call site.
-  ///
-  Function *getSomeCalleeForCallSite(const CallSite &CS) const;
-
-  DSGraph &getGlobalsGraph() const {
-    return *GlobalsGraph;
-  }
-
-  typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy;
-  const ActualCalleesTy &getActualCallees() const {
-    return ActualCallees;
-  }
-
-  typedef ActualCalleesTy::const_iterator callee_iterator;
-  callee_iterator callee_begin(Instruction *I) const {
-    return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
-  }
-
-  callee_iterator callee_end(Instruction *I) const {
-    I = (Instruction*)((char*)I + 1);
-    return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
-  }
-
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-    AU.addRequired<CompleteBUDataStructures>();
-  }
-
-private:
-  void buildIndirectFunctionSets(Module &M);
-
-  unsigned processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack,
-                      unsigned &NextID,
-                      std::map<DSGraph*, unsigned> &ValMap);
-  void processGraph(DSGraph &FG);
-
-  DSGraph &getOrCreateGraph(Function &F);
-};
-
-} // End llvm namespace
-
-#endif