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

Chris Lattner wrote:
> On Aug 4, 2009, at 3:48 PM, Patrick Alexander Simmons wrote:
>
>   
>> 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?
>>     
>
> Hi Patrick,
>
> The scc_begin/end specializations look fine.  The "bb_reachable"
name
> is not a good one though, it doesn't give any hint about what the  
> function actually does.  I don't think it is really generally useful  
> enough to include in scciterator.h
>
> -Chris
>   
I agree that bb_reachable is not the best name.  How about
"is_in_cycle"
instead?  I think a function to tell whether an arbitrary graph node is 
part of a cycle could be useful in a variety of circumstances; is there 
another header file where it would be more appropriate?

--Patrick

On Aug 6, 2009, at 4:19 PM, Patrick Alexander Simmons wrote:
> Chris Lattner wrote:
>> On Aug 4, 2009, at 3:48 PM, Patrick Alexander Simmons wrote:
>>
>>
>>> 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?
>>>
>>
>> Hi Patrick,
>>
>> The scc_begin/end specializations look fine.  The
"bb_reachable" name
>> is not a good one though, it doesn't give any hint about what the
>> function actually does.  I don't think it is really generally
useful
>> enough to include in scciterator.h
>>
>> -Chris
>>
> I agree that bb_reachable is not the best name.  How about  
> "is_in_cycle"
> instead?  I think a function to tell whether an arbitrary graph node  
> is
> part of a cycle could be useful in a variety of circumstances; is  
> there
> another header file where it would be more appropriate?
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

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 *)