[LLVMdev] Identify recursion in a call graph

[Nick Lewycky]

Trevor Harmon wrote:
> 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?

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. 
Read through a few of them as examples, or see upstream's documentation at:

   http://code.google.com/p/googletest/wiki/Documentation

As an aside, there's a method called LoadAssembly in 
unittests/ExecutionEngine/JITTest.cpp that should probably be refactored 
somewhere more general. It's great for embedding .ll text inside a unit 
test.

Nick