llvm dev - Aug 2009 - [LLVMdev] [PATCH] Add functionality to scc_iterator

Hi,

I've been using scc_iterator, and I added the templates necessary to 
make it work with inverse graphs.  I also added a "bb_reachable" 
function to tell whether an arbitrary graph node is part of cycle.  
Might this be useful to others?

--Patrick

--- include/llvm/ADT/SCCIterator.h      (revision 76093)
+++ include/llvm/ADT/SCCIterator.h      (working copy)
@@ -194,6 +194,34 @@
   return scc_iterator<T>::end(G);
 }

+template <class T>
+scc_iterator<Inverse<T> > scc_begin(Inverse<T> G) {
+       return scc_iterator<Inverse<T> >::begin(G);
+}
+
+template <class T>
+scc_iterator<Inverse<T> > scc_end(Inverse<T> G) {
+       return scc_iterator<Inverse<T> >::end(G);
+}
+
+/*Discover whether a graph node is part of any cycle, including a 
self-cycle.*/
+template<class T>
+bool bb_reachable(T* bb)
+{
+       /*Return true iff we are in a nonsingular SCC.*/
+       scc_iterator<T*> cur = scc_begin(bb);
+       while(cur!=scc_end(bb))
+       {
+               for(typename vector<typename 
GraphTraits<T*>::NodeType*>::iterator i = (*cur).begin(); 
i!=(*cur).end(); i++)
+                       if(*i==bb)
+                               return cur.hasLoop();
+               cur++;
+       }
+
+       //We should never get here.
+       abort();
+}
+
 } // End llvm namespace

 #endif