Andrew Kelley via llvm-dev
2017-Oct-21 17:43 UTC
[llvm-dev] conceiving of a frontend feature which requires LLVM support: builtin to determine stack size upper bound
Here is a feature I would like to introduce to my frontend: A builtin function to calculate the upper bound of the stack size of any given function. The idea here is that, if we do not have any: * external library calls * alloca * indirect function calls * non-tail-recursion * inline assembly that modifies the stack pointer Then, we can look at a given function and determine precisely how much stack space is needed to spawn a thread to run that function. This provides two benefits: * Statically guarantee that stack overflow will not occur * Threads can have smaller stack sizes, lowering the cost of creating a thread This feature requires tight coupling with LLVM, because: * We need to know the stack size post-optimizations * Frontend needs to make a compile error if non-tail-recursion occurs, but LLVM might introduce (or remove?) tail recursion, and so we would need to capture this error from LLVM and report it back in the frontend. What do you think? Is this feature reasonable to achieve with LLVM and in scope of the LLVM project? I would propose an LLVM builtin function to perform this calculation, and I can work on a proof-of-concept if llvm-dev thinks this idea is worth pursuing. Upstream issue: https://github.com/zig-lang/zig/issues/157 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171021/01fedbb5/attachment.html>
Manuel Jacob via llvm-dev
2017-Oct-22 01:23 UTC
[llvm-dev] conceiving of a frontend feature which requires LLVM support: builtin to determine stack size upper bound
[+CC John Regehr] Hi Andrew, Good to know that someone is working on a feature like this. Many languages - even those used for embedded applications - are happily ignoring the issue of an overflowing stack. Some comments inline... On 2017-10-21 19:43, Andrew Kelley via llvm-dev wrote:> Here is a feature I would like to introduce to my frontend: > > A builtin function to calculate the upper bound of the stack size of > any > given function. > > The idea here is that, if we do not have any: > * external library callsAs was discussed in the upstream issue, this can be solved by providing the upper stack size bound for the external function. LLVM's function attributes can be used for this.> * allocaI was going to write that this shouldn't be problem. But of course there are variably-sized allocas, which are hard to support.> * indirect function callsThese can be supported by passing the upper bound along with the function pointer.> * non-tail-recursionIn some cases, a tight upper bound can be calculated even for recursive functions, although this is non-trivial and impossible to do for the general case.> * inline assembly that modifies the stack pointer > > Then, we can look at a given function and determine precisely how much > stack space is needed to spawn a thread to run that function. This > provides > two benefits: > * Statically guarantee that stack overflow will not occur > * Threads can have smaller stack sizes, lowering the cost of creating > a > thread > > This feature requires tight coupling with LLVM, because: > * We need to know the stack size post-optimizations > * Frontend needs to make a compile error if non-tail-recursion occurs, > but > LLVM might introduce (or remove?) tail recursion, and so we would need > to > capture this error from LLVM and report it back in the frontend. > > > What do you think? Is this feature reasonable to achieve with LLVM and > in > scope of the LLVM project?Writing this analysis on the MIR level shouldn't be too difficult. The basic pieces (for a single function) are already there. Search LLVM's source code for "FrameLowering" and "MachineFrameInfo". Your analysis would have to scan the machine code for function calls to find the worst case call sequence. The machine code can contain calls to additional functions, like memcpy and functions from compiler-rt, whose stack usage information has to be provided externally. For embedded applications you have to keep in mind interrupts. A possible solution is described in this paper: https://www.cs.utah.edu/~regehr/papers/p751-regehr.pdf> I would propose an LLVM builtin function to perform this calculation, > and I > can work on a proof-of-concept if llvm-dev thinks this idea is worth > pursuing.What do you mean by "LLVM builtin function"? -Manuel> > Upstream issue: https://github.com/zig-lang/zig/issues/157 > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Hal Finkel via llvm-dev
2017-Oct-23 14:07 UTC
[llvm-dev] conceiving of a frontend feature which requires LLVM support: builtin to determine stack size upper bound
On 10/21/2017 12:43 PM, Andrew Kelley via llvm-dev wrote:> Here is a feature I would like to introduce to my frontend: > > A builtin function to calculate the upper bound of the stack size of > any given function. > > The idea here is that, if we do not have any: > * external library calls > * alloca > * indirect function calls > * non-tail-recursion > * inline assembly that modifies the stack pointer > > Then, we can look at a given function and determine precisely how much > stack space is needed to spawn a thread to run that function. This > provides two benefits: > * Statically guarantee that stack overflow will not occur > * Threads can have smaller stack sizes, lowering the cost of creating > a thread > > This feature requires tight coupling with LLVM, because: > * We need to know the stack size post-optimizations > * Frontend needs to make a compile error if non-tail-recursion > occurs, but LLVM might introduce (or remove?) tail recursion, and so > we would need to capture this error from LLVM and report it back in > the frontend. > > > What do you think? Is this feature reasonable to achieve with LLVM and > in scope of the LLVM project? > > I would propose an LLVM builtin function to perform this calculation, > and I can work on a proof-of-concept if llvm-dev thinks this idea is > worth pursuing.Would a builtin function be the best way to expose this information? Maybe generating a side table would be best? As I recall, we already produce some stack-size information as part of our StackMap table (see https://llvm.org/docs/StackMaps.html). Another option could be some special form of prefix/prologue data (http://llvm.org/docs/LangRef.html#prefix-data / http://llvm.org/docs/LangRef.html#prologue-data). The "@stack_size(function)" you've discussed on the zig issue may not be implementable in general (because we'd need some way of making sure that we always generate code for "@foo" before any other function containing a call to "@stack_size(@foo)", and that's probably not possible in general). -Hal> > > Upstream issue: https://github.com/zig-lang/zig/issues/157 > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171023/b87e56a1/attachment.html>