What is clang trying to do optimizing this simple recursive algorithm?
Upon writing an answer to this question: Using variable vs. using number I ran clang x86 9.0.0/trunk with -O3 to see if it could do tail-call optimization of this simple code:
int faculty1 (const unsigned int n) {
return n == 1 ? n : n * faculty1(n - 1);
}
Not only does clang fail that, it goes completely bananas and gives me this:
.LCPI0_0:
.long 0 # 0x0
.long 4294967295 # 0xffffffff
.long 4294967294 # 0xfffffffe
.long 4294967293 # 0xfffffffd
.LCPI0_1:
.long 1 # 0x1
.long 1 # 0x1
.long 1 # 0x1
.long 1 # 0x1
.LCPI0_2:
.long 4294967292 # 0xfffffffc
.long 4294967292 # 0xfffffffc
.long 4294967292 # 0xfffffffc
.long 4294967292 # 0xfffffffc
.LCPI0_3:
.long 4294967288 # 0xfffffff8
.long 4294967288 # 0xfffffff8
.long 4294967288 # 0xfffffff8
.long 4294967288 # 0xfffffff8
.LCPI0_4:
.long 4294967284 # 0xfffffff4
.long 4294967284 # 0xfffffff4
.long 4294967284 # 0xfffffff4
.long 4294967284 # 0xfffffff4
.LCPI0_5:
.long 4294967280 # 0xfffffff0
.long 4294967280 # 0xfffffff0
.long 4294967280 # 0xfffffff0
.long 4294967280 # 0xfffffff0
.LCPI0_6:
.long 4294967276 # 0xffffffec
.long 4294967276 # 0xffffffec
.long 4294967276 # 0xffffffec
.long 4294967276 # 0xffffffec
.LCPI0_7:
.long 4294967272 # 0xffffffe8
.long 4294967272 # 0xffffffe8
.long 4294967272 # 0xffffffe8
.long 4294967272 # 0xffffffe8
.LCPI0_8:
.long 4294967268 # 0xffffffe4
.long 4294967268 # 0xffffffe4
.long 4294967268 # 0xffffffe4
.long 4294967268 # 0xffffffe4
.LCPI0_9:
.long 4294967264 # 0xffffffe0
.long 4294967264 # 0xffffffe0
.long 4294967264 # 0xffffffe0
.long 4294967264 # 0xffffffe0
faculty1: # @faculty1
mov eax, 1
cmp edi, 1
je .LBB0_12
lea ecx, [rdi - 1]
mov eax, 1
cmp ecx, 8
jb .LBB0_11
mov r8d, ecx
and r8d, -8
movd xmm0, edi
pshufd xmm6, xmm0, 0 # xmm6 = xmm0[0,0,0,0]
paddd xmm6, xmmword ptr [rip + .LCPI0_0]
lea edx, [r8 - 8]
mov esi, edx
shr esi, 3
add esi, 1
mov eax, esi
and eax, 3
cmp edx, 24
jae .LBB0_4
movdqa xmm1, xmmword ptr [rip + .LCPI0_1] # xmm1 = [1,1,1,1]
movdqa xmm4, xmm1
jmp .LBB0_6
.LBB0_4:
and esi, -4
neg esi
movdqa xmm1, xmmword ptr [rip + .LCPI0_1] # xmm1 = [1,1,1,1]
movdqa xmm9, xmmword ptr [rip + .LCPI0_3] # xmm9 = [4294967288,4294967288,4294967288,4294967288]
movdqa xmm10, xmmword ptr [rip + .LCPI0_4] # xmm10 = [4294967284,4294967284,4294967284,4294967284]
movdqa xmm11, xmmword ptr [rip + .LCPI0_5] # xmm11 = [4294967280,4294967280,4294967280,4294967280]
movdqa xmm12, xmmword ptr [rip + .LCPI0_6] # xmm12 = [4294967276,4294967276,4294967276,4294967276]
movdqa xmm13, xmmword ptr [rip + .LCPI0_7] # xmm13 = [4294967272,4294967272,4294967272,4294967272]
movdqa xmm14, xmmword ptr [rip + .LCPI0_8] # xmm14 = [4294967268,4294967268,4294967268,4294967268]
movdqa xmm15, xmmword ptr [rip + .LCPI0_9] # xmm15 = [4294967264,4294967264,4294967264,4294967264]
movdqa xmm4, xmm1
.LBB0_5: # =>This Inner Loop Header: Depth=1
movdqa xmm0, xmm6
paddd xmm0, xmmword ptr [rip + .LCPI0_2]
pshufd xmm5, xmm1, 245 # xmm5 = xmm1[1,1,3,3]
pshufd xmm7, xmm6, 245 # xmm7 = xmm6[1,1,3,3]
pmuludq xmm7, xmm5
pmuludq xmm1, xmm6
pshufd xmm5, xmm4, 245 # xmm5 = xmm4[1,1,3,3]
pshufd xmm2, xmm0, 245 # xmm2 = xmm0[1,1,3,3]
pmuludq xmm2, xmm5
pmuludq xmm0, xmm4
movdqa xmm4, xmm6
paddd xmm4, xmm9
movdqa xmm5, xmm6
paddd xmm5, xmm10
pmuludq xmm1, xmm4
pshufd xmm4, xmm4, 245 # xmm4 = xmm4[1,1,3,3]
pmuludq xmm4, xmm7
pmuludq xmm0, xmm5
pshufd xmm5, xmm5, 245 # xmm5 = xmm5[1,1,3,3]
pmuludq xmm5, xmm2
movdqa xmm2, xmm6
paddd xmm2, xmm11
movdqa xmm7, xmm6
paddd xmm7, xmm12
pshufd xmm3, xmm2, 245 # xmm3 = xmm2[1,1,3,3]
pmuludq xmm3, xmm4
pmuludq xmm2, xmm1
pshufd xmm8, xmm7, 245 # xmm8 = xmm7[1,1,3,3]
pmuludq xmm8, xmm5
pmuludq xmm7, xmm0
movdqa xmm0, xmm6
paddd xmm0, xmm13
movdqa xmm5, xmm6
paddd xmm5, xmm14
pmuludq xmm2, xmm0
pshufd xmm1, xmm2, 232 # xmm1 = xmm2[0,2,2,3]
pshufd xmm0, xmm0, 245 # xmm0 = xmm0[1,1,3,3]
pmuludq xmm0, xmm3
pshufd xmm0, xmm0, 232 # xmm0 = xmm0[0,2,2,3]
punpckldq xmm1, xmm0 # xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
pmuludq xmm7, xmm5
pshufd xmm4, xmm7, 232 # xmm4 = xmm7[0,2,2,3]
pshufd xmm0, xmm5, 245 # xmm0 = xmm5[1,1,3,3]
pmuludq xmm0, xmm8
pshufd xmm0, xmm0, 232 # xmm0 = xmm0[0,2,2,3]
punpckldq xmm4, xmm0 # xmm4 = xmm4[0],xmm0[0],xmm4[1],xmm0[1]
paddd xmm6, xmm15
add esi, 4
jne .LBB0_5
.LBB0_6:
movdqa xmm5, xmm1
movdqa xmm0, xmm4
test eax, eax
je .LBB0_9
neg eax
movdqa xmm2, xmmword ptr [rip + .LCPI0_2] # xmm2 = [4294967292,4294967292,4294967292,4294967292]
movdqa xmm3, xmmword ptr [rip + .LCPI0_3] # xmm3 = [4294967288,4294967288,4294967288,4294967288]
.LBB0_8: # =>This Inner Loop Header: Depth=1
movdqa xmm0, xmm6
paddd xmm0, xmm2
movdqa xmm5, xmm6
pmuludq xmm5, xmm1
pshufd xmm5, xmm5, 232 # xmm5 = xmm5[0,2,2,3]
pshufd xmm1, xmm1, 245 # xmm1 = xmm1[1,1,3,3]
pshufd xmm7, xmm6, 245 # xmm7 = xmm6[1,1,3,3]
pmuludq xmm7, xmm1
pshufd xmm1, xmm7, 232 # xmm1 = xmm7[0,2,2,3]
punpckldq xmm5, xmm1 # xmm5 = xmm5[0],xmm1[0],xmm5[1],xmm1[1]
pshufd xmm1, xmm0, 245 # xmm1 = xmm0[1,1,3,3]
pmuludq xmm0, xmm4
pshufd xmm0, xmm0, 232 # xmm0 = xmm0[0,2,2,3]
pshufd xmm4, xmm4, 245 # xmm4 = xmm4[1,1,3,3]
pmuludq xmm4, xmm1
pshufd xmm1, xmm4, 232 # xmm1 = xmm4[0,2,2,3]
punpckldq xmm0, xmm1 # xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
paddd xmm6, xmm3
movdqa xmm1, xmm5
movdqa xmm4, xmm0
inc eax
jne .LBB0_8
.LBB0_9:
pshufd xmm1, xmm5, 245 # xmm1 = xmm5[1,1,3,3]
pshufd xmm2, xmm0, 245 # xmm2 = xmm0[1,1,3,3]
pmuludq xmm2, xmm1
pmuludq xmm0, xmm5
pshufd xmm1, xmm0, 78 # xmm1 = xmm0[2,3,0,1]
pmuludq xmm1, xmm0
pshufd xmm0, xmm2, 162 # xmm0 = xmm2[2,0,2,2]
pmuludq xmm0, xmm2
pmuludq xmm0, xmm1
movd eax, xmm0
cmp ecx, r8d
je .LBB0_12
sub edi, r8d
.LBB0_11: # =>This Inner Loop Header: Depth=1
imul eax, edi
add edi, -1
cmp edi, 1
jne .LBB0_11
.LBB0_12:
ret
What on earth is happening here!? Is the code containing some UB I fail to spot? Underflow/overflow shouldn't happen as far as I can tell and changing return type to unsigned int doesn't change anything.
Is this a bug at the Golbolt site or in clang? gcc and icc produce sensible code for the same snippet. For example gcc x86 -O3:
faculty1:
mov eax, 1
cmp edi, 1
je .L4
.L3:
mov edx, edi
sub edi, 1
imul eax, edx
cmp edi, 1
jne .L3
ret
.L4:
ret
(It managed to unroll the recursion)
Lundin1 Answer
I have Clang 7 installed, and it does the same thing, which means that it's not a compiler bug.
As noted in a comment, this recursion is being converted into a loop which is being vectorized.
The multiplication between the signed result and the unsigned operand promote the result to unsigned int, which is then converted back to int in an implementation-defined manner. That means that Clang can't/won't use integer overflow as a way to optimize.
This test program:
#include <stdio.h>
int faculty1 (const unsigned int n) {
return n == 1 ? n : n * faculty1(n - 1);
}
int main(void)
{
for(int i = 0; i < 65536; i++)
{
printf("%d: %d\n", i, faculty1(i));
}
}
takes around 3.8 seconds to run with Clang 7 -O2, and 8.6 seconds to run with GCC 8.3.0 -O2. So yes, Clang's version is faster. I think it's a little overkill, but it works and is standards-compliant.
S.S. AnneUser contributions licensed under CC BY-SA 3.0