[LLVMdev] Identifying recursive functions in a backend
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
-- 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
More information about the llvm-dev