理解clang循环优化

Question

理解clang循环优化

c++optimizationcompiler-optimizationllvm-clang

3

我已经得到这段代码。

#include  <cstdlib>
#include <time.h> 

int sum () {
  srand (time(NULL));
  unsigned long extra = rand() % 10; 
  int sum = 0;
  // #pragma nounroll. <<<< This makes no difference
  for (int i = 0; i < 16 + extra; ++i) {
    sum += i;
  }
    return sum;
}

使用-O3, clang进行了以下优化，让我大开眼界。（请注意，没有任何分支）

我真的不明白这种优化的正确性如何被证明。特别是，似乎使用两个神奇数字（顺便说一下，它们在编译之间不会改变），感到神秘。此外，我猜你称它们为“随机”，但并不像rand()的精神那样随机，对吗？

sum():                                # @sum()
        push    rax
        xor     edi, edi
        call    time
        mov     edi, eax
        call    srand
        call    rand
        cdqe
        imul    rcx, rax, 1717986919. # <<<< magic number
        mov     rdx, rcx
        shr     rdx, 63
        sar     rcx, 34
        add     ecx, edx
        add     ecx, ecx
        lea     ecx, [rcx + 4*rcx]
        mov     edx, eax
        sub     edx, ecx
        neg     ecx
        add     eax, ecx
        add     eax, 16
        lea     rcx, [rax - 1]
        movabs  rsi, 8589934590 # <<< magic number
        add     rsi, rax
        imul    rsi, rcx
        shr     rsi
        lea     eax, [rsi + rdx]
        add     eax, 15
        pop     rcx
        ret

为了后世留存，gcc生成了以下内容：

sum():
        sub     rsp, 8
        xor     edi, edi
        call    time
        mov     rdi, rax
        call    srand
        call    rand
        mov     esi, 1
        movsx   rdx, eax
        mov     ecx, eax
        imul    rdx, rdx, 1717986919
        sar     ecx, 31
        sar     rdx, 34
        sub     edx, ecx
        lea     ecx, [rdx+rdx*4]
        add     ecx, ecx
        sub     eax, ecx
        mov     edx, eax
        add     eax, 16
        movsx   rcx, eax
        cmp     edx, -16
        cmovne  rsi, rcx
        cmp     eax, 18
        jbe     .L6
        mov     rdx, rsi
        movdqa  xmm1, XMMWORD PTR .LC0[rip]
        pxor    xmm0, xmm0
        xor     eax, eax
        movdqa  xmm3, XMMWORD PTR .LC1[rip]
        shr     rdx, 2
.L3:
        movdqa  xmm2, xmm1
        add     eax, 1
        paddd   xmm1, xmm3
        paddd   xmm0, xmm2
        cmp     eax, edx
        jne     .L3
        movdqa  xmm1, xmm0
        mov     rdi, rsi
        psrldq  xmm1, 8
        and     rdi, -4
        paddd   xmm0, xmm1
        movsx   rdx, edi
        movdqa  xmm1, xmm0
        psrldq  xmm1, 4
        paddd   xmm0, xmm1
        movd    eax, xmm0
        cmp     rsi, rdi
        je      .L1
.L5:
        add     eax, edx
        add     rdx, 1
        cmp     rcx, rdx
        ja      .L5
.L1:
        add     rsp, 8
        ret
.L6:
        xor     edx, edx
        xor     eax, eax
        jmp     .L5
.LC0:
        .long   0
        .long   1
        .long   2
        .long   3
.LC1:
        .long   4
        .long   4
        .long   4
        .long   4

- Curious Learner

3

可能是用 res = (16+extra-1) * (16+extra-2) / 2 替换了循环。 - IlCapitano

@MarcoBonelli 这不会改变结果。有趣的是，针对ARM的gcc也生成类似的魔数（在十六进制中看起来不那么神奇）。 - Eugene Sh.

IlCapitano @ 你能详细解释一下为什么吗？ - Curious Learner

@CuriousLearner 等差数列的和。 - Eugene Sh.

1

@CuriousLearner，有一个计算从0到n的整数和的公式，即n * (n-1) / 2。Clang可能会看到循环正好执行此操作，因此用公式替换了它。这些神奇的数字可能与模运算有关。如果您查看llvm IR输出（使用-emit-llvm），则没有神奇的数字。 - IlCapitano

显示剩余8条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Antti Haapala -- Слава Україні · Accepted Answer

代码确实调用了rand，这已经足够了。返回值将被保存在rax寄存器中。如果你将2³²除以1717986919，得到的结果是2.499999999126885，非常接近于10/4...使用常数，配合移位操作，可以计算出% 10而无需使用昂贵的idiv指令。

之后，结果就是1 + 2 + 3 ... + n的等差数列的前n项和，即n(n + 1) / 2。第二个神奇数字与此计算有关。