[llvm-dev] [RFC] Stack overflow and optimizations

[Ralf Jung via llvm-dev]

Hi Michael,

Please keep in mind non-C/C++ frontends. For example, in Rust, we promise to
avoid all undefined behavior in safe code. There is no reasonable compositional
analysis that can statically detect stack overflows (I know safety-critical
systems are subjected such analyses, but those could not reasonably be enforced
on all Rust code -- most of them just forbid recursion, for example), so we
defer to a dynamic check instead: we have a guard page for every thread, and we
make sure that for big stack frames being pushed, every page covered by that
frame is touched at least once (so that we will never skip the guard page).

If LLVM considers stack overflows as UB, the guard page is not enough. Dynamic
checks cannot guard against UB exploited by the compiler. So, in that case it
would become basically impossible to compile a safe language to LLVM, as far as
I can see.

> Two aspects that I forgot to mention in the RFC mail:
> 
> First: In some situations, we already assume that stack overflows are
> unobservable behaviours. For instance, optimizations of stack
> variables cause the stack frames to be smaller, such that the stack
> overflow does not occur where it would have in an unoptimized program.

That's fine. Basically, the abstract machine can be specified to
*non-deterministically* trigger a stack overflow any time the stack grows. So
essentially the running program has to be prepared that the stack might overflow
any time, but at the same time cannot rely on *when* it overflows. This is a
standard "trick" to formally handle resource exhaustion without having to
specify exactly how much of that resource is available.

This gives LLVM the freedom to grow or shrink stack frames. But this dos *not*
mean that stack overflows are UB!

> Also, we optimize the function
> ```
>  void overflow() {
>   overflow();
> }
> ```
>  to
> ```
> ; Function Attrs: nounwind readnone sspstrong uwtable
> define dso_local void @"?overflow@@YAXXZ"() local_unnamed_addr #0 {
> entry:
>   ret void
> }
> ```

This looks like an instance of the C++ forward progress assumption?
(C AFAIK only has that assumption for [some] loops, not recursive functions, so
arguably this is a miscompilation for C.)

Kind regards,
Ralf