similar to: [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) +++

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

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

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

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" >>>

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

Hello, I posted an earlier version of this patch some months ago and realized I've still been sitting on it. The earlier version of this patch was rejected for adding a cycle detection function to SCCIterator.h. This function is now removed. This patch makes the following changes: 1. Allow SCCIterator to work with GraphT types that are constant. 2. Allow SCCIterator to work with

On Oct 30, 2010, at 4:38 AM, Duncan Sands wrote: >> Is there any facility in LLVM to identify recursion in a call graph? ... > use the facilities in SCCIterator.h, or declare your pass to be a > CallGraphSCCPass in which case it will work one strongly connected > component at a time. Converting my ModulePass to a CallGraphSCCPass doesn't seem feasible, so I'll use

Hi Trevor, > Converting my ModulePass 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)

Hi you basically need to find a cycles in the call graph. Do do this just search google for a graph algorithm, then make it for your problem. See http://en.wikipedia.org/wiki/Cycle_detection. Jeff Kunkel On Tue, Nov 2, 2010 at 4:27 AM, Duncan Sands <baldrick at free.fr> wrote: > Hi Trevor, > > > Converting my ModulePass to a CallGraphSCCPass doesn't seem feasible, so >

Also, could you write this in a separate pass, and obtain the results from getAnalysis()? I think others would find it useful to discover if a Function may be called recursively. -Jeff Kunkel On Tue, Nov 2, 2010 at 2:38 PM, Jeff Kunkel <jdkunk3 at gmail.com> wrote: > Hi you basically need to find a cycles in the call graph. Do do this just > search google for a graph algorithm, then

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

Hi Ryan, On 9/29/06, Ryan M. Lefever <lefever at crhc.uiuc.edu> wrote: > 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 >

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

Chris Lattner wrote: > On Sep 3, 2009, at 4:15 AM, Hans Vandierendonck wrote: > Hi, >> >> I am using the scc_iterator class in my code on a CallGraph, where some >> functions are not called from within the module. It seems that >> scc_iterator does not list all SCCs if the graph is not connected; only >> those nodes connected to the node pointed to by >>

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

Chris Lattner wrote: > 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

On Sep 3, 2009, at 4:15 AM, Hans Vandierendonck wrote: Hi, > > I am using the scc_iterator class in my code on a CallGraph, where > some > functions are not called from within the module. It seems that > scc_iterator does not list all SCCs if the graph is not connected; > only > those nodes connected to the node pointed to by > GraphTraits<...>::getEntryNode() are

Hi, I am using the scc_iterator class in my code on a CallGraph, where some functions are not called from within the module. It seems that scc_iterator does not list all SCCs if the graph is not connected; only those nodes connected to the node pointed to by GraphTraits<...>::getEntryNode() are returned. Can someone verify this behavior? Any tips on how I should go about extending the

I printed the call graph as you suggested. The bugpoint bytecode that I sent below prints the following call graph: Indirect call node / | | \ / | | \ V | V V execute | prog_char clear_func | | V V push_constant | V Node0x8d7b370 i.e., Indirect call node -> execute