test_compiler_recursion_limit fails on wasm32-wasi

[iritkatriel]

The problem showed up after we merged #95107
and a couple of test were disabled for WASI in #95296

With the patch in iritkatriel@4ce85e8 we get:

Here is a full WASM stack trace generated with

WASMTIME_BACKTRACE_DETAILS=1 \
  wasmtime run --env PYTHONPATH=/builddir/wasi/$(cat pybuilddir.txt) --mapdir /::../../ -- \
  python.wasm -m test -v test_compile -m test_compiler_recursion_limit

wasi_stacktrace.txt

test_compiler_recursion_limit (test.test_compile.TestSpecifics.test_compiler_recursion_limit) ... Error: failed to run main module `python.wasm`

Caused by:
    0: failed to invoke command default
    1: wasm trap: out of bounds memory access
       wasm backtrace:
           0: 0x15d8eb - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5868:37
           1: 0x15ee62 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4846:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5802:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5870:15
           2: 0x15ee62 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4846:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5802:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5870:15
           3: 0x15ee62 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4846:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5802:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5870:15
           4: 0x15ee62 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4846:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5802:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5870:15
           5: 0x15ee62 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4846:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5802:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5870:15
           6: 0x15ee62 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4846:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5802:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5870:15

Originally posted by @tiran in #93678 (comment)

[tiran]

• wasmtime-cli 0.39.1
• WASI-SDK 16.0 with clang version 14.0.4

[tiran]

To reproduce a similar problem before #95107, add sys.setrecursionlimit(1700) at the beginning of test_compiler_recursion_limit. The default recursion limit on WASI is 600. It will result in a call stack exhausted trap with 3,609 calls instead of a out of bounds memory access trap after 991 calls.

test_compiler_recursion_limit (test.test_compile.TestSpecifics.test_compiler_recursion_limit) ... Error: failed to run main module `python.wasm`

Caused by:
    0: failed to invoke command default
    1: wasm trap: call stack exhausted
       wasm backtrace:
           0: <unknown>!validate_keywords
           1: 0x15c9e4 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4844:9
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5813:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5881:15
           2: 0x15cde6 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4857:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5813:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5881:15
           3: 0x15cde6 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4857:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5813:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5881:15
           4: 0x15cde6 - compiler_call
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:4857:5
                     - compiler_visit_expr1
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5813:16
                     - compiler_visit_expr
                           at /python-wasm/cpython/builddir/wasi/../../Python/compile.c:5881:15
...
         3602: 0x1b6c85 - pymain_run_module
                           at /python-wasm/cpython/builddir/wasi/../../Modules/main.c:300:14
         3603: 0x1b63f1 - pymain_run_python
                           at /python-wasm/cpython/builddir/wasi/../../Modules/main.c:604:21
                     - Py_RunMain
                           at /python-wasm/cpython/builddir/wasi/../../Modules/main.c:689:5
         3604: 0x1b70d7 - pymain_main
                           at /python-wasm/cpython/builddir/wasi/../../Modules/main.c:719:12
         3605: 0x1b7186 - Py_BytesMain
                           at /python-wasm/cpython/builddir/wasi/../../Modules/main.c:743:12
         3606: 0x4c85 - __main_argc_argv
                           at /python-wasm/cpython/builddir/wasi/../../Programs/python.c:15:12
         3607: 0x321d5b - <unknown>!__main_void
         3608: 0x4c69 - <unknown>!_start
         3609: 0x339092 - <unknown>!_start.command_export

[markshannon]

This reminds me of #30855 (comment)

Fiddling with the code to keep the stack use below some arbitrary limit imposed by the compiler and platform is not the way to fix this or other bugs of the sort.

The proper fix is use some sort of C stack check: #91079

For now, I would recommend reducing the recursion limit in the compiler.

TBH, we shouldn't care if some really weird code f()()()()()()()... fails in the compiler, as long as it fails gracefully.

The only thing we need to handle is long chains of if: .. elifs, which should be handled iteratively to avoid consuming excessive stack.

[markshannon]

Until we implement #91079 we should use the standard recursion limit counter in the compiler, otherwise we can crash on this code:

def f(n):
    if n: 
        f(n-1)
    else:
        compile_deeply_recursive_ast()
f(900)

As we consume most of the stack in f, then crash in the compiler.

[iritkatriel]

I’m not actually sure my PR added function calls that get repeated in a recursion. I don’t really know what I’m my PR would have caused this.

[markshannon]

It was probably passing locations by value, instead of by pointer, that increased the stack consumption.
But, as I've said, it could be any change that tips the stack use over the limit.

We need to reduce the recursion by using iterative approaches, not fiddle with the code.

[markshannon]

Converting recursion into iteration is a pain. So, I'd just reduce the depth for everything but if/elifs and handle those iteratively.

[markshannon]

@pablogsal might have thoughts on converting if/elifs into a list from a tree in the parser.

[iritkatriel]

I’m not sure the locations are passed down deep recursions though.

[markshannon]

Probably, not. But they still need stack space to be passed into the ADDOP...s

[tiran]

It is very well possible that your commit change some unrelated properties of the code that results in different optimizations.

I asked the wasmtime developers about stack limits in my ticket bytecodealliance/wasmtime#4214 .

Currently there is no way for a wasm module to determine its own stack limit or otherwise see how big stack frames are, so there's no way for the wasm module itself to detect what its recursion limit should be.

The stack limit also depends on the WASM runtime and possible other parameters. So far we have been testing with wasmtime only.