ac/c ++编译器是否将两次幂值的常量除法优化为移位？

Question

问题说明了一切.有谁知道以下......

size_t div(size_t value) {
    const size_t x = 64;
    return value / x;
}

...优化成？

size_t div(size_t value) {
    return value >> 6;
}

编译器会这样做吗？(我的兴趣在于GCC).是否有这样的情况,有些情况不是吗？

我真的很想知道,因为每当我写一个可以像这样优化的师时,我会花费一些心理能量,想知道一秒钟的宝贵事迹是否会浪费在一个转变就足够的分裂上.

Answer 1

即使g++ -O0(是的,-O0!),这种情况也会发生.您的函数编译为:

_Z3divm:
.LFB952:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movq    %rdi, -24(%rbp)
        movq    $64, -8(%rbp)
        movq    -24(%rbp), %rax
        shrq    $6, %rax
        leave
        ret

注意shrq $6,这是一个右移6个地方.

随着-O1,不必要的垃圾被删除:

_Z3divm:
.LFB1023:
        movq    %rdi, %rax
        shrq    $6, %rax
        ret

关于g ++ 4.3.3,x64的结果.

Answer 2

大多数编译器甚至比通过将2的幂除以移位更进一步 - 它们通常将整数除以常数转换为一系列乘法,移位和加法指令以获得结果而不是使用CPU的内置除法指令(如果有的话).

例如,MSVC将除以71转换为以下值:

// volatile int y = x / 71;

8b 0c 24        mov ecx, DWORD PTR _x$[esp+8] ; load x into ecx

b8 49 b4 c2 e6  mov eax, -423447479 ; magic happens starting here...
f7 e9           imul ecx            ; edx:eax = x * 0xe6c2b449

03 d1           add edx, ecx        ; edx = x + edx

c1 fa 06        sar edx, 6          ; edx >>= 6 (with sign fill)

8b c2           mov eax, edx        ; eax = edx
c1 e8 1f        shr eax, 31         ; eax >>= 31 (no sign fill)
03 c2           add eax, edx        ; eax += edx

89 04 24        mov DWORD PTR _y$[esp+8], eax

所以,你得到一个除以71的乘法,一个班次和几个加法.

有关正在发生的事情的详细信息,请参阅Henry Warren的"Hacker's Delight"一书或随附的网页:

• http://www.hackersdelight.org/

这里有一个在线添加的章节,它提供了一些关于常数除法的附加信息,使用带有幻数的乘法/移位/加法,以及一个带有一个小程序的页面,它将计算你需要的幻数.

这本书的配套网站非常值得一读(正如本书一样) - 特别是如果你对比特级微优化感兴趣的话.

我刚刚发现的另一篇文章讨论了这种优化:http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx

Answer 3

只有当它能够确定论证是积极的时候.对于你的例子就是这种情况,但是自从C99为整数除法指定了向零舍入的语义之后,将两个幂的除法进行优化变得更加困难,因为它们为负参数提供了不同的结果.

在反应以下迈克尔的评论,在这里是一种方式划分r=x/p;的x通过两种已知功率p的确可以被编译器编译:

if (x<0)
  x += p-1;
r = x >> (log2 p);

由于OP在询问他是否应该考虑这些事情,一个可能的答案是"只有你知道股息的符号比编译器更好,或者知道如果结果向0或-∞舍入则无关紧要".