similar to: [LLVMdev] Identify recursion in a call graph

Displaying 20 results from an estimated 900 matches similar to: "[LLVMdev] Identify recursion in a call graph"

2010 Nov 01
2
[LLVMdev] Identify recursion in a call graph
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
2010 Oct 30
0
[LLVMdev] Identify recursion in a call graph
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
2010 Nov 02
0
[LLVMdev] Identify recursion in a call graph
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)
2010 Nov 02
2
[LLVMdev] Identify recursion in a call graph
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 >
2010 Nov 02
0
[LLVMdev] Identify recursion in a call graph
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
2010 Nov 05
3
[LLVMdev] Identify recursion in a call graph
On Nov 2, 2010, at 11:08 PM, Nick Lewycky wrote: > The unittests/ directory contains C++ unit tests for arbitrary C++ > APIs > that don't fit the dejagnu model of running opt or llc over .ll files. Thanks for the tip. Attached is a patch+testcase that adds CallGraphNode::isRecursive to LLVM. Could someone with commit access please review and apply? Thanks, Trevor
2010 Nov 03
2
[LLVMdev] Identify recursion in a call graph
On Nov 2, 2010, at 12:53 PM, Jeff Kunkel wrote: > 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. I've modified the code so that it correctly identifies both direct and indirect recursion. I'm now trying to package it up as a patch for the
2009 Aug 07
0
[LLVMdev] [PATCH] Add functionality to scc_iterator
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" >>>
2009 Aug 06
2
[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
2009 Aug 07
2
[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
2009 Aug 04
2
[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) +++
2010 Nov 03
0
[LLVMdev] Identify recursion in a call graph
Trevor Harmon wrote: > On Nov 2, 2010, at 12:53 PM, Jeff Kunkel wrote: > >> 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. > > I've modified the code so that it correctly identifies both direct and > indirect recursion.
2006 Sep 29
2
[LLVMdev] FunctionPass requiring SCCs
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?
2009 Sep 03
3
[LLVMdev] SCCIterator and unconnected graphs
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
2009 Sep 15
0
[LLVMdev] SCCIterator and unconnected graphs
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
2009 Aug 06
0
[LLVMdev] [PATCH] Add functionality to scc_iterator
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
2009 Aug 08
3
[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
2010 Nov 06
0
[LLVMdev] Identify recursion in a call graph
On Nov 5, 2010, at 3:21 PM, Trevor Harmon wrote: > On Nov 2, 2010, at 11:08 PM, Nick Lewycky wrote: > >> The unittests/ directory contains C++ unit tests for arbitrary C++ APIs >> that don't fit the dejagnu model of running opt or llc over .ll files. > > Thanks for the tip. Attached is a patch+testcase that adds CallGraphNode::isRecursive to LLVM. Could someone with
2009 Sep 15
1
[LLVMdev] SCCIterator and unconnected graphs
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 >>
2009 Aug 07
0
[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