Identifying recursive functions in a backend

Hi,

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?

Thanks,
Rob

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.

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.