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 指令？我该怎么做才能避免这种情况？

P.S。 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 才能证明 [=17] =] 不为 table.

的成员起别名

你的workaround/fix可能是调整参数的传递方式，使用the restrict specifier，或者自己手动下沉store。

Answer 2

为避免这种情况，您可以改用它：

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

您可以很容易地注意到生成的指令在您的情况下不是最佳的，但是由于不同的原因 gcc 可能无法确定这一点。（在这种情况下，gcc 无法确定 table 永远不会访问与 X 相同的内存区域，正如 ecatmur 更详细地解释的那样。）

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

GCC generates redundant code for repeated XOR of an array element

c

assembly

gcc

compiler-optimization