From c3f5f7701f670c73244a08f8afd631b44a4fc0c4 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Sun, 8 Feb 2004 01:51:48 +0000
Subject: [PATCH] Instead of callign removeTriviallyDeadNodes on the global
 graph every time removeDeadNodes is called, only call it at the end of the
 pass being run. This saves 1.3 seconds running DSA on 177.mesa (5.3->4.0s),
 which is pretty big.  This is only possible because of the automatic garbage
 collection done on forwarding nodes.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11178 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/DataStructure/BottomUpClosure.cpp |  1 +
 lib/Analysis/DataStructure/DataStructure.cpp   | 17 +++++++++--------
 lib/Analysis/DataStructure/Local.cpp           |  1 +
 lib/Analysis/DataStructure/TopDownClosure.cpp  |  2 ++
 4 files changed, 13 insertions(+), 8 deletions(-)

diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index 3dd8f204f72..5d71b19b574 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -63,6 +63,7 @@ bool BUDataStructures::run(Module &M) {
   // nodes at the end of the BU phase should make things that they point to
   // incomplete in the globals graph.
   // 
+  GlobalsGraph->removeTriviallyDeadNodes();
   GlobalsGraph->maskIncompleteMarkers();
   return false;
 }
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 68530f043ed..24ccf91357d 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -30,6 +30,8 @@ namespace {
   Statistic<> NumCallNodesMerged("dsa", "Number of call nodes merged");
   Statistic<> NumNodeAllocated  ("dsa", "Number of nodes allocated");
   Statistic<> NumDNE            ("dsa", "Number of nodes removed by reachability");
+  Statistic<> NumTrivialDNE     ("dsa", "Number of nodes trivially removed");
+  Statistic<> NumTrivialGlobalDNE("dsa", "Number of globals trivially removed");
 
   cl::opt<bool>
   EnableDSNodeGlobalRootsHack("enable-dsa-globalrootshack", cl::Hidden,
@@ -1470,8 +1472,6 @@ static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
 //
 void DSGraph::removeTriviallyDeadNodes() {
   TIME_REGION(X, "removeTriviallyDeadNodes");
-  removeIdenticalCalls(FunctionCalls);
-  removeIdenticalCalls(AuxFunctionCalls);
 
   // Loop over all of the nodes in the graph, calling getNode on each field.
   // This will cause all nodes to update their forwarding edges, causing
@@ -1531,6 +1531,7 @@ void DSGraph::removeTriviallyDeadNodes() {
           for (unsigned j = 0, e = Globals.size(); j != e; ++j)
             ScalarMap.erase(Globals[j]);
           Node.makeNodeDead();
+          ++NumTrivialGlobalDNE;
         }
       }
     }
@@ -1538,10 +1539,14 @@ void DSGraph::removeTriviallyDeadNodes() {
     if (Node.getNodeFlags() == 0 && Node.hasNoReferrers()) {
       // This node is dead!
       NI = Nodes.erase(NI);    // Erase & remove from node list.
+      ++NumTrivialDNE;
     } else {
       ++NI;
     }
   }
+
+  removeIdenticalCalls(FunctionCalls);
+  removeIdenticalCalls(AuxFunctionCalls);
 }
 
 
@@ -1755,12 +1760,8 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
   AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx,
                          AuxFunctionCalls.end());
 
-  // We are finally done with the GGCloner so we can clear it and then get rid
-  // of unused nodes in the GlobalsGraph produced by merging.
-  if (GGCloner.clonedNode()) {
-    GGCloner.destroy();
-    GlobalsGraph->removeTriviallyDeadNodes();
-  }
+  // We are finally done with the GGCloner so we can destroy it.
+  GGCloner.destroy();
 
   // At this point, any nodes which are visited, but not alive, are nodes
   // which can be removed.  Loop over all nodes, eliminating completely
diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp
index a62cf9806fc..22a60414d3c 100644
--- a/lib/Analysis/DataStructure/Local.cpp
+++ b/lib/Analysis/DataStructure/Local.cpp
@@ -623,6 +623,7 @@ bool LocalDataStructures::run(Module &M) {
     if (!I->isExternal())
       GGB.mergeInGlobalInitializer(I);
 
+  GlobalsGraph->removeTriviallyDeadNodes();
   GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs);
   return false;
 }
diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp
index 939d7ebd6e1..78ffc359525 100644
--- a/lib/Analysis/DataStructure/TopDownClosure.cpp
+++ b/lib/Analysis/DataStructure/TopDownClosure.cpp
@@ -107,6 +107,8 @@ bool TDDataStructures::run(Module &M) {
   }
 
   ArgsRemainIncomplete.clear();
+  GlobalsGraph->removeTriviallyDeadNodes();
+
   return false;
 }
 
-- 
2.34.1