Displaying 20 results from an estimated 500 matches similar to: "[LLVMdev] [PATCH] Add functionality to scc_iterator"
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 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 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
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 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
2009 Aug 04
0
[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?
--Patrick
--- include/llvm/ADT/SCCIterator.h (revision 76093)
+++ include/llvm/ADT/SCCIterator.h (working copy)
@@ -194,6 +194,34 @@
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 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)
2009 Nov 16
2
[LLVMdev] [PATCH] ADT Fixups
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
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 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 Oct 29
2
[LLVMdev] Identify recursion in a call graph
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
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
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
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
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 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
2009 Aug 08
0
[LLVMdev] [PATCH] Add functionality to scc_iterator
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
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?
2006 Sep 29
0
[LLVMdev] FunctionPass requiring SCCs
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
>