search for: scc_end

...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 &quo...

On Aug 6, 2009, at 4:19 PM, Patrick Alexander Simmons wrote: > 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" >>>

...ywhere. 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_cycl...

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

...py) @@ -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_iterat...

...ool fini() const { @@ -185,15 +185,25 @@ // 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...

...s to a CallGraphSCCPass doesn't seem feasible, so I'll use llvm::scc_iterator. Here's what I have so far: bool MyModulePass::isRecursive() { CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = scc_end(rootNode); SCCI != E; ++SCCI) { const std::vector<CallGraphNode*> &nextSCC = *SCCI; if (nextSCC.size() == 1 && SCCI.hasLoop()) { return true; } } return false; } This correctly identifies direct (self) recursion but fails to identify indirect recursion, such as: voi...

...y) @@ -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_itera...

...doesn't seem feasible, so I'll > use llvm::scc_iterator. Here's what I have so far: > > bool MyModulePass::isRecursive() { > CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); > for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = > scc_end(rootNode); SCCI != E; ++SCCI) { > const std::vector<CallGraphNode*> &nextSCC = *SCCI; > if (nextSCC.size() == 1 && SCCI.hasLoop()) { > return true; > } > } > return false; > } > > This correctly identifies direct (self) recursion but fails to identify in...

...tor<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 a...

...I'll > > use llvm::scc_iterator. Here's what I have so far: > > > > bool MyModulePass::isRecursive() { > > CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); > > for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = > > scc_end(rootNode); SCCI != E; ++SCCI) { > > const std::vector<CallGraphNode*> &nextSCC = *SCCI; > > if (nextSCC.size() == 1 && SCCI.hasLoop()) { > > return true; > > } > > } > > return false; > > } > > > > This correctly identifies dir...

Hi, Is there any facility in LLVM to identify recursion in a call graph? I realize this is undecidable in the general case due to function pointers, but at least the static cases could be identified. I don't even care about whole-program recursion, just looking at a single module would suffice. But I don't see anything like this already in LLVM, so do I simply write some code to

Hi Trevor, > Is there any facility in LLVM to identify recursion in a call graph? I > realize this is undecidable in the general case due to function > pointers, but at least the static cases could be identified. I don't > even care about whole-program recursion, just looking at a single > module would suffice. But I don't see anything like this already in > LLVM, so do

I have a FunctionPass F that needs a list of all the SCCs for use in its doFinalization() method. Let's say I write a CallGraphSCCPass C that creates an array of all SCCs. Let C be required by F, and let F call getAnalysis<C>() from its doFinalization() method. Am I guaranteed that C's runOnSCC() method will have executed on all SCCs before F's doFinalization() method?

...build the array of SCCs? If not, how else might I structure things? That should work. I've written such code, something like: bool doFinalization(Module &M) { CallGraph &CG = getAnalysis<CallGraph>(); for (scc_iterator<CallGraph*> SCCI = scc_begin(&CG), SCCE = scc_end(&CG); SCCI != SCCE; ++SCCI) { unsigned size = (*SCCI).size(); for (unsigned i = 0; i < size; ++i) { Function *F = (*SCCI)[i]->getFunction(); ...... } } .... } Check out scc_* iterators. Also note that the call graph is not aware of the indirect calls, so you w...

...use llvm::scc_iterator. Here's what I have so far: >> > >> > bool MyModulePass::isRecursive() { >> > CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); >> > for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), E = >> > scc_end(rootNode); SCCI != E; ++SCCI) { >> > const std::vector<CallGraphNode*> &nextSCC = *SCCI; >> > if (nextSCC.size() == 1 && SCCI.hasLoop()) { >> > return true; >> > } >> > } >> > return false; >> > } >> > >&gt...