* Add a new commandline argument to control the "global roots hack". Default

  it to be off.  If it looks like it's completely unnecessary after testing, I
  will remove it completely (which is the hope).
* Callers of the DSNode "copy ctor" can not choose to not copy links.
* Make node collapsing not create a garbage node in some cases, avoiding a
  memory allocation, and a subsequent DNE.
* When merging types, allow two functions of different types to be merged
  without collapsing.
* Use DSNodeHandle::isNull more often instead of DSNodeHandle::getNode() == 0,
  as it is much more efficient.
*** Implement the new, more efficient reachability cloner class
    In addition to only cloning nodes that are reachable from interesting
    roots, this also fixes the huge inefficiency we had where we cloned lots
    of nodes, only to merge them away immediately after they were cloned.
    Now we only actually allocate a node if there isn't one to merge it into.
* Eliminate the now-obsolete cloneReachable* and clonePartiallyInto methods
* Rewrite updateFromGlobalsGraph to use the reachability cloner
* Rewrite mergeInGraph to use the reachability cloner
* Disable the scalar map scanning code in removeTriviallyDeadNodes.  In large
  SCC's, this is extremely expensive.  We need a better data structure for the
  scalar map, because we really want to scan the unique node handles, not ALL
  of the scalars.
* Remove the incorrect SANER_CODE_FOR_CHECKING_IF_ALL_REFERRERS_ARE_FROM_SCALARMAP code.
* Move the code for eliminating integer nodes from the trivially dead
  eliminator to the dead node eliminator.
* removeDeadNodes no longer uses removeTriviallyDeadNodes, as it contains a
  superset of the node removal power.
* Only futz around with the globals graph in removeDeadNodes if it is modified


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

1 files changed, 407 insertions, 454 deletions

diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 81e6db3d75..2a0dc998a0 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -17,6 +17,7 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/Assembly/Writer.h"
+#include "Support/CommandLine.h"
 #include "Support/Debug.h"
 #include "Support/STLExtras.h"
 #include "Support/Statistic.h"
@@ -27,6 +28,11 @@ using namespace llvm;
 namespace {
   Statistic<> NumFolds          ("dsnode", "Number of nodes completely folded");
   Statistic<> NumCallNodesMerged("dsnode", "Number of call nodes merged");
+  Statistic<> NumNodeAllocated  ("dsnode", "Number of nodes allocated");
+
+  cl::opt<bool>
+  EnableDSNodeGlobalRootsHack("enable-dsa-globalrootshack", cl::Hidden,
+                cl::desc("Make DSA less aggressive when cloning graphs"));
 };
 
 #if 0
@@ -68,13 +74,19 @@ DSNode::DSNode(const Type *T, DSGraph *G)
   // Add the type entry if it is specified...
   if (T) mergeTypeInfo(T, 0);
   G->getNodes().push_back(this);
+  ++NumNodeAllocated;
 }
 
 // DSNode copy constructor... do not copy over the referrers list!
-DSNode::DSNode(const DSNode &N, DSGraph *G)
+DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks)
   : NumReferrers(0), Size(N.Size), ParentGraph(G),
-    Ty(N.Ty), Links(N.Links), Globals(N.Globals), NodeType(N.NodeType) {
+    Ty(N.Ty), Globals(N.Globals), NodeType(N.NodeType) {
+  if (!NullLinks)
+    Links = N.Links;
+  else
+    Links.resize(N.Links.size()); // Create the appropriate number of null links
   G->getNodes().push_back(this);
+  ++NumNodeAllocated;
 }
 
 /// getTargetData - Get the target data object used to construct this node.
@@ -138,26 +150,40 @@ void DSNode::foldNodeCompletely() {
 
   ++NumFolds;
 
-  // Create the node we are going to forward to...
-  DSNode *DestNode = new DSNode(0, ParentGraph);
-  DestNode->NodeType = NodeType|DSNode::Array;
-  DestNode->Ty = Type::VoidTy;
-  DestNode->Size = 1;
-  DestNode->Globals.swap(Globals);
-
-  // Start forwarding to the destination node...
-  forwardNode(DestNode, 0);
-  
-  if (Links.size()) {
-    DestNode->Links.push_back(Links[0]);
-    DSNodeHandle NH(DestNode);
-
-    // If we have links, merge all of our outgoing links together...
-    for (unsigned i = Links.size()-1; i != 0; --i)
-      NH.getNode()->Links[0].mergeWith(Links[i]);
-    Links.clear();
+  // If this node has a size that is <= 1, we don't need to create a forwarding
+  // node.
+  if (getSize() <= 1) {
+    NodeType |= DSNode::Array;
+    Ty = Type::VoidTy;
+    Size = 1;
+    assert(Links.size() <= 1 && "Size is 1, but has more links?");
+    Links.resize(1);
   } else {
-    DestNode->Links.resize(1);
+    // Create the node we are going to forward to.  This is required because
+    // some referrers may have an offset that is > 0.  By forcing them to
+    // forward, the forwarder has the opportunity to correct the offset.
+    DSNode *DestNode = new DSNode(0, ParentGraph);
+    DestNode->NodeType = NodeType|DSNode::Array;
+    DestNode->Ty = Type::VoidTy;
+    DestNode->Size = 1;
+    DestNode->Globals.swap(Globals);
+    
+    // Start forwarding to the destination node...
+    forwardNode(DestNode, 0);
+    
+    if (!Links.empty()) {
+      DestNode->Links.reserve(1);
+      
+      DSNodeHandle NH(DestNode);
+      DestNode->Links.push_back(Links[0]);
+      
+      // If we have links, merge all of our outgoing links together...
+      for (unsigned i = Links.size()-1; i != 0; --i)
+        NH.getNode()->Links[0].mergeWith(Links[i]);
+      Links.clear();
+    } else {
+      DestNode->Links.resize(1);
+    }
   }
 }
 
@@ -432,6 +458,10 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset,
   // If we found our type exactly, early exit
   if (SubType == NewTy) return false;
 
+  // Differing function types don't require us to merge.  They are not values anyway.
+  if (isa<FunctionType>(SubType) &&
+      isa<FunctionType>(NewTy)) return false;
+
   unsigned SubTypeSize = SubType->isSized() ? TD.getTypeSize(SubType) : 0;
 
   // Ok, we are getting desperate now.  Check for physical subtyping, where we
@@ -523,10 +553,10 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset,
 // can cause merging of nodes in the graph.
 //
 void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) {
-  if (NH.getNode() == 0) return;       // Nothing to do
+  if (NH.isNull()) return;       // Nothing to do
 
   DSNodeHandle &ExistingEdge = getLink(Offset);
-  if (ExistingEdge.getNode()) {
+  if (!ExistingEdge.isNull()) {
     // Merge the two nodes...
     ExistingEdge.mergeWith(NH);
   } else {                             // No merging to perform...
@@ -578,8 +608,11 @@ static void MergeSortedVectors(std::vector<GlobalValue*> &Dest,
   }
 }
 
+void DSNode::mergeGlobals(const std::vector<GlobalValue*> &RHS) {
+  MergeSortedVectors(Globals, RHS);
+}
 
-// MergeNodes() - Helper function for DSNode::mergeWith().
+// MergeNodes - Helper function for DSNode::mergeWith().
 // This function does the hard work of merging two nodes, CurNodeH
 // and NH after filtering out trivial cases and making sure that
 // CurNodeH.offset >= NH.offset.
@@ -642,7 +675,7 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) {
   if (CurNodeH.getNode() == N || N == 0) return;
   assert(!CurNodeH.getNode()->isDeadNode());
 
-  // Merge the NodeType information...
+  // Merge the NodeType information.
   CurNodeH.getNode()->NodeType |= N->NodeType;
 
   // Start forwarding to the new node!
@@ -673,7 +706,7 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) {
 
   // Merge the globals list...
   if (!N->Globals.empty()) {
-    MergeSortedVectors(CurNodeH.getNode()->Globals, N->Globals);
+    CurNodeH.getNode()->mergeGlobals(N->Globals);
 
     // Delete the globals from the old node...
     std::vector<GlobalValue*>().swap(N->Globals);
@@ -731,6 +764,213 @@ void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) {
   DSNode::MergeNodes(CurNodeH, NHCopy);
 }
 
+
+//===----------------------------------------------------------------------===//
+// ReachabilityCloner Implementation
+//===----------------------------------------------------------------------===//
+
+DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) {
+  if (SrcNH.isNull()) return DSNodeHandle();
+  const DSNode *SN = SrcNH.getNode();
+
+  DSNodeHandle &NH = NodeMap[SN];
+  if (!NH.isNull())    // Node already mapped?
+    return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset());
+
+  DSNode *DN = new DSNode(*SN, &Dest, true /* Null out all links */);
+  DN->maskNodeTypes(BitsToKeep);
+  NH.setNode(DN);
+  NH.setOffset(SrcNH.getOffset());
+  
+  // Next, recursively clone all outgoing links as necessary.  Note that
+  // adding these links can cause the node to collapse itself at any time, and
+  // the current node may be merged with arbitrary other nodes.  For this
+  // reason, we must always go through NH.
+  DN = 0;
+  for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) {
+    const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift);
+    if (!SrcEdge.isNull()) {
+      const DSNodeHandle &DestEdge = getClonedNH(SrcEdge);
+      // Compute the offset into the current node at which to
+      // merge this link.  In the common case, this is a linear
+      // relation to the offset in the original node (with
+      // wrapping), but if the current node gets collapsed due to
+      // recursive merging, we must make sure to merge in all remaining
+      // links at offset zero.
+      unsigned MergeOffset = 0;
+      DSNode *CN = NH.getNode();
+      if (CN->getSize() != 1)
+        MergeOffset = ((i << DS::PointerShift)+NH.getOffset()
+                       - SrcNH.getOffset()) %CN->getSize();
+      CN->addEdgeTo(MergeOffset, DestEdge);
+    }
+  }
+  
+  // If this node contains any globals, make sure they end up in the scalar
+  // map with the correct offset.
+  for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end();
+       I != E; ++I) {
+    GlobalValue *GV = *I;
+    const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
+    DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
+    assert(DestGNH.getNode() == NH.getNode() &&"Global mapping inconsistent");
+    Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
+                                          DestGNH.getOffset()+NH.getOffset()));
+    
+    if (CloneFlags & DSGraph::UpdateInlinedGlobals)
+      Dest.getInlinedGlobals().insert(GV);
+  }
+
+  return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset());
+}
+
+void ReachabilityCloner::merge(const DSNodeHandle &NH,
+                               const DSNodeHandle &SrcNH) {
+  if (SrcNH.isNull()) return;  // Noop
+  if (NH.isNull()) {
+    // If there is no destination node, just clone the source and assign the
+    // destination node to be it.
+    NH.mergeWith(getClonedNH(SrcNH));
+    return;
+  }
+
+  // Okay, at this point, we know that we have both a destination and a source
+  // node that need to be merged.  Check to see if the source node has already
+  // been cloned.
+  const DSNode *SN = SrcNH.getNode();
+  DSNodeHandle &SCNH = NodeMap[SN];  // SourceClonedNodeHandle
+  if (SCNH.getNode()) {   // Node already cloned?
+    NH.mergeWith(DSNodeHandle(SCNH.getNode(),
+                              SCNH.getOffset()+SrcNH.getOffset()));
+
+    return;  // Nothing to do!
+  }
+
+  // Okay, so the source node has not already been cloned.  Instead of creating
+  // a new DSNode, only to merge it into the one we already have, try to perform
+  // the merge in-place.  The only case we cannot handle here is when the offset
+  // into the existing node is less than the offset into the virtual node we are
+  // merging in.  In this case, we have to extend the existing node, which
+  // requires an allocation anyway.
+  DSNode *DN = NH.getNode();   // Make sure the Offset is up-to-date
+  if (NH.getOffset() >= SrcNH.getOffset()) {
+
+    if (!DN->isNodeCompletelyFolded()) {
+      // Make sure the destination node is folded if the source node is folded.
+      if (SN->isNodeCompletelyFolded()) {
+        DN->foldNodeCompletely();
+        DN = NH.getNode();
+      } else if (SN->getSize() != DN->getSize()) {
+        // If the two nodes are of different size, and the smaller node has the
+        // array bit set, collapse!
+        if (SN->getSize() < DN->getSize()) {
+          if (SN->isArray()) {
+            DN->foldNodeCompletely();
+            DN = NH.getNode();
+          }
+        } else if (DN->isArray()) {
+          DN->foldNodeCompletely();
+          DN = NH.getNode();
+        }
+      }
+    
+      // Merge the type entries of the two nodes together...    
+      if (SN->getType() != Type::VoidTy && !DN->isNodeCompletelyFolded()) {
+        DN->mergeTypeInfo(SN->getType(), NH.getOffset()-SrcNH.getOffset());
+        DN = NH.getNode();
+      }
+    }
+
+    assert(!DN->isDeadNode());
+    
+    // Merge the NodeType information.
+    DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep);
+
+    // Before we start merging outgoing links and updating the scalar map, make
+    // sure it is known that this is the representative node for the src node.
+    SCNH = DSNodeHandle(DN, NH.getOffset()-SrcNH.getOffset());
+
+    // If the source node contains any globals, make sure they end up in the
+    // scalar map with the correct offset.
+    if (SN->global_begin() != SN->global_end()) {
+      // Update the globals in the destination node itself.
+      DN->mergeGlobals(SN->getGlobals());
+
+      // Update the scalar map for the graph we are merging the source node
+      // into.
+      for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end();
+           I != E; ++I) {
+        GlobalValue *GV = *I;
+        const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
+        DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
+        assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent");
+        Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
+                                           DestGNH.getOffset()+NH.getOffset()));
+        
+        if (CloneFlags & DSGraph::UpdateInlinedGlobals)
+          Dest.getInlinedGlobals().insert(GV);
+      }
+    }
+  } else {
+    // We cannot handle this case without allocating a temporary node.  Fall
+    // back on being simple.
+
+    DSNode *NewDN = new DSNode(*SN, &Dest, true /* Null out all links */);
+    NewDN->maskNodeTypes(BitsToKeep);
+
+    unsigned NHOffset = NH.getOffset();
+    NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset()));
+    assert(NH.getNode() &&
+           (NH.getOffset() > NHOffset ||
+            (NH.getOffset() == 0 && NH.getNode()->isNodeCompletelyFolded())) &&
+           "Merging did not adjust the offset!");
+
+    // Before we start merging outgoing links and updating the scalar map, make
+    // sure it is known that this is the representative node for the src node.
+    SCNH = DSNodeHandle(NH.getNode(), NH.getOffset()-SrcNH.getOffset());
+  }
+
+
+  // Next, recursively merge all outgoing links as necessary.  Note that
+  // adding these links can cause the destination node to collapse itself at
+  // any time, and the current node may be merged with arbitrary other nodes.
+  // For this reason, we must always go through NH.
+  DN = 0;
+  for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) {
+    const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift);
+    if (!SrcEdge.isNull()) {
+      // Compute the offset into the current node at which to
+      // merge this link.  In the common case, this is a linear
+      // relation to the offset in the original node (with
+      // wrapping), but if the current node gets collapsed due to
+      // recursive merging, we must make sure to merge in all remaining
+      // links at offset zero.
+      unsigned MergeOffset = 0;
+      DSNode *CN = SCNH.getNode();
+      if (CN->getSize() != 1)
+        MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) %CN->getSize();
+      
+      // Perform the recursive merging.  Make sure to create a temporary NH,
+      // because the Link can disappear in the process of recursive merging.
+      DSNodeHandle Tmp = CN->getLink(MergeOffset);
+      merge(Tmp, SrcEdge);
+    }
+  }
+}
+
+/// mergeCallSite - Merge the nodes reachable from the specified src call
+/// site into the nodes reachable from DestCS.
+void ReachabilityCloner::mergeCallSite(const DSCallSite &DestCS,
+                                       const DSCallSite &SrcCS) {
+  merge(DestCS.getRetVal(), SrcCS.getRetVal());
+  unsigned MinArgs = DestCS.getNumPtrArgs();
+  if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.getNumPtrArgs();
+  
+  for (unsigned a = 0; a != MinArgs; ++a)
+    merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a));
+}
+
+
 //===----------------------------------------------------------------------===//
 // DSCallSite Implementation
 //===----------------------------------------------------------------------===//
@@ -740,6 +980,10 @@ Function &DSCallSite::getCaller() const {
   return *Site.getInstruction()->getParent()->getParent();
 }
 
+void DSCallSite::InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
+                        ReachabilityCloner &RC) {
+  NH = RC.getClonedNH(Src);
+}
 
 //===----------------------------------------------------------------------===//
 // DSGraph Implementation
@@ -807,108 +1051,29 @@ void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) {
     }
 }
 
-
-/// cloneReachableNodes - Clone all reachable nodes from *Node into the current
-/// graph.  This is a recursive function.  The map OldNodeMap is a map from the
-/// original nodes to their clones.  This populates the Globals set with all of
-/// the global values that are cloned in.
-/// 
-void DSGraph::cloneReachableNodes(const DSNode *Node, unsigned BitsToClear,
-                                  NodeMapTy &OldNodeMap, GlobalSetTy &Globals) {
-  DSNodeHandle &NH = OldNodeMap[Node];
-  if (NH.getNode()) return;   // Already cloned this node?
-
-  // FIXME: eliminate eventually!
-  Globals.insert(Node->getGlobals().begin(), Node->getGlobals().end());
-
-  // else Node has not yet been cloned: clone it and clear the specified bits
-  DSNode *New = new DSNode(*Node, this);
-  New->maskNodeTypes(~BitsToClear);
-  NH = New;           // enters in OldNodeMap
-
-  // now recursively clone nodes pointed to by this node
-  for (unsigned i = 0, e = Node->getNumLinks(); i != e; ++i)
-    if (const DSNode *N = Node->getLink(i << DS::PointerShift).getNode())
-      cloneReachableNodes(N, BitsToClear, OldNodeMap, Globals);
-}
-
-void DSGraph::cloneReachableSubgraph(const DSGraph &G,
-                                     hash_set<const DSNode*> &RootNodes,
-                                     NodeMapTy &OldNodeMap,
-                                     unsigned CloneFlags) {
-  RootNodes.erase(0);   // Null is not a root node
-  if (RootNodes.empty()) return;
-  TIME_REGION(X, "cloneReachableSubgraph");
-
-  assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
-  assert(&G != this && "Cannot clone graph into itself!");
-  assert((*RootNodes.begin())->getParentGraph() == &G &&
-         "Root nodes do not belong to this graph!");
-
-  // Remove alloca or mod/ref bits as specified...
-  unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
-    | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0)
-    | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0);
-  BitsToClear |= DSNode::DEAD;  // Clear dead flag...
-
-  GlobalSetTy Globals;
-
-  // Clone all nodes reachable from each root node, using a recursive helper.
-  for (hash_set<const DSNode*>::const_iterator I = RootNodes.begin(),
-         E = RootNodes.end(); I != E; ++I)
-    cloneReachableNodes(*I, BitsToClear, OldNodeMap, Globals);
-
-  // Rewrite the links in the newly created nodes (the nodes in OldNodeMap)
-  // to point into the current graph.
-  for (NodeMapTy::iterator I=OldNodeMap.begin(), E=OldNodeMap.end(); I!= E; ++I)
-    I->second.getNode()->remapLinks(OldNodeMap);
-
-  if (CloneFlags & DSGraph::UpdateInlinedGlobals)
-    InlinedGlobals.insert(Globals.begin(), Globals.end());
-
-  // Make sure to set up the scalar map entries for all of the globals.
-  //
-  // FIXME: when cloneReachableNodes is improved to not require 'remapLinks',
-  // this should not be needed!
-  for (GlobalSetTy::iterator I = Globals.begin(), E = Globals.end(); I!=E; ++I){
-    const DSNodeHandle &GOrig = G.getNodeForValue(*I);
-    DSNodeHandle &GClone = OldNodeMap[GOrig.getNode()];
-    GClone.setOffset(GClone.getOffset()+GOrig.getOffset());
-    ScalarMap[*I].mergeWith(GClone);
-  }
-}
-
-
 /// updateFromGlobalGraph - This function rematerializes global nodes and
 /// nodes reachable from them from the globals graph into the current graph.
-/// It invokes cloneReachableSubgraph, using the globals in the current graph
-/// as the roots.  It also uses the vector InlinedGlobals to avoid cloning and
-/// merging globals that are already up-to-date in the current graph.  In
-/// practice, in the TD pass, this is likely to be a large fraction of the
-/// live global nodes in each function (since most live nodes are likely to
-/// have been brought up-to-date in at _some_ caller or callee).
+/// It uses the vector InlinedGlobals to avoid cloning and merging globals that
+/// are already up-to-date in the current graph.  In practice, in the TD pass,
+/// this is likely to be a large fraction of the live global nodes in each
+/// function (since most live nodes are likely to have been brought up-to-date
+/// in at _some_ caller or callee).
 /// 
 void DSGraph::updateFromGlobalGraph() {
-  // Put the live, non-up-to-date global nodes into a set and the up-to-date
-  // ones in the map above, mapping node in GlobalsGraph to the up-to-date node.
-  hash_set<const DSNode*> GlobalNodeSet;
-  for (ScalarMapTy::const_iterator I = getScalarMap().begin(),
-         E = getScalarMap().end(); I != E; ++I)
-    if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
-      DSNode* GNode = I->second.getNode();
-      assert(GNode && "No node for live global in current Graph?");
-      if (const DSNode* GGNode = GlobalsGraph->ScalarMap[GV].getNode())
-        if (InlinedGlobals.count(GV) == 0) // GNode is not up-to-date
-          GlobalNodeSet.insert(GGNode);
-    }
+  TIME_REGION(X, "updateFromGlobalGraph");
 
-  // Clone the subgraph reachable from the vector of nodes in GlobalNodes
-  // and merge the cloned global nodes with the corresponding ones, if any.
-  {
-    NodeMapTy OldNodeMap;  // Scope ensures these is deleted promptly
-    cloneReachableSubgraph(*GlobalsGraph, GlobalNodeSet, OldNodeMap);
-  }
+  ReachabilityCloner RC(*this, *GlobalsGraph, 0);
 
+  // Clone the non-up-to-date global nodes into this graph.
+  for (ScalarMapTy::const_iterator I = getScalarMap().begin(),
+         E = getScalarMap().end(); I != E; ++I)
+    if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first))
+      if (InlinedGlobals.count(GV) == 0) { // GNode is not up-to-date
+        ScalarMapTy::iterator It = GlobalsGraph->ScalarMap.find(GV);
+        if (It != GlobalsGraph->ScalarMap.end())
+          RC.getClonedNH(It->second);
+      }
+  
   // Merging global nodes leaves behind unused nodes: get rid of them now.
   removeTriviallyDeadNodes();
 }
@@ -950,8 +1115,6 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap,
   for (unsigned i = FN, e = Nodes.size(); i != e; ++i)
     Nodes[i]->remapLinks(OldNodeMap);
 
-  { TIME_REGION(X, "cloneInto:scalars");
-
   // Copy the scalar map... merging all of the global nodes...
   for (ScalarMapTy::const_iterator I = G.ScalarMap.begin(),
          E = G.ScalarMap.end(); I != E; ++I) {
@@ -967,7 +1130,6 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap,
         InlinedGlobals.insert(GV);
     }
   }
-  }
 
   if (!(CloneFlags & DontCloneCallNodes)) {
     // Copy the function calls list...
@@ -996,174 +1158,6 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap,
   }
 }
 
-/// clonePartiallyInto - Clone the reachable subset of the specified DSGraph
-/// into the current graph, for the specified function.
-///
-/// This differs from cloneInto in that it only clones nodes reachable from
-/// globals, call nodes, the scalars specified in ValBindings, and the return
-/// value of the specified function.  This method merges the the cloned
-/// version of the scalars and return value with the specified DSNodeHandles.
-///
-/// On return, OldNodeMap contains a mapping from the original nodes to the
-/// newly cloned nodes, for the subset of nodes that were actually cloned.
-///
-/// The CloneFlags member controls various aspects of the cloning process.
-///
-void DSGraph::clonePartiallyInto(const DSGraph &G, Function &F,
-                                 const DSNodeHandle &RetVal,
-                                 const ScalarMapTy &ValBindings,
-                                 NodeMapTy &OldNodeMap,
-                                 unsigned CloneFlags) {
-
-  TIME_REGION(X, "clonePartiallyInto");
-  assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
-  assert(&G != this && "Cannot clone graph into itself!");
-
-#if 0   // ENABLE THIS to get the cloneReachableSubGraph code path
-  hash_set<const DSNode*> RootNodes;
-
-#if 0
-  // THIS IS A HACK that sanity checks the cloner.  This is inefficient, and
-  // causes all nodes to be cloned.
-
-  // Add the nodes that we need to clone to the RootNodes set.
-  for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i)
-    RootNodes.insert(G.Nodes[i]);
-
-#else
-  // We need the return value nodes...
-  if (RetVal.getNode())
-    RootNodes.insert(G.getReturnNodeFor(F).getNode());      
-
-  // We need the nodes whose bindings are specified by the ValBindings map.
-  for (ScalarMapTy::const_iterator I = ValBindings.begin(),
-         E = ValBindings.end(); I != E; ++I)
-    RootNodes.insert(G.getNodeForValue(I->first).getNode());
-
-  // If requested, we need the nodes from the calls list...
-  if (!(CloneFlags & DontCloneCallNodes)) {
-    for (unsigned i = 0, e = G.FunctionCalls.size(); i != e; ++i) {
-      const DSCallSite &CS = G.FunctionCalls[i];
-      RootNodes.insert(CS.getRetVal().getNode());
-      if (CS.isIndirectCall())
-        RootNodes.insert(CS.getCalleeNode());
-      for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
-        RootNodes.insert(CS.getPtrArg(a).getNode());
-    }
-  }
-
-  // If requested, we need the nodes from the aux calls list...
-  if (!(CloneFlags & DontCloneAuxCallNodes)) {
-    for (unsigned i = 0, e = G.AuxFunctionCalls.size(); i != e; ++i) {
-      const DSCallSite &CS = G.AuxFunctionCalls[i];
-      RootNodes.insert(CS.getRetVal().getNode());
-      if (CS.isIndirectCall())
-        RootNodes.insert(CS.getCalleeNode());
-      for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
-        RootNodes.insert(CS.getPtrArg(a).getNode());
-    }
-  }
-
-
-  /// FIXME: This is another hack, which adds all global nodes to the roots,
-  /// this is necessary for correctness for some reason???
-
-  // Add the nodes that we need to clone to the RootNodes set.
-  for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i)
-    if (!G.Nodes[i]->getGlobals().empty())
-      RootNodes.insert(G.Nodes[i]);
-
-
-#endif
-
-  // Finally, clone the subgraph reachable from these roots.
-  cloneReachableSubgraph(G, RootNodes, OldNodeMap, CloneFlags);
-#else
-  unsigned FN = Nodes.size();           // First new node...
-
-  /// FIXME: This currently clones the whole graph over, instead of doing it
-  /// incrementally.  This could be sped up quite a bit further!
-
-  // Duplicate all of the nodes, populating the node map...
-  Nodes.reserve(FN+G.Nodes.size());
-
-  // Remove alloca or mod/ref bits as specified...
-  unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
-    | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0)
-    | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0);
-  BitsToClear |= DSNode::DEAD;  // Clear dead flag...
-
-  GlobalSetTy ClonedGlobals;
-  for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) {
-    DSNode *Old = G.Nodes[i];
-    DSNode *New = new DSNode(*Old, this);
-    New->maskNodeTypes(~BitsToClear);
-    OldNodeMap[Old] = New;
-
-    ClonedGlobals.insert(New->getGlobals().begin(), New->getGlobals().end());
-  }
-
-  // Rewrite the links in the new nodes to point into the current graph now.
-  for (unsigned i = FN, e = Nodes.size(); i != e; ++i)
-    Nodes[i]->remapLinks(OldNodeMap);
-
-  // Ensure that all global nodes end up in the scalar map, as appropriate.
-  for (GlobalSetTy::iterator CI = ClonedGlobals.begin(),
-         E = ClonedGlobals.end(); CI != E; ++CI) {
-    const DSNodeHandle &NGH = G.getNodeForValue(*CI);
-
-    DSNodeHandle &MappedNode = OldNodeMap[NGH.getNode()];
-    DSNodeHandle H(MappedNode.getNode(),NGH.getOffset()+MappedNode.getOffset());
-    ScalarMap[*CI].mergeWith(H);
-
-    if (CloneFlags & DSGraph::UpdateInlinedGlobals)
-      InlinedGlobals.insert(*CI);
-  }
-#endif
-
-#ifndef NDEBUG
-  Timer::addPeakMemoryMeasurement();
-#endif
-
-  // Merge the requested portion of the scalar map with the values specified.
-  for (ScalarMapTy::const_iterator I = ValBindings.begin(),
-         E = ValBindings.end(); I != E; ++I) {
-    const DSNodeHandle &SNH = G.getNodeForValue(I->first);
-
-    DSNodeHandle &MappedNode = OldNodeMap[SNH.getNode()];
-    DSNodeHandle H(MappedNode.getNode(),SNH.getOffset()+MappedNode.getOffset());
-    H.mergeWith(I->second);
-  }
-
-  // Map the return node pointer over.
-  if (RetVal.getNode()) {
-    const DSNodeHandle &Ret = G.getReturnNodeFor(F);
-    DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
-    DSNodeHandle H(MappedRet.getNode(), 
-                 MappedRet.getOffset()+Ret.getOffset());
-    H.mergeWith(RetVal);
-  }
-
-  // If requested, copy the calls or aux-calls lists.
-  if (!(CloneFlags & DontCloneCallNodes)) {
-    // Copy the function calls list...
-    unsigned FC = FunctionCalls.size();  // FirstCall
-    FunctionCalls.reserve(FC+G.FunctionCalls.size());
-    for (unsigned i = 0, ei = G.FunctionCalls.size(); i != ei; ++i)
-      FunctionCalls.push_back(DSCallSite(G.FunctionCalls[i], OldNodeMap));
-  }
-
-  if (!(CloneFlags & DontCloneAuxCallNodes)) {
-    // Copy the auxiliary function calls list...
-    unsigned FC = AuxFunctionCalls.size();  // FirstCall
-    AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size());
-    for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i)
-      AuxFunctionCalls.push_back(DSCallSite(G.AuxFunctionCalls[i], OldNodeMap));
-  }
-}
-
-
-
 
 /// mergeInGraph - The method is used for merging graphs together.  If the
 /// argument graph is not *this, it makes a clone of the specified graph, then
@@ -1172,13 +1166,15 @@ void DSGraph::clonePartiallyInto(const DSGraph &G, Function &F,
 ///
 void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
                            const DSGraph &Graph, unsigned CloneFlags) {
+  TIME_REGION(X, "mergeInGraph");
+
   // If this is not a recursive call, clone the graph into this graph...
   if (&Graph != this) {
-    // Clone the callee's graph into the current graph, keeping
-    // track of where scalars in the old graph _used_ to point,
-    // and of the new nodes matching nodes of the old graph.
-    ScalarMapTy ValueBindings;
-
+    // Clone the callee's graph into the current graph, keeping track of where
+    // scalars in the old graph _used_ to point, and of the new nodes matching
+    // nodes of the old graph.
+    ReachabilityCloner RC(*this, Graph, CloneFlags);
+    
     // Set up argument bindings
     Function::aiterator AI = F.abegin();
     for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) {
@@ -1193,16 +1189,38 @@ void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
       if (AI == F.aend()) break;
       
       // Add the link from the argument scalar to the provided value.
-      ValueBindings[AI] = CS.getPtrArg(i);
+      RC.merge(CS.getPtrArg(i), Graph.getNodeForValue(AI));
     }
     
-    NodeMapTy OldNodeMap;
-    clonePartiallyInto(Graph, F, CS.getRetVal(), ValueBindings, OldNodeMap,
-                       CloneFlags | DSGraph::UpdateInlinedGlobals);
-
+    // Map the return node pointer over.
+    if (CS.getRetVal().getNode())
+      RC.merge(CS.getRetVal(), Graph.getReturnNodeFor(F));
+    
+    // If requested, copy the calls or aux-calls lists.
+    if (!(CloneFlags & DontCloneCallNodes)) {
+      // Copy the function calls list...
+      FunctionCalls.reserve(FunctionCalls.size()+Graph.FunctionCalls.size());
+      for (unsigned i = 0, ei = Graph.FunctionCalls.size(); i != ei; ++i)
+        FunctionCalls.push_back(DSCallSite(Graph.FunctionCalls[i], RC));
+    }
+    
+    if (!(CloneFlags & DontCloneAuxCallNodes)) {
+      // Copy the auxiliary function calls list...
+      AuxFunctionCalls.reserve(AuxFunctionCalls.size()+
+                               Graph.AuxFunctionCalls.size());
+      for (unsigned i = 0, ei = Graph.AuxFunctionCalls.size(); i != ei; ++i)
+        AuxFunctionCalls.push_back(DSCallSite(Graph.AuxFunctionCalls[i], RC));
+    }
+    
+    // If the user requested it, add the nodes that we need to clone to the
+    // RootNodes set.
+    if (!EnableDSNodeGlobalRootsHack)
+      for (unsigned i = 0, e = Graph.Nodes.size(); i != e; ++i)
+        if (!Graph.Nodes[i]->getGlobals().empty())
+          RC.getClonedNH(Graph.Nodes[i]);
+                                                 
   } else {
     DSNodeHandle RetVal = getReturnNodeFor(F);
-    ScalarMapTy &ScalarMap = getScalarMap();
 
     // Merge the return value with the return value of the context...
     RetVal.mergeWith(CS.getRetVal());
@@ -1222,8 +1240,7 @@ void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
       if (AI == F.aend()) break;
       
       // Add the link from the argument scalar to the provided value
-      assert(ScalarMap.count(AI) && "Argument not in scalar map?");
-      DSNodeHandle &NH = ScalarMap[AI];
+      DSNodeHandle &NH = getNodeForValue(AI);
       assert(NH.getNode() && "Pointer argument without scalarmap entry?");
       NH.mergeWith(CS.getPtrArg(i));
     }
@@ -1238,7 +1255,7 @@ DSCallSite DSGraph::getCallSiteForArguments(Function &F) const {
 
   for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
     if (isPointerType(I->getType()))
-      Args.push_back(getScalarMap().find(I)->second);
+      Args.push_back(getNodeForValue(I));
 
   return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args);
 }
@@ -1291,9 +1308,8 @@ void DSGraph::markIncompleteNodes(unsigned Flags) {
       Function &F = *FI->first;
       if (F.getName() != "main")
         for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
-          if (isPointerType(I->getType()) &&
-              ScalarMap.find(I) != ScalarMap.end())
-            markIncompleteNode(ScalarMap[I].getNode());
+          if (isPointerType(I->getType()))
+            markIncompleteNode(getNodeForValue(I).getNode());
     }
 
   // Mark stuff passed into functions calls as being incomplete...
@@ -1330,11 +1346,11 @@ static inline bool nodeContainsExternalFunction(const DSNode *N) {
 }
 
 static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
-
   // Remove trivially identical function calls
   unsigned NumFns = Calls.size();
   std::sort(Calls.begin(), Calls.end());  // Sort by callee as primary key!
 
+#if 1
   // Scan the call list cleaning it up as necessary...
   DSNode   *LastCalleeNode = 0;
   Function *LastCalleeFunc = 0;
@@ -1375,12 +1391,21 @@ static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
           else
             LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal();
         }
-        
+     
+        // It is not clear why, but enabling this code makes DSA really
+        // sensitive to node forwarding.  Basically, with this enabled, DSA
+        // performs different number of inlinings based on which nodes are
+        // forwarding or not.  This is clearly a problem, so this code is
+        // disabled until this can be resolved.
 #if 1
-        if (LastCalleeContainsExternalFunction ||
+        if (LastCalleeContainsExternalFunction
+#if 0
+            ||
             // This should be more than enough context sensitivity!
             // FIXME: Evaluate how many times this is tripped!
-            NumDuplicateCalls > 20) {
+            NumDuplicateCalls > 20
+#endif
+            ) {
           DSCallSite &OCS = Calls[i-1];
           OCS.mergeWith(CS);
           
@@ -1403,7 +1428,7 @@ static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
       }
     }
   }
-
+#endif
   Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end());
 
   // Track the number of call nodes merged away...
@@ -1421,7 +1446,6 @@ static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
 //