[LLVMdev] [PATCH] Add functionality to scc_iterator

[Patrick Alexander Simmons]

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?

(Sorry for the double post; previous patch didn't compile.)

--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 std::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