search for: scc_iterators

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

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

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

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

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

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

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

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

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

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

Hey all, I'm working on adding function attribute propagation to function summaries in the ThinLTO index, and have run into some trouble with ensuring bottom-up traversal when finding the SCCs in the call graph. I'm basing my implementation for the GraphTraits for the ModuleSummaryIndex off the GraphTraits<CallGraph *> implementation (

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

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

On Sun, 3 Dec 2006, Ryan M. Lefever wrote: > I am working on a transform that uses an scc_iterator on a program's > CallGraph. However, I am running into a problem in which not all > callees are being processed before callers, leading me to believe there > might be a bug. In particular, this is happening in a case where a > callee is a function pointer. I ran bugpoint and

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)

I am working on a transform that uses an scc_iterator on a program's CallGraph. However, I am running into a problem in which not all callees are being processed before callers, leading me to believe there might be a bug. In particular, this is happening in a case where a callee is a function pointer. I ran bugpoint and have included the bugpoint-reduced-simplified.ll below. If

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 >

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