What is clang trying to do optimizing this simple recursive algorithm?

6

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:

godbolt

.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)

c
assembly
x86
clang
asked on Stack Overflow Mar 20, 2020 by Lundin • edited Mar 20, 2020 by Lundin

1 Answer

4

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.

answered on Stack Overflow Mar 20, 2020 by S.S. Anne • edited Mar 20, 2020 by S.S. Anne

User contributions licensed under CC BY-SA 3.0