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

[Ralf Jung via llvm-dev]

Hi,

> I think this is more target-platform specific than input-language. My
> motivation was to preserve Windows SEH behavior where one can
> (reliably?) catch stack overflows using a __try __except handler. I
> think its ABI even specifies that there must be stack probing. The
> original version of https://reviews.llvm.org/D59978 would not consider
> that such an asynchronous exception could be a cause for jumping to
> the unwind handler with the argument that "LLVM does not model
> asynchronous exceptions" (cite from
> https://clang.llvm.org/docs/MSVCCompatibility.html) anyway.
> 
> As Nevin pointed out, other platforms not require stack probing, do
> not have Structured Exception Handling, but may call the signal
> handler (which we also do not model).
> 
> So I wrote this RFC to clarify which guarantees we are giving in case
> of stack overflow, especially in situations where the compilation
> target does not give such guarantees.

My point is that right now, it is possible to reliably catch Stack Overflows
even on non-Windows systems, e.g. by setting up the guard page correctly.  Doing
this properly surely requires target-specific actions, which will most likely
not be modeled by LLVM.  Declaring stack overflow as UB would remove this
ability, which would be a serious problem for languages that *have to* reliably
catch Stack Overflows.

If Rust fails to catch a Stack Overflow, that's a serious soundness bug in the
compiler.  It would be as bad as Rust failing to catch a dereferenced NULL
pointer.  The difference is that Rust's type system can rule out the NULL
pointer case statically (so making them UB in LLVM is fine), while ruling out
stack overflows is done dynamically (and it is fundamentally impossible to
reliably do dynamic UB checks *after* passing through an IR that exploited this UB).

>> 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!
> 
> What is it then? What reference says it is/is not UB?

I don't know what C/C++ says, and AFAIK LLVM doesn't document anything about
this.  All I am saying is that, if LLVM is to be used as the backend language in
a compiler for a safe language (one that protects its users for UB), it is a
*hard requirement* that LLVM does not make Stack Overflows UB.

Then I proposed a scheme that permits growing and shrinking stack frames in a
semantics that does not make Stack Overflow UB.  This was in response to a
concern you raised about growing or shrinking stack frames being a problem if
LLVM declared stack overflow as not being 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.)
> 
> If stack overflow is UB, then this is a valid optimization.
> If the compiler is allowed to optimize the stack frame size to zero
> (=> tail call), we would effectively get an infinite loop, also a
> valid outcome of UB.
> 
> If it is not UB, what is the defined behaviour?

The defined behavior is to loop forever, or abort at some point due to a stack
overflow.  So, there are two possible defined behaviors.  The compiler has to
make sure that any time the program runs, it exhibits one of these two behaviors.

Even programs with defined behavior can have different outcomes when run /
compiled multiple times.  That's just a normal consequence of non-determinism.
This is similar to e.g. a program that starts two threads and has both of them
print to stdout: sometimes one thread will come first, sometimes another thread
will come first.  The compiler is allowed to optimize this program in a way that
the order becomes fixed (e.g. by inlining both of them into the main thread).
The compiler can also keep the non-determinism so that it gets resolved at run-time.

> If this is an instance of the forward-progress assumption, we should
> maybe discuss it here:
> https://reviews.llvm.org/D65718
> 
> Should we have a similar document clarifying the behavior of stack overflows?

That seems like a good idea.

Kind regards,
Ralf