Patrick Alexander Simmons
2009-Aug-04 22:48 UTC
[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
Patrick Alexander Simmons
2009-Aug-06 23:19 UTC
[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
Reasonably Related Threads
- [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
- [LLVMdev] [PATCH] Add functionality to scc_iterator