[LLVMdev] Identify recursion in a call graph

[Trevor Harmon]

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.