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>
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 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/60c46f10/attachment.html>
On Nov 2, 2010, at 12:53 PM, Jeff Kunkel wrote:> 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.I've modified the code so that it correctly identifies both direct and indirect recursion. I'm now trying to package it up as a patch for the LLVM trunk so that others can use it. Your suggestion to create a new pass for the code is interesting, but I'm not sure that this feature warrants an entirely new pass. Maybe it's more appropriate to integrate with the existing CallGraph pass by adding an isRecursive method to CallGraphNode. For example: AU.addRequired<CallGraph>(); ... CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); if (rootNode->isRecursive()) { ... } But I have no idea how to write a test case for this. It appears that LLVM is not set up for unit tests of individual API calls. Any thoughts? Trevor