llvm dev - Nov 2010 - [LLVMdev] Identify recursion in a call graph

Hi,

Is there any facility in LLVM to identify recursion in a call graph? I  
realize this is undecidable in the general case due to function  
pointers, but at least the static cases could be identified. I don't  
even care about whole-program recursion, just looking at a single  
module would suffice. But I don't see anything like this already in  
LLVM, so do I simply write some code to look for cycles in the call  
graph? Thanks,

Trevor

Hi Trevor,
> Is there any facility in LLVM to identify recursion in a call graph? I
> realize this is undecidable in the general case due to function
> pointers, but at least the static cases could be identified. I don't
> even care about whole-program recursion, just looking at a single
> module would suffice. But I don't see anything like this already in
> LLVM, so do I simply write some code to look for cycles in the call
> graph? Thanks,
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.

Ciao,

Duncan.

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.