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?

(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

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
>
>
> (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
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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