[LLVMdev] [PATCH] Add functionality to scc_iterator

[Vikram S. Adve]

Checking if a graph node is in a cycle or not must be a relatively  
common query.  E.g., we used this on DS graphs to decide if DS node  
represented multiple objects or a single object.  It's the basic query  
to decide if a function is part of a recursive computation (a cycle in  
the call graph).  CFGs happen to have special code for natural loops  
but you could use this query to handle irreducible loops as well.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve



On Aug 7, 2009, at 2:22 PM, Patrick Alexander Simmons wrote:

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