* Allow access to DSNode iterator as DSNode::iterator/begin/end

* Add debugging "dump" method to DSNode
* Fix bugs in DSNode iterator


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

5 files changed, 66 insertions, 33 deletions

diff --git a/include/llvm/Analysis/DSGraphTraits.h b/include/llvm/Analysis/DSGraphTraits.h
index 6798969..3b6ff74 100644
--- a/include/llvm/Analysis/DSGraphTraits.h
+++ b/include/llvm/Analysis/DSGraphTraits.h
@@ -11,19 +11,24 @@
 
 #include "Support/GraphTraits.h"
 #include "llvm/Analysis/DataStructure.h"
-#include "llvm/Value.h"  // FIXME: Move cast/dyn_cast out to Support
 
 class DSNodeIterator : public std::forward_iterator<DSNode, ptrdiff_t> {
+  friend class DSNode;
   DSNode * const Node;
   unsigned Link;
   unsigned LinkIdx;
   
   typedef DSNodeIterator _Self;
-public:
-  DSNodeIterator(DSNode *N) : Node(N), Link(0), LinkIdx(0) {}  // begin iterator
+
+  DSNodeIterator(DSNode *N) : Node(N), Link(0), LinkIdx(0) {   // begin iterator
+    unsigned NumLinks = Node->getNumOutgoingLinks();
+    while (Link < NumLinks && Node->getOutgoingLink(Link).empty())
+      ++Link;
+  }
   DSNodeIterator(DSNode *N, bool)       // Create end iterator
     : Node(N), Link(N->getNumOutgoingLinks()), LinkIdx(0) {
   }
+public:
 
   bool operator==(const _Self& x) const {
     return Link == x.Link && LinkIdx == x.LinkIdx;
@@ -39,7 +44,10 @@ public:
     if (LinkIdx < Node->getOutgoingLink(Link).size()-1)
       ++LinkIdx;
     else {
-      ++Link;
+      unsigned NumLinks = Node->getNumOutgoingLinks();
+      do {
+        ++Link;
+      } while (Link < NumLinks && Node->getOutgoingLink(Link).empty());
       LinkIdx = 0;
     }
     return *this;
@@ -52,16 +60,15 @@ public:
 
 template <> struct GraphTraits<DSNode*> {
   typedef DSNode NodeType;
-  typedef DSNodeIterator ChildIteratorType;
+  typedef DSNode::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(DSNode *N) { return N; }
-  static ChildIteratorType child_begin(NodeType *N) { 
-    return DSNodeIterator(N);
-  }
-  static ChildIteratorType child_end(NodeType *N) { 
-    return DSNodeIterator(N, true);
-  }
+  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
+  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 };
 
+// Provide iterators for DSNode...
+inline DSNode::iterator DSNode::begin() { return DSNodeIterator(this); }
+inline DSNode::iterator DSNode::end()   { return DSNodeIterator(this, false); }
 
 #endif
diff --git a/include/llvm/Analysis/DataStructure.h b/include/llvm/Analysis/DataStructure.h
index 64cd3fc..edb0ac5 100644
--- a/include/llvm/Analysis/DataStructure.h
+++ b/include/llvm/Analysis/DataStructure.h
@@ -19,6 +19,7 @@ class FunctionRepBuilder;
 class GlobalValue;
 class FunctionDSGraph;
 class DataStructure;
+class DSNodeIterator;
 
 // FIXME: move this somewhere private
 unsigned countPointerFields(const Type *Ty);
@@ -126,6 +127,10 @@ public:
     assert(Referrers.empty() && "Referrers to dead node exist!");
   }
 
+  typedef DSNodeIterator iterator;
+  inline iterator begin();   // Defined in DataStructureGraph.h
+  inline iterator end();
+
   unsigned getNumLinks() const { return FieldLinks.size(); }
   PointerValSet &getLink(unsigned i) {
     assert(i < getNumLinks() && "Field links access out of range...");
@@ -163,6 +168,7 @@ public:
   }
 
   void print(std::ostream &O) const;
+  void dump() const;
 
   virtual std::string getCaption() const = 0;
   virtual const std::vector<PointerValSet> *getAuxLinks() const {
diff --git a/include/llvm/Analysis/DataStructure/DSGraphTraits.h b/include/llvm/Analysis/DataStructure/DSGraphTraits.h
index 6798969..3b6ff74 100644
--- a/include/llvm/Analysis/DataStructure/DSGraphTraits.h
+++ b/include/llvm/Analysis/DataStructure/DSGraphTraits.h
@@ -11,19 +11,24 @@
 
 #include "Support/GraphTraits.h"
 #include "llvm/Analysis/DataStructure.h"
-#include "llvm/Value.h"  // FIXME: Move cast/dyn_cast out to Support
 
 class DSNodeIterator : public std::forward_iterator<DSNode, ptrdiff_t> {
+  friend class DSNode;
   DSNode * const Node;
   unsigned Link;
   unsigned LinkIdx;
   
   typedef DSNodeIterator _Self;
-public:
-  DSNodeIterator(DSNode *N) : Node(N), Link(0), LinkIdx(0) {}  // begin iterator
+
+  DSNodeIterator(DSNode *N) : Node(N), Link(0), LinkIdx(0) {   // begin iterator
+    unsigned NumLinks = Node->getNumOutgoingLinks();
+    while (Link < NumLinks && Node->getOutgoingLink(Link).empty())
+      ++Link;
+  }
   DSNodeIterator(DSNode *N, bool)       // Create end iterator
     : Node(N), Link(N->getNumOutgoingLinks()), LinkIdx(0) {
   }
+public:
 
   bool operator==(const _Self& x) const {
     return Link == x.Link && LinkIdx == x.LinkIdx;
@@ -39,7 +44,10 @@ public:
     if (LinkIdx < Node->getOutgoingLink(Link).size()-1)
       ++LinkIdx;
     else {
-      ++Link;
+      unsigned NumLinks = Node->getNumOutgoingLinks();
+      do {
+        ++Link;
+      } while (Link < NumLinks && Node->getOutgoingLink(Link).empty());
       LinkIdx = 0;
     }
     return *this;
@@ -52,16 +60,15 @@ public:
 
 template <> struct GraphTraits<DSNode*> {
   typedef DSNode NodeType;
-  typedef DSNodeIterator ChildIteratorType;
+  typedef DSNode::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(DSNode *N) { return N; }
-  static ChildIteratorType child_begin(NodeType *N) { 
-    return DSNodeIterator(N);
-  }
-  static ChildIteratorType child_end(NodeType *N) { 
-    return DSNodeIterator(N, true);
-  }
+  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
+  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 };
 
+// Provide iterators for DSNode...
+inline DSNode::iterator DSNode::begin() { return DSNodeIterator(this); }
+inline DSNode::iterator DSNode::end()   { return DSNodeIterator(this, false); }
 
 #endif
diff --git a/include/llvm/Analysis/DataStructure/DataStructure.h b/include/llvm/Analysis/DataStructure/DataStructure.h
index 64cd3fc..edb0ac5 100644
--- a/include/llvm/Analysis/DataStructure/DataStructure.h
+++ b/include/llvm/Analysis/DataStructure/DataStructure.h
@@ -19,6 +19,7 @@ class FunctionRepBuilder;
 class GlobalValue;
 class FunctionDSGraph;
 class DataStructure;
+class DSNodeIterator;
 
 // FIXME: move this somewhere private
 unsigned countPointerFields(const Type *Ty);
@@ -126,6 +127,10 @@ public:
     assert(Referrers.empty() && "Referrers to dead node exist!");
   }
 
+  typedef DSNodeIterator iterator;
+  inline iterator begin();   // Defined in DataStructureGraph.h
+  inline iterator end();
+
   unsigned getNumLinks() const { return FieldLinks.size(); }
   PointerValSet &getLink(unsigned i) {
     assert(i < getNumLinks() && "Field links access out of range...");
@@ -163,6 +168,7 @@ public:
   }
 
   void print(std::ostream &O) const;
+  void dump() const;
 
   virtual std::string getCaption() const = 0;
   virtual const std::vector<PointerValSet> *getAuxLinks() const {
diff --git a/include/llvm/Analysis/DataStructureGraph.h b/include/llvm/Analysis/DataStructureGraph.h
index 6798969..3b6ff74 100644
--- a/include/llvm/Analysis/DataStructureGraph.h
+++ b/include/llvm/Analysis/DataStructureGraph.h
@@ -11,19 +11,24 @@
 
 #include "Support/GraphTraits.h"
 #include "llvm/Analysis/DataStructure.h"
-#include "llvm/Value.h"  // FIXME: Move cast/dyn_cast out to Support
 
 class DSNodeIterator : public std::forward_iterator<DSNode, ptrdiff_t> {
+  friend class DSNode;
   DSNode * const Node;
   unsigned Link;
   unsigned LinkIdx;
   
   typedef DSNodeIterator _Self;
-public:
-  DSNodeIterator(DSNode *N) : Node(N), Link(0), LinkIdx(0) {}  // begin iterator
+
+  DSNodeIterator(DSNode *N) : Node(N), Link(0), LinkIdx(0) {   // begin iterator
+    unsigned NumLinks = Node->getNumOutgoingLinks();
+    while (Link < NumLinks && Node->getOutgoingLink(Link).empty())
+      ++Link;
+  }
   DSNodeIterator(DSNode *N, bool)       // Create end iterator
     : Node(N), Link(N->getNumOutgoingLinks()), LinkIdx(0) {
   }
+public:
 
   bool operator==(const _Self& x) const {
     return Link == x.Link && LinkIdx == x.LinkIdx;
@@ -39,7 +44,10 @@ public:
     if (LinkIdx < Node->getOutgoingLink(Link).size()-1)
       ++LinkIdx;
     else {
-      ++Link;
+      unsigned NumLinks = Node->getNumOutgoingLinks();
+      do {
+        ++Link;
+      } while (Link < NumLinks && Node->getOutgoingLink(Link).empty());
       LinkIdx = 0;
     }
     return *this;
@@ -52,16 +60,15 @@ public:
 
 template <> struct GraphTraits<DSNode*> {
   typedef DSNode NodeType;
-  typedef DSNodeIterator ChildIteratorType;
+  typedef DSNode::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(DSNode *N) { return N; }
-  static ChildIteratorType child_begin(NodeType *N) { 
-    return DSNodeIterator(N);
-  }
-  static ChildIteratorType child_end(NodeType *N) { 
-    return DSNodeIterator(N, true);
-  }
+  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
+  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 };
 
+// Provide iterators for DSNode...
+inline DSNode::iterator DSNode::begin() { return DSNodeIterator(this); }
+inline DSNode::iterator DSNode::end()   { return DSNodeIterator(this, false); }
 
 #endif