[LLVMdev] Identifying recursive functions in a backend

John Criswell criswell at uiuc.edu
Thu Jan 14 07:23:48 PST 2010

Anton Korobeynikov wrote:
> Hello, Robert
>> I was wondering if it was possible to detect if a function is recursive in a back-end. For instance, I'd like to be able to say: "If this function we are about to call is recursive, store the return address to the stack, if it isn't we don't need a stack so do nothing". Does anyone know if this is possible?
> Well, in general - no. Think about the function which does an indirect call...
> If you want some approximation - find all call sites in the function
> and check the destinations.
More completely, you need to find Strongly Connected Components (SCCs) 
in the call graph.  Indirect function calls will simply make the call 
graph more conservative than it needs to be because you will have 
conservative estimates of what functions can be called at the indirect 
function call site.

What you could do is write a pure LLVM pass that locates SCCs and marks 
functions that are part of an SCC with a special attribute.  Your code 
generator pass could then check this attribute when generating code for 
each function.

-- John T.

> --
> With best regards, Anton Korobeynikov
> Faculty of Mathematics and Mechanics, Saint Petersburg State University
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

More information about the llvm-dev mailing list