为什么GCC不能优化"x &&(x&4242)"到"x&4242"中的逻辑按位AND对？

Question

以下是我声称完成同样事情的两个功能:

bool fast(int x)
{
  return x & 4242;
}

bool slow(int x)
{
  return x && (x & 4242);
}

从逻辑上讲,他们做同样的事情,只是为了100%肯定我写了一个测试,通过他们两个运行所有40亿个可能的输入,并且他们匹配.但汇编代码是一个不同的故事:

fast:
    andl    $4242, %edi
    setne   %al
    ret

slow:
    xorl    %eax, %eax
    testl   %edi, %edi
    je      .L3
    andl    $4242, %edi
    setne   %al
.L3:
    rep
    ret

令我感到惊讶的是,GCC无法实现消除冗余测试的逻辑上的飞跃.我用-O2,-O3和-Os尝试了g ++ 4.4.3和4.7.2,所有这些都生成了相同的代码.该平台是Linux x86_64.

有人可以解释为什么GCC不够聪明,不能在两种情况下生成相同的代码吗？我还想知道其他编译器是否可以做得更好.

编辑以添加测试工具:

#include <cstdlib>
#include <vector>
using namespace std;

int main(int argc, char* argv[])
{
    // make vector filled with numbers starting from argv[1]
    int seed = atoi(argv[1]);
    vector<int> v(100000);
    for (int j = 0; j < 100000; ++j)
        v[j] = j + seed;

    // count how many times the function returns true
    int result = 0;
    for (int j = 0; j < 100000; ++j)
        for (int i : v)
            result += slow(i); // or fast(i), try both

    return result;
}

我在Mac OS上用-O3测试了上面的clang 5.1.使用时间为2.9秒,使用时间为fast()3.8秒slow().如果我改为使用全零的向量,则两个函数之间的性能没有显着差异.

Answer 1

究竟为什么要它能够对代码进行优化？您假设任何有效的转换都将完成.这根本不是优化者的工作方式.他们不是人工智能.他们只是通过参数化替换已知模式来工作.例如,"Common Subexpression Elimination"扫描表达式以查找常见的子表达式,如果不改变副作用,则向前移动它们.

(顺便说一句,CSE表明优化者已经非常清楚可能存在副作用的代码运动.他们知道你必须要小心&&.是否expr && expr可以进行CSE优化取决于副作用expr. )

总而言之:您认为哪种模式适用于此？

Answer 2

你是正确的,这在优化器中似乎是一个缺陷,可能是一个彻头彻尾的错误.

考虑:

bool slow(int x)
{
  return x && (x & 4242);
}

bool slow2(int x)
{
  return (x & 4242) && x;
}

GCC 4.8.1(-O3)发布的装配:

slow:
    xorl    %eax, %eax
    testl   %edi, %edi
    je      .L2
    andl    $4242, %edi
    setne   %al
.L2:
    rep ret

slow2:
    andl    $4242, %edi
    setne   %al
    ret

换句话说,slow2是错误的名字.

我只是偶尔向GCC提供补丁,所以我的观点是否有任何重要性值得商榷:-).但在我看来,GCC优化其中一个而不是另一个当然是奇怪的.我建议提交一份错误报告.

[更新]

令人惊讶的是,微小的变化似乎有很大的不同.例如:

bool slow3(int x)
{
  int y = x & 4242;
  return y && x;
}

...再次生成"慢"代码.我对这种行为没有假设.

您可以在此处在多个编译器上试验所有这些.

Answer 3

这就是你的代码在ARM中看起来如何slow在输入0时运行得更快.

fast(int):
    movw    r3, #4242
    and r3, r0, r3
    adds    r0, r3, #0
    movne   r0, #1
    bx  lr
slow(int):
    cmp r0, #0
    bxeq    lr
    movw    r3, #4242
    and r3, r0, r3
    adds    r0, r3, #0
    movne   r0, #1
    bx  lr

但是,无论如何,当你开始使用这些简单的函数时,GCC会非常好地进行优化.

bool foo() {
    return fast(4242) && slow(42);
}

变

foo():
    mov r0, #1
    bx  lr

我的观点是,有时这样的代码需要更多的上下文进一步优化,为什么优化器(改进器!)的实现者应该打扰？

另一个例子:

bool bar(int c) {
  if (fast(c))
    return slow(c);
}

变

bar(int):
    movw    r3, #4242
    and r3, r0, r3
    cmp r3, #0
    movne   r0, #1
    bxne    lr
    bx  lr

Answer 4

要执行此优化,需要研究两个不同情况的表达式:x == 0简化到false,并x != 0简化为x & 4242.然后足够聪明地看到第二个表达式的值也会产生正确的值,即使对于x == 0.

让我们假设编译器执行案例研究并找到简化.

如果x != 0,表达式简化为x & 4242.

如果x == 0,表达式简化为false.

简化后,我们得到两个完全不相关的表达式.为了协调它们,编译器应该提出不自然的问题:

如果x != 0,可以false代替使用x & 4242吗？[没有]

如果x == 0,可以x & 4242代替使用false吗？[是]

Answer 5

我工作的最后一个编译器没有进行这些类型的优化.编写优化器以利用与组合二进制和逻辑运算符相关的优化不会加速应用程序.这样做的主要原因是人们不经常使用这样的二元运算符.许多人对二元运算符感到不舒服,那些通常不会编写需要优化的无用操作的人.

如果我去写作的麻烦

return (x & 4242)

我理解这意味着为什么我会为额外的步骤而烦恼.出于同样的原因,我不会写这个次优的代码

if (x==0) return false;
if (x==1) return true;
if (x==0xFFFEFD6) return false;
if (x==4242) return true;
return (x & 4242)

可以更好地利用编译器开发人员的时间,而不是优化那些没有区别的东西.在编译器优化中有很多更大的鱼可以炒.

Answer 6

值得注意的是,这种优化在所有机器上都无效.特别是如果你在使用负数的补码表示的机器上运行,那么:

-0 & 4242 == true
-0 && ( -0 & 4242 ) == false

海湾合作委员会从未支持此类陈述,但C标准允许这些陈述.