search for: scc_iterator

Displaying 20 results from an estimated 32 matches for "scc_iterator".

2009 Aug 07
2
[LLVMdev] [PATCH] Add functionality to 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...
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 --- incl...
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" >>> function to tell whether an arbitrary graph node is part of cycle. >>> Might this be useful to others? >>> >> >> Hi Patrick, &gt...
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 others? >> > > Hi Patrick, > > The scc_begi...
2009 Aug 07
0
[LLVMdev] [PATCH] Add functionality to scc_iterator
...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...
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 fine. The "...
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/...
2009 Nov 16
2
[LLVMdev] [PATCH] ADT Fixups
...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...
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 ve...
2010 Nov 01
2
[LLVMdev] Identify recursion in a call graph
...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*> &...
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()...
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
2017 Aug 09
2
[ThinLTO] Suggestions on how to traverse SCCs in the Module Summary Index bottom up
...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...
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
2006 Dec 04
1
[LLVMdev] problem using scc_iterator on CallGraph
...-> 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...
2006 Dec 04
0
[LLVMdev] problem using scc_iterator on CallGraph
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...
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) { > const std::vector<C...
2006 Dec 04
2
[LLVMdev] problem using scc_iterator on CallGraph
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...
2010 Nov 02
2
[LLVMdev] Identify recursion in a call graph
...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...
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 >> GraphTraits<...>::getEntryNode...