[LLVMdev] Identify recursion in a call graph

[Jeff Kunkel]

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.

-Jeff Kunkel

On Tue, Nov 2, 2010 at 2:38 PM, Jeff Kunkel <jdkunk3 at gmail.com> wrote:

> 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/60c46f10/attachment.html>