thr3ads.net - llvm dev - [LLVMdev] [PATCH] Add functionality to scc

If this information is useful, please help other people find it:
Share via:

Patrick Alexander Simmons

2009-Aug-07 19:22 UTC

[LLVMdev] [PATCH] Add functionality to scc_iterator

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

Vikram S. Adve

2009-Aug-07 19:51 UTC

head link

[LLVMdev] [PATCH] Add functionality to scc_iterator

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

Chris Lattner

2009-Aug-08 18:33 UTC

head link

[LLVMdev] [PATCH] Add functionality to scc_iterator

On Aug 7, 2009, at 12:51 PM, Vikram S. Adve wrote:
> 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.
These typically don't use the scciterator though.

-Chris

Possibly Parallel Threads

Search for more apparently analagous threads

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

[LLVMdev] [PATCH] Add functionality to scc_iterator

[LLVMdev] [PATCH] Add functionality to scc_iterator

[LLVMdev] [PATCH] Add functionality to scc_iterator

Possibly Parallel Threads