为什么GCC不能优化“x”中的逻辑/按位AND对

Question

以下是我声称执行完全相同操作的两个函数：

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

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

从逻辑上讲，它们做同样的事情，为了100%确定，我编写了一个测试，通过它们运行了所有40亿个可能的输入，并且它们匹配。（x

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

我用-O3在Mac OS上用clang 5.1测试了以上内容。使用< code>fast()花费了2.9秒，使用< code>slow()花费了3.8秒。如果我使用一个全零的向量，这两个函数的性能没有明显的差别。

其他编译器：

• 主线clang 3.7及更高版本甚至对进行优化




Answer 1

这就是你的代码在ARM中的样子，当输入它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 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

到底为什么它应该能够优化代码？您假设任何有效的转换都会完成。这根本不是优化器的工作方式。它们不是人工智能。它们只是通过参数化替换已知模式来工作。E、 g.“公共子表达式消除”扫描表达式中的公共子表达式，如果不改变副作用，则向前移动它们。

（顺便说一句，CSE表明优化器已经非常清楚在可能存在副作用的情况下允许什么代码移动。他们知道你必须小心

总之，你认为哪种模式适用于这里？