Что Clang пытается сделать, оптимизируя этот простой рекурсивный алгоритм? - PullRequest
Новая
       3

Что Clang пытается сделать, оптимизируя этот простой рекурсивный алгоритм?

7 голосов
/ 20 марта 2020

После написания ответа на этот вопрос: Использование переменной против использования числа Я запустил clang x86 9.0.0 / trunk с -O3, чтобы посмотреть, сможет ли он выполнить оптимизацию хвостового вызова этого простого кода: 

int faculty1 (const unsigned int n) {
    return n == 1 ? n : n * faculty1(n - 1);
}

Мало того, что кланг терпит неудачу, он идет полностью бананом и дает мне это:

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

Что на земле здесь происходит? Код, содержащий некоторый UB, который я не могу обнаружить? Переполнение / переполнение не должно происходить, насколько я могу судить, и изменение типа возвращаемого значения на unsigned int ничего не меняет.

Это ошибка на сайте Golbolt или в clang? g cc и i cc создают разумный код для того же фрагмента. Например, g cc 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

(удалось развернуть рекурсию)

1 Ответ

4 голосов
/ 20 марта 2020

У меня установлен Clang 7, и он делает то же самое, что означает, что это не ошибка компилятора.

Как отмечено в комментарии, эта рекурсия преобразуется в al oop, который vectorized.

Умножение между подписанным результатом и беззнаковым операндом переводит результат в unsigned int, который затем преобразуется обратно в int способом, определяемым реализацией. Это означает, что Clang не может / не будет использовать целочисленное переполнение как способ оптимизации.

Эта тестовая программа: 

#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));
    }
}

занимает около 3,8 секунды для запуска с Clang 7 -O2 и 8,6 секунды для запуска с G CC 8.3.0 -O2. Так что да, версия Clang быстрее. Я думаю, что это немного излишнее, но оно работает и соответствует стандартам.

...