[LLVMdev] Fixed DSGraph iteration, depth first search, etc...

[Chris Lattner]

The following now works for me:

    const DSNode *N1 = ...;
    df_iterator<const DSNode*> X1 = df_begin(N1), XE1 = df_end(N1);

    DSNode *N2 = ...;
    df_iterator<DSNode*> X2 = df_begin(N2), XE2 = df_end(N2);

You need the following #includes:

#include "Support/DepthFirstIterator.h"
#include "llvm/Analysis/DSGraphTraits.h"

You need this patch:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021118/001623.html

and this patch:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021118/001628.html

Unfortunately, I hadn't commited a bunch of stuff before I did this, so
there are some extra things mixed in with the second patch.  The following
hunks should be enough to get DSNode iteration working (with the first
linked patch):

--- llvm/include/llvm/Analysis/DSSupport.h:1.7	Sun Nov 10 17:46:51 2002
+++ llvm/include/llvm/Analysis/DSSupport.h	Mon Nov 18 15:45:07 2002
@@ -20,7 +20,6 @@

 class DSNode;                  // Each node in the graph
 class DSGraph;                 // A graph for a function
-class DSNodeIterator;          // Data structure graph traversal iterator

 namespace DS { // FIXME: After the paper, this should get cleaned up
   enum { PointerShift = 3,     // 64bit ptrs = 3, 32 bit ptrs = 2

--- llvm/include/llvm/Analysis/DSNode.h:1.14	Sun Nov 10 00:48:24 2002
+++ llvm/include/llvm/Analysis/DSNode.h	Mon Nov 18 15:45:30 2002
@@ -8,6 +8,8 @@
 #define LLVM_ANALYSIS_DSNODE_H

 #include "llvm/Analysis/DSSupport.h"
+template<typename BaseType>
+class DSNodeIterator;          // Data structure graph traversal iterator


//===----------------------------------------------------------------------===//
 /// DSNode - Data structure node class
@@ -76,11 +79,13 @@
     assert(Referrers.empty() && "Referrers to dead node exist!");
   }

-  // Iterator for graph interface...
-  typedef DSNodeIterator iterator;
-  typedef DSNodeIterator const_iterator;
-  inline iterator begin() const;   // Defined in DSGraphTraits.h
-  inline iterator end() const;
+  // Iterator for graph interface... Defined in DSGraphTraits.h
+  typedef DSNodeIterator<DSNode> iterator;
+  typedef DSNodeIterator<const DSNode> const_iterator;
+  inline iterator begin();
+  inline iterator end();
+  inline const_iterator begin() const;
+  inline const_iterator end() const;

   //===--------------------------------------------------
   // Accessors

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/