On Nov 2, 2010, at 11:08 PM, Nick Lewycky wrote:> The unittests/ directory contains C++ unit tests for arbitrary C++ > APIs > that don't fit the dejagnu model of running opt or llc over .ll files.Thanks for the tip. Attached is a patch+testcase that adds CallGraphNode::isRecursive to LLVM. Could someone with commit access please review and apply? Thanks, Trevor -------------- next part -------------- A non-text attachment was scrubbed... Name: isRecursive_LLVM-2.8.patch Type: application/octet-stream Size: 1726 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101105/7a5e7a84/attachment.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: isRecursive_LLVM-trunk.patch Type: application/octet-stream Size: 1726 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101105/7a5e7a84/attachment-0001.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: CallGraphTest.cpp Type: application/octet-stream Size: 8522 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101105/7a5e7a84/attachment-0002.obj> -------------- next part --------------
On Fri, Nov 5, 2010 at 11:21 PM, Trevor Harmon <trevor.w.harmon at nasa.gov> wrote:> On Nov 2, 2010, at 11:08 PM, Nick Lewycky wrote: > Thanks for the tip. Attached is a patch+testcase that adds > CallGraphNode::isRecursive to LLVM. Could someone with commit access please > review and apply? Thanks,I don't have commit access, but I can review: + const std::vector<CallGraphNode*> &nextSCC = *SCCI; + if (nextSCC.size() > 1 || SCCI.hasLoop()) { + return true; + } The "nextSCC.size() > 1" is redundant because SCCI.hasLoop() already checks that first thing. Because of this, the nextSCC declaration can be removed entirely.
On Nov 5, 2010, at 3:21 PM, Trevor Harmon wrote:> On Nov 2, 2010, at 11:08 PM, Nick Lewycky wrote: > >> The unittests/ directory contains C++ unit tests for arbitrary C++ APIs >> that don't fit the dejagnu model of running opt or llc over .ll files. > > Thanks for the tip. Attached is a patch+testcase that adds CallGraphNode::isRecursive to LLVM. Could someone with commit access please review and apply? Thanks,Hi Trevor, What is the desired behavior for code like this? extern void bar(); void foo() { ... bar(); ... } In this situation, the call graph will report that foo is not recursive. However, it *is* possible that bar has an implementation that calls foo. The call graph originally modeled this possibility explicitly, but it turns that that this makes almost all functions end up in a single big SCC. Since one of the most important clients of the CallGraph are CallGraphSCC passes, I changed the call graph to stop modeling this behavior, instead using two different abstract nodes. How do you think should be handled? At the very least, the comments on isRecursive should mention this case. -Chris
Sorry for the delay in my reply. I was at a conference. It would of course be desirable to identify this pattern, but I'm not sure what effort would be involved in doing so. If it is difficult, I think it would be acceptable to define recursion as "recursion that is explicitly present in the LLVM CallGraph", not necessarily recursion that is present in the code. A documentation note to that effect should suffice, though perhaps it could be worded better? What do you think? Trevor On Nov 5, 2010, at 10:38 PM, Chris Lattner wrote:> What is the desired behavior for code like this? > > extern void bar(); > void foo() { > ... > bar(); > ... > } > > In this situation, the call graph will report that foo is not > recursive. However, it *is* possible that bar has an implementation > that calls foo. The call graph originally modeled this possibility > explicitly, but it turns that that this makes almost all functions > end up in a single big SCC. Since one of the most important clients > of the CallGraph are CallGraphSCC passes, I changed the call graph > to stop modeling this behavior, instead using two different abstract > nodes. > > How do you think should be handled? At the very least, the comments > on isRecursive should mention this case.