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 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*> &nextSCC = *SCCI; if (nextSCC.size() == 1 && SCCI.hasLoop()) { return true; } } return false; } This correctly identifies direct (self) recursion but fails to identify indirect recursion, such as: void foo() { bar(); } void bar() { foo(); } Any suggestions on how to identify both types? Thanks, Trevor P.S. Is it possible to start the call graph traversal from a particular function, rather than from getRoot()? Setting rootNode to "new CallGraphNode(myFunction)" causes isRecursive to return false, even with direct recursion.
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<CallGraphNode*> &nextSCC = *SCCI; > if (nextSCC.size() == 1 && SCCI.hasLoop()) { > return true; > } > } > return false; > } > > This correctly identifies direct (self) recursion but fails to identify indirect > recursion, such as: > > void foo() { bar(); } > void bar() { foo(); } > > Any suggestions on how to identify both types? Thanks,in this case nextSCC.size() will be 2, so your logic will not consider it. Ciao, Duncan.> P.S. Is it possible to start the call graph traversal from a particular > function, rather than from getRoot()? Setting rootNode to "new > CallGraphNode(myFunction)" causes isRecursive to return false, even with direct > recursion.I don't know.
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 > 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*> &nextSCC = *SCCI; > > if (nextSCC.size() == 1 && SCCI.hasLoop()) { > > return true; > > } > > } > > return false; > > } > > > > This correctly identifies direct (self) recursion but fails to identify > indirect > > recursion, such as: > > > > void foo() { bar(); } > > void bar() { foo(); } > > > > Any suggestions on how to identify both types? Thanks, > > in this case nextSCC.size() will be 2, so your logic will not consider it. > > Ciao, > > Duncan. > > > P.S. Is it possible to start the call graph traversal from a particular > > function, rather than from getRoot()? Setting rootNode to "new > > CallGraphNode(myFunction)" causes isRecursive to return false, even with > direct > > recursion. > > I don't know. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101102/68d48e51/attachment.html>