[LLVMdev] [PATCH] Add functionality to scc_iterator

[Patrick Alexander Simmons]

Chris Lattner wrote:
> It's more of an algorithm than a datastructure.  Where else in the  
> codebase would it be useful to use?  If only in one place, it is  
> probably reasonable to put it near the code that uses it.
>
> -Chris
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>   
I'm not sure where specifically it might be useful in the codebase; I 
wrote it for use in an external (currently not public) project.  I could 
just put it in the utility header for that project, but then it wouldn't 
be available to others, so I thought SCCIterator.h would be a better 
place.  I figured people who'd be interested in detecting cycles might 
look in SCCIterator.h for a way to do so and find that code.  It could 
also serve as an example of how to use scc_iterator, and, since it's a 
template, there's no penalty for having it in there if it's not used 
anywhere.  What a deal, right?

If you don't want it in LLVM, I'll put it back in my utility header 
file, but I've included it in my revised patch in case you change your 
mind.  The revised patch does the following things:
1.  Changes the templates of scc_begin and scc_end to pass by constant 
reference rather than value (no reason to do a copy unless you have to).
2.  Adds the inverse graph scc_begin and scc_end templates (similarly 
fixed to pass by constant reference rather than value).
3.  Adds the cycle-detection code as "is_in_cycle" rather than 
"bb_reachable".
3.  Fixes an incorrect comment in the GraphTraits.h header.

Index: include/llvm/ADT/SCCIterator.h
===================================================================
--- include/llvm/ADT/SCCIterator.h      (revision 76093)
+++ include/llvm/ADT/SCCIterator.h      (working copy)
@@ -135,8 +135,8 @@
   typedef scc_iterator<GraphT, GT> _Self;

   // Provide static "constructors"...
-  static inline _Self begin(GraphT& G) { return 
_Self(GT::getEntryNode(G)); }
-  static inline _Self end  (GraphT& G) { return _Self(); }
+  static inline _Self begin(const GraphT& G) { return 
_Self(GT::getEntryNode(G)); }
+  static inline _Self end  (const GraphT& G) { return _Self(); }

   // Direct loop termination test (I.fini() is more efficient than I == 
end())
   inline bool fini() const {
@@ -185,15 +185,43 @@

 // Global constructor for the SCC iterator.
 template <class T>
-scc_iterator<T> scc_begin(T G) {
+scc_iterator<T> scc_begin(const T& G) {
   return scc_iterator<T>::begin(G);
 }

 template <class T>
-scc_iterator<T> scc_end(T G) {
+scc_iterator<T> scc_end(const T& G) {
   return scc_iterator<T>::end(G);
 }

+template <class T>
+scc_iterator<Inverse<T> > scc_begin(const Inverse<T>& G) {
+       return scc_iterator<Inverse<T> >::begin(G);
+}
+
+template <class T>
+scc_iterator<Inverse<T> > scc_end(const 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 is_in_cycle(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
Index: include/llvm/ADT/GraphTraits.h
===================================================================
--- include/llvm/ADT/GraphTraits.h      (revision 76093)
+++ include/llvm/ADT/GraphTraits.h      (working copy)
@@ -30,7 +30,7 @@
   // typedef NodeType          - Type of Node in the graph
   // typedef ChildIteratorType - Type used to iterate over children in 
graph

-  // static NodeType *getEntryNode(GraphType *)
+  // static NodeType *getEntryNode(const GraphType &)
   //    Return the entry node of the graph

   // static ChildIteratorType child_begin(NodeType *)