Factorial function gets over-vectorized and slower with -O2

[llvmbot]

Bugzilla Link	36918
Version	5.0
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@davidbolvansky,@DougGregor,@efriedma-quic,@hfinkel,@laytonio,@RKSimon,@jeremy-rifkin

Extended Description

Consider a simple factorial function with tail recursion:

int factorial(int n)
{
    if (n <= 0) return 1;
    return n * factorial(n - 1);
}

Compiling with -O2 on clang++ produces a lot of code compared to -O1, -Os, or any of these flags on gcc. This holds for at least versions 3.8 and onwards.

A comparison can be found here: https://godbolt.org/g/fbztqo

Basic performance tests on Ubuntu 16.04 (core i7-6700 CPU) also shows the non-super-vectorized version is considerably slower, at least for all values that don't lead to overflow. The clang binary is also slightly larger.

I would expect clang to not attempt this "optimization".

Note: Using -Os gives a result almost identical to gcc with -O2.

[efriedma-quic]

This looks like a vectorizable loop... but I guess there are two problems:

1. SSE without SSE4.1 doesn't have pmulld, which makes vectorizing this much less beneficial; the cost modeling might be wrong.

2. factorial() overflows for n > 13, so specializing the loop for the case where n > 24 is a bit dubious.

[davidbolvansky]

LLVM cannot handle a bit "harder" example:

unsigned almost_factorial(unsigned n)
{
if (n <= 0) return 1;
return 2 * almost_factorial(n - 1);
}

Produces:
almost_factorial(unsigned int): # @​almost_factorial(unsigned int)
test edi, edi
je .LBB0_2
push rax
add edi, -1
call almost_factorial(unsigned int)
add eax, eax
pop rcx
ret
.LBB0_2:
mov eax, 1
ret

GCC or ICC can eliminate tail recursion:
mov eax, 1
.L3:
test edi, edi
je .L4
dec edi
add eax, eax
jmp .L3
.L4:
ret

[davidbolvansky]

Also GCC and ICC are able to eliminate TR for this case:

unsigned almost_factorial(int A[10], unsigned n)
{
if (n <= 0) return A[0];
return A[n] + almost_factorial(A, n - 1);
}

https://godbolt.org/z/5UVv6X

[Laytonio]

This seems to be a conflation of two issues at this point. The original bug is related to the decision as to whether to vectorize the loop created after the tail call has been eliminated. The other two examples posted are missed elimination opportunities.

As for the two missed eliminations; The first is due to the multiplication getting converted to a shift. We only support operations that are associative and commutative when eliminating calls like this, so the shift is skipped. We should probably just convert the shift back to a multiply during the elimination. The second is due to some limitations in the current implementations handling of memory loads (array indexes) in the base case. I am actively working to remove that limitation and should have a patch soon.

[Laytonio]

This patch https://reviews.llvm.org/D80844, fixes the below and adds it as a test case.

unsigned almost_factorial(int A[10], unsigned n)
{
if (n <= 0) return A[0];
return A[n] + almost_factorial(A, n - 1);
}