JIT: Recursive calls elimination

[hez2010]

Description

I'm implementing Peano's natural number with Algebra Data Type in C#: https://gist.github.com/hez2010/39af351442c1b71a46e194bca72abfde

However, due to JIT cannot eliminate recursive calls, I got stackoverflow exception during runtime if the number is large enough.

To reproduce, execute c * c * c with above code.

This doesn't happen to Haskell (using ghc 9), so I think JIT should also be able to transform those calls to jmps for deep recursive calls.

Configuration

.NET 6 Preview 7

category:cq
theme:basic-cq

[jakobbotsch]

The runtime guarantees tailcall optimization only for calls that are tail. prefixed and are in tail position. Sometimes the x64 and ARM64 compilers will also opportunistically perform tailcalls when it does not take special effort to do so, even without any tail. prefix (which the C# compiler never emits). However, in your example I see no multiplication in tail position, so there is no tailcall optimization the compiler can do.

This doesn't happen to Haskell (using ghc 9), so I think JIT should also be able to transform those calls to jmps for deep recursive calls.

My guess is that ghc does not do tailcall elimination in this situation either, but rather just uses a larger stack size than .NET. Can you try passing -S to ghc and checking the generated code?

[hez2010]

ghc generated code: https://godbolt.org/z/Y9bPKeYTd

It compiles recursive function calls to jmp even for non tail calls (see code for mult around line 590)

[jakobbotsch]

If I modify your program so that it is infinite:

-    mult (S n) m = m `add` (n `mult` m)
+    mult (S n) m = m `add` (S n `mult` m)

Then I see steadily growing memory usage until it segfaults after using all my memory. I see the same behavior with a more simple:

foo 0 = 0
foo x = 1 + foo x

I don't know how ghc works internally, but it looks like it is allocating a continuation from memory pointed to by rbp:

        movq $.Lc2Ct_info,-16(%rbp)
        movq %r14,%rbx
        movq %rsi,-8(%rbp)
        addq $-16,%rbp

[hez2010]

it looks like it is allocating a continuation from memory pointed to by rbp

I think so.

Can this optimization also be applied to RyuJIT so that users no longer need to face stack overflow due to recursive calls (even they're not tail calls)? This often happens in real scenario, for example, implementing a deep search algorithm for image processing.

[jakobbotsch]

On Linux you can set the stack size to unlimited with ulimit -s unlimited. On Windows, you can change it with editbin or similar. I don't think this is something we would do inside the runtime by default, for most users exhausting the available stack is probably an indication of a bug.

There is also a Roslyn feature request to specify default stack size: dotnet/roslyn#22825

[hez2010]

Maybe a [MethodImpl(MethodImplOptions.DeepRecursion)] can be provided to achieve this? It's similar to AggressiveInlining.

[MichalStrehovsky]

Stack needs to be a region of contiguous memory. With enough threads, each having their own stack, we'll very quickly run out of address space on 32bit systems. 64bit systems have a bit more leeway, but the stack can't be set too big either.

[AndyAyersMS]

I'm not sure there is much else the jit can do here. There are some tricks one can play to turn recursion into tail recursion but they are likely well beyond what we'd be able to do in the jit as they require modifying method signatures.

Marking as future since I need to apply some milestone to make it clear this is not a 6.0 issue.