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它会展开循环,每个xor和赋值会产生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值可以rax在所有16 xors中累积到寄存器中,然后它可以存储在[X]地址中,这可以通过这两个指令实现,每个xor具有赋值:

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

PS C99,GCC 5.3.0,Intel Core i5 Sandy Bridge

Answer 1

冗余商店通常会出现混淆; 在这种情况下,gcc将无法证明商店对其X[0]不会产生影响table.如何将变量传递给例程会有很大的不同; 如果它们是全局变量或相同更大结构的成员,那么证明非混叠更容易.

示例:

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,因为只有在f2gcc 中才能证明这X不是别名的成员table.

您的解决方法/修复可能是调整参数的传递方式,使用说明restrict符,或自己手动下沉存储.

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无法确定该表永远不会访问与X相同的内存区域,因为ecatmur更精心地解释了.)