[LLVMdev] Identify recursion in a call graph

[Jeff Kunkel]

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>