Substantially improve the DSA code by removing 'forwarding' nodes from

DSGraphs while they are forwarding.  When the last reference to the forwarding
node is dropped, the forwarding node is autodeleted.  This should simplify
removeTriviallyDead nodes, and is only (efficiently) possible because we are
using an ilist of dsnodes now.

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

diff --git a/include/llvm/Analysis/DSGraph.h b/include/llvm/Analysis/DSGraph.h
index 568a90bc6062be7d82e837c06fb31eb76aeefe8e..1c108518489b445ddd4d7a64c58215ef157f5979 100644 (file)
--- a/include/llvm/Analysis/DSGraph.h
+++ b/include/llvm/Analysis/DSGraph.h
@@ -182,6 +182,7 @@ public:
   /// 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...

diff --git a/include/llvm/Analysis/DSNode.h b/include/llvm/Analysis/DSNode.h
index e76a48090f0a7b6d8393dfc7da56c28d5b3301b6..611293132bea15327f03d1fd5891012db693cef9 100644 (file)
--- a/include/llvm/Analysis/DSNode.h
+++ b/include/llvm/Analysis/DSNode.h
@@ -159,12 +159,18 @@ public:
   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.setNode(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
@@ -377,8 +383,8 @@ inline DSNode *DSNodeHandle::getNode() const {
 }
 
 inline void DSNodeHandle::setNode(DSNode *n) const {
-  assert(!n || !n->getForwardNode() && "Cannot set node to a forwarded node!");
-  if (N) N->NumReferrers--;
+  assert(!n || !n->isForwarding() && "Cannot set node to a forwarded node!");
+  if (N) getNode()->NumReferrers--;
   N = n;
   if (N) {
     N->NumReferrers++;

diff --git a/include/llvm/Analysis/DataStructure/DSGraph.h b/include/llvm/Analysis/DataStructure/DSGraph.h
index 568a90bc6062be7d82e837c06fb31eb76aeefe8e..1c108518489b445ddd4d7a64c58215ef157f5979 100644 (file)
--- a/include/llvm/Analysis/DataStructure/DSGraph.h
+++ b/include/llvm/Analysis/DataStructure/DSGraph.h
@@ -182,6 +182,7 @@ public:
   /// 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...

diff --git a/include/llvm/Analysis/DataStructure/DSNode.h b/include/llvm/Analysis/DataStructure/DSNode.h
index e76a48090f0a7b6d8393dfc7da56c28d5b3301b6..611293132bea15327f03d1fd5891012db693cef9 100644 (file)
--- a/include/llvm/Analysis/DataStructure/DSNode.h
+++ b/include/llvm/Analysis/DataStructure/DSNode.h
@@ -159,12 +159,18 @@ public:
   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.setNode(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
@@ -377,8 +383,8 @@ inline DSNode *DSNodeHandle::getNode() const {
 }
 
 inline void DSNodeHandle::setNode(DSNode *n) const {
-  assert(!n || !n->getForwardNode() && "Cannot set node to a forwarded node!");
-  if (N) N->NumReferrers--;
+  assert(!n || !n->isForwarding() && "Cannot set node to a forwarded node!");
+  if (N) getNode()->NumReferrers--;
   N = n;
   if (N) {
     N->NumReferrers++;

diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 57651d78e1ee5677641df083e3d2f1afad1699f7..68530f043ed467d5481a339a39059f9a9c163130 100644 (file)
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -46,7 +46,7 @@ namespace {
 using namespace DS;
 
 DSNode *DSNodeHandle::HandleForwarding() const {
-  assert(!N->ForwardNH.isNull() && "Can only be invoked if forwarding!");
+  assert(N->isForwarding() && "Can only be invoked if forwarding!");
 
   // Handle node forwarding here!
   DSNode *Next = N->ForwardNH.getNode();  // Cause recursive shrinkage
@@ -124,6 +124,10 @@ void DSNode::forwardNode(DSNode *To, unsigned Offset) {
   NodeType = DEAD;
   Size = 0;
   Ty = Type::VoidTy;
+
+  // Remove this node from the parent graph's Nodes list.
+  ParentGraph->unlinkNode(this);  
+  ParentGraph = 0;
 }
 
 // addGlobal - Add an entry for a global value to the Globals list.  This also