Repository navigation
LLVM: recursive calls have overhead in JIT mode #16943
Description
A simple recursion (calculates factorial):
public static int Factorial(int number)
{
if (number == 1)
return 1;
return number * Factorial(number - 1);
}We emit the following LLVM IR:
; ModuleID = 'jit-module-Factorial'
source_filename = "jit-module-Factorial"
@tramp_141 = global i32 (i32)* inttoptr (i64 2147373336 to i32 (i32)*)
; Function Attrs: noinline uwtable
define monocc i32 @"Program:Factorial (int)"(i32 %arg_number) #0 {
BB0:
br label %BB3
BB3:
br label %BB2
BB2:
%0 = icmp ne i32 %arg_number, 1
br i1 %0, label %BB4, label %BB5
BB5:
br label %BB1
BB4:
%t26 = sub i32 %arg_number, 1
%1 = load i32 (i32)*, i32 (i32)** @tramp_141 ; we load itself here!
%2 = notail call monocc i32 %1(i32 %t26)
%t30 = mul i32 %arg_number, %2
br label %BB1
BB1:
%3 = phi i32 [ 1, %BB5 ], [ %t30, %BB4 ]
ret i32 %3
}
attributes #0 = { noinline uwtable }Instead of calling itself directly (call @"Program:Factorial (int)") we do an external call (load @tramp_141 global variable, do call)
However, this problem is JIT specific, when I compile the snippet with Mono-LLVM-AOT - it generates the expected direct call and works faster:
; Function Attrs: noinline nounwind readnone uwtable
define hidden monocc i32 @Program_Factorial_int(i32 %arg_number) #3 {
BB0:
%0 = icmp eq i32 %arg_number, 1
br i1 %0, label %BB1, label %BB4
BB4:
%t26 = add i32 %arg_number, -1
%1 = notail call monocc i32 @Program_Factorial_int(i32 %t26) ; calls itself as expected!
%t30 = mul i32 %1, %arg_number
br label %BB1
BB1:
%2 = phi i32 [ %t30, %BB4 ], [ 1, %BB0 ]
ret i32 %2
}By the way if I remove that notail in the AOT case - it will remove the recursion 🙂 but it's a different issue (cc @jaykrell)
So the LLVM JIT is slower, it explains why it's slow in the Fibonacci benchmark (slower than LLVM AOT).
Activity
[llvm] Handle recursive calls as a direct call.
vargaz commentedon Sep 19, 2019
Note that even with that PR, llvm will still generate an indirect call.
[llvm] Handle recursive calls as a direct call. (#16944)
Bump to mono/mono@18920a83 (#3753)
Bump to mono/mono@18920a83 (#3753)
[llvm] Handle recursive calls as a direct call. (mono/mono#16944)