GCC генерирует избыточный код для повторного XOR элемента массива

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? Что я могу сделать, чтобы избежать этого?

P.S. C99, GCC 5.3.0, Intel Core i5 Sandy Bridge

Ответы

Ответ 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, потому что только в f2 может gcc доказать, что X не является псевдонимом членов table.

Ваш метод обхода/исправления может заключаться в том, чтобы настроить способ передачи параметров, использовать спецификатор restrict или вручную погрузить магазин.

Ответ 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 объясняет более подробно).