c - GCC 为数组元素的重复 XOR 生成冗余代码

Question

GCC 让我很难为以下源代码生成最佳汇编:

memset(X, 0, 16);
for (int i= 0; i < 16; ++i) {
    X[0] ^= table[i][Y[i]].asQWord;
}

X 是一个 uint64_t[2] 数组，并且
Y 是一个 unsigned char[16] 数组，并且
table 是 union qword_t 的二维数组:

union qword_t {
    uint8_t asBytes[8];
    uint64_t asQWord;
};

const union qword_t table[16][256] = /* ... */;

使用选项 -m64 -Ofast -mno-sse 它确实展开循环，并且每个异或赋值产生 3 条指令(因此发出的指令总数是3 * 16 = 48):

movzx  r9d, byte ptr [Y + i]                   ; extracting byte
xor    rax, qword ptr [table + r9*8 + SHIFT]   ; xoring, SHIFT = i * 0x800
mov    qword ptr [X], rax                      ; storing result

现在，我的理解是生成的 X 值可以在所有 16 个异或运算中累加到 rax 寄存器中，然后它可以存储在 [X] 地址，对于每个带赋值的异或，可以通过这两条指令来实现:

movzx  r9d, byte ptr [Y + i]                   ; extracting byte
xor    rax, qword ptr [table + r9*8 + SHIFT]   ; xoring, SHIFT = i * 0x800

和单存储:

mov    qword ptr [X], rax                      ; storing result

(在这种情况下，指令总数为 2 * 16 + 1 = 33)

为什么 GCC 会生成这些冗余的 mov 指令？我该怎么做才能避免这种情况？

附言C99、GCC 5.3.0、Intel Core i5 Sandy Bridge

Answer 1

冗余商店通常会导致别名；在这种情况下，gcc 将无法令人满意地证明对 X[0] 的存储不会影响 table。 如何将变量传递给例程有很大的不同；如果它们是全局变量或同一个更大结构的成员，那么证明非别名会更容易。

Example :

void f1(uint64_t X[2]) {
  memset(X, 0, 16);
  for (int i= 0; i < 16; ++i) {
    X[0] ^= table[i][Y[i]].asQWord;
  }
}

uint64_t X[2];
void f2() {
  memset(X, 0, 16);
  for (int i= 0; i < 16; ++i) {
    X[0] ^= table[i][Y[i]].asQWord;
  }
}

这里对 X[0] 的存储在 f2 中而不是在 f1 中陷入循环之外，因为仅在 >f2 gcc 可以证明X 没有别名table 的成员。

您的解决方法/修复可能是调整参数的传递方式，以使用 the restrict specifier ，或自己手动下沉商店。