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 - This message is subject to Imagination Technologies' e-mail terms: http://www.imgtec.com/e-mail.htm Imagination Technologies Ltd is a limited company registered in England No: 1306335 Registered Office: Imagination House, Home Park Estate, Kings Langley, Hertfordshire, WD4 8LZ. Email to and from the company may be monitored for compliance and other administrative purposes. - -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100113/f960f540/attachment.html>
Anton Korobeynikov
2010-Jan-13 18:26 UTC
[LLVMdev] Identifying recursive functions in a backend
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. -- With best regards, Anton Korobeynikov Faculty of Mathematics and Mechanics, Saint Petersburg State University
John Criswell
2010-Jan-14 15:23 UTC
[LLVMdev] Identifying recursive functions in a backend
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 >