如何让 GCC 优化长 XOR 链

Question

我有一个像这样的循环：

uint32_t result = 0;

for ( int i = 0; i < CONSTANT; ++i )
{
    result ^= expr;
}
return result;

总的来说，GCC 使用这段代码做得很好。它完全展开循环并为 expr 生成最佳代码。但是，它执行 result XOR CONSTANT 次。它可能会累积部分结果并将它们分层异或。

我怀疑如果我用宏手动展开这个我可以手动完成（CONSTANT 并不大），但我想知道为什么它看不到这个，或者如果我由于一些神秘的 C++ 语言规则，正在做一些阻止它的事情。

Answer 1

在这里累积部分结果可能没有任何好处。如果您使用分而治之的策略（异或偶数使大小减半，然后重复，每次将操作数减半），您最终仍然会做 O(CONSTANT) 工作（一半的工作加上四分之一的工作加上八分之一的工作等等，最终执行 CONSTANT - 1 操作）。

在块中累积部分结果的行为相同。从根本上说，您必须进行 CONSTANT - 1 异或运算。由于这些是固定宽度的寄存器，而不是增长任意精度的整数，因此每个 XOR 的工作是相同的。除非并行化 expr 工作，否则您极不可能从更复杂的方法中获得任何收益。

Answer 2

对于您的循环，expr 不依赖于 i，在这种情况下 gcc 应该完全优化循环¹，或者在这种情况下 gcc 可以仍然优化它（因为循环边界是常数，整个循环可以是 pre-calculated）。

好像是fails in the latter case though, _unless you optimize for -march=haswell. That seems really weird, but I've seen exactly that kind of behavior before.

无论如何²，你提到expr编译成两条指令。为 xor、循环增量和测试指令添加 3 条指令，这个循环已经有 5 条指令，这甚至超过了 high-end x86 CPU 的报废率，因此没有任何好处在这里寻找额外的指令级并行性（除非你可能正在编译到宽度更高的非 x86 arch？）。

¹ ...而且它一般都会在 -O3 无论如何。

² 我们只需要猜测就可以了，因为你真的在严密保护expr的秘密。

如何让 GCC 优化长 XOR 链

How to get GCC to optimize long XOR chain

c++

gcc

compiler-optimization