From c4ebdcea7aae1e8ffaa7d2bfd3ae127668097dfb Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 3 Mar 2004 22:01:09 +0000
Subject: [PATCH] Fix a DSA bug that caused DSA to generate incredibly huge
 graphs and take forever to do it on povray.  The problem is that we were not
 copying globals from callees to callers unless the existed in both graphs. 
 We should have copied them in the case where the global pointed to a node
 that was copied as well.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12104 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/DataStructure/DataStructure.cpp | 35 +++++++++++++++++++-
 1 file changed, 34 insertions(+), 1 deletion(-)

diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index a99c59f927b..96284957334 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -11,7 +11,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/DSGraph.h"
+#include "llvm/Analysis/DSGraphTraits.h"
 #include "llvm/Function.h"
 #include "llvm/GlobalVariable.h"
 #include "llvm/iOther.h"
@@ -20,6 +20,7 @@
 #include "llvm/Assembly/Writer.h"
 #include "Support/CommandLine.h"
 #include "Support/Debug.h"
+#include "Support/DepthFirstIterator.h"
 #include "Support/STLExtras.h"
 #include "Support/Statistic.h"
 #include "Support/Timer.h"
@@ -1181,6 +1182,13 @@ void DSGraph::cloneInto(const DSGraph &G, DSScalarMap &OldValMap,
   }
 }
 
+static bool PathExistsToClonedNode(const DSNode *N, ReachabilityCloner &RC) {
+  for (df_iterator<const DSNode*> I = df_begin(N), E = df_end(N); I != E; ++I)
+    if (RC.hasClonedNode(*I))
+      return true;
+  return false;
+}
+
 
 /// 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
@@ -1240,11 +1248,36 @@ void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
     }
     
     // Clone over all globals that appear in the caller and callee graphs.
+    hash_set<GlobalVariable*> NonCopiedGlobals;
     for (DSScalarMap::global_iterator GI = Graph.getScalarMap().global_begin(),
            E = Graph.getScalarMap().global_end(); GI != E; ++GI)
       if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*GI))
         if (ScalarMap.count(GV))
           RC.merge(ScalarMap[GV], Graph.getNodeForValue(GV));
+        else
+          NonCopiedGlobals.insert(GV);
+    
+    // If the global does not appear in the callers graph we generally don't
+    // want to copy the node.  However, if there is a path from the node global
+    // node to a node that we did copy in the graph, we *must* copy it to
+    // maintain the connection information.  Every time we decide to include a
+    // new global, this might make other globals live, so we must iterate
+    // unfortunately.
+    bool MadeChange = false;
+    for (hash_set<GlobalVariable*>::iterator I = NonCopiedGlobals.begin();
+         I != NonCopiedGlobals.end();) {
+      DSNode *GlobalNode = Graph.getNodeForValue(*I).getNode();
+      if (RC.hasClonedNode(GlobalNode)) {
+        // Already cloned it, remove from set.
+        NonCopiedGlobals.erase(I++);
+      } else if (PathExistsToClonedNode(GlobalNode, RC)) {
+        RC.getClonedNH(Graph.getNodeForValue(*I));
+        NonCopiedGlobals.erase(I++);
+      } else {
+        ++I;
+      }
+    }
+
   } else {
     DSNodeHandle RetVal = getReturnNodeFor(F);
 
-- 
2.34.1