search for: scc_iterator

...or that project, but then it wouldn't be available to others, so I thought SCCIterator.h would be a better place. I figured people who'd be interested in detecting cycles might look in SCCIterator.h for a way to do so and find that code. It could also serve as an example of how to use scc_iterator, and, since it's a template, there's no penalty for having it in there if 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 r...

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

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" >>> function to tell whether an arbitrary graph node is part of cycle. >>> Might this be useful to others? >>> >> >> Hi Patrick, &gt...

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 others? >> > > Hi Patrick, > > The scc_begi...

...en it > wouldn't > be available to others, so I thought SCCIterator.h would be a better > place. I figured people who'd be interested in detecting cycles might > look in SCCIterator.h for a way to do so and find that code. It could > also serve as an example of how to use scc_iterator, and, since it's a > template, there's no penalty for having it in there if 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 chan...

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 fine. The "...

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

...it authority please apply this for me? --Patrick Index: include/llvm/ADT/SCCIterator.h =================================================================== --- include/llvm/ADT/SCCIterator.h (revision 88920) +++ include/llvm/ADT/SCCIterator.h (working copy) @@ -135,8 +135,8 @@ typedef scc_iterator<GraphT, GT> _Self; // Provide static "constructors"... - static inline _Self begin(GraphT& G) { return _Self(GT::getEntryNode(G)); } - static inline _Self end (GraphT& G) { return _Self(); } + static inline _Self begin(const GraphT& G) { return _Self(GT::getEnt...

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

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

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()...

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

...7). In the GraphTrait<CallGraph *> definition, the getEntryNode function returns the external calling node ( http://llvm-cs.pcc.me.uk/include/llvm/Analysis/CallGraph.h#450), which I assume is supposed to be at the bottom of the callgraph. Would doing same for the ModuleSummaryIndex ensure the scc_iterator traverses bottom up (if that even makes sense)? Rather than returning a dummy FunctionSummary that's empty for external functions (which is what I'm doing right now), would it make more sense to have one node that represents all external FunctionSummaries? If I used this FunctionSummary as...

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

...-> clear_func execute -> push_constant push_constant -> Node0x8d7b370 First, I'm not exactly sure what Node0x8d7b370 is? In the same bytecode used to produce the call graph above, prog_char is called from push_constant via an indirect call. However, when I use the scc_iterator on the call graph, push_constant is processed before prog_char, even though push_constant calls prog_char. That violates callees before callers. If I want to guarantee that I process callees before callers, and SCCs grouped together, do I need to construct my own callee before caller SCC iter...

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

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) { > const std::vector<C...

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

...our 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 > 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) { &g...

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 >> GraphTraits<...>::getEntryNode...