[LLVMdev] [PATCH] Add functionality to scc_iterator

[Chris Lattner]

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