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

[Michael Kruse via llvm-dev]

During the review of https://reviews.llvm.org/D59978 we got to the
question whether we can optimize based on the assumption that stack
overflow is undefined behavior. While I think it is according to the
C++ standard, Windows Structured Exception Handling and signal
handlers might allow programs to recover/exit gracefully.

Concretely, the patch D59978 wants add the noreturn attribute to
functions that recurse infinitly. Also, a function that
unconditionally calls a function with a noreturn attribute can be
deduced to be noreturn.

Consider the following program:
```
#include <cstdlib>
#include <cstdio>

void overflow(); // Secret function that triggers a stack overflow

int catchoverflow() {
  __try  {
    overflow();
    printf("Exception NOT caught\n");
    return 0;
  } __except(true) {
    printf("Exception caught\n");
    return 1;
  }
  return 2;
}

int main() {
  auto result = catchoverflow();
  printf("Done execution result=%i\n", result);
  return EXIT_SUCCESS;
}
```
An implementation of the overflow function could be:
```
 void overflow() {
  overflow();
  printf("x");
}
```

Compiled with msvc or clang-cl, this prints:
```
Exception caught
Done execution result=1
```
That is, even though overflow() does not return normally, catchoverflow() does.

The documentation for the "noreturn" attribute currently says
(https://llvm.org/docs/LangRef.html#function-attributes):
> This function attribute indicates that the function never returns normally. This produces undefined behavior at runtime if the function ever does dynamically return.

The motivation of marking catchoverflow() is that a program cannot
reasonably expect to continue normal execution after a stack overflow
happened, and shouldn't inhibit optimizations.

In this RFC, I would like to clarify the following questions:
1. Does the "noreturn" attribute imply that the function is not
returning via the unwind edge of an invoke instruction?
2. Can/should overflow() be marked noreturn?
3. Can/should catchoverflow() be marked noreturn?
4a. More generally, for the purpose of optimizations, can we assume
that functions do not overflow? That is, is stack overflow is
undefined behavior?
4b. If not undefined behavior, can we assume that if a stack overflow
occurs, the program will be terminated? This would e.g. stop
side-effect code to be moved before the overflowing call; otherwise it
would be executed on overflow termination. How would we check whether
a function can overflow the stack?

Whatever the answers to these questions are, I think we should clarify
what the function attributes noreturn, nounwind, willreturn mean. The
most explicit way would be listing all the possible outcomes of
calling a function and exclude possibilities per attribute.

1. Call returns to next instruction / invoke branches to "to" block.
2a. Call throws synchronous exception and stack is unwound to parent caller
2b. Invoke throws synchronous exception and branches to "unwind to" block
3a. Call throws asynchronous exception and stack is unwound to parent caller
3b. Invoke throws asynchronous exception and branches to "unwind to" block
4a. Call/invoke triggers thread/program termination and dtors/atexit
funcs are called (e.g. by calling exit())
4b. Call/invoke triggers thread/program immediate termination (e.g. by
calling abort())
5. Signal handler is executed and which kills the program
6. Immediate thread/program termination by external cause (e.g. by ,
`TerminateThread`, `kill -9`, kernel panic, power switch)


Michael