НКУ петли разворачивая странность

Question

В процессе написания «не равно сканирование» для булевых массивов, я в конечном итоге написание этого цикла:

// Heckman recursive doubling 
#ifdef STRENGTHREDUCTION // Haswell/gcc does not like the multiply 
    for(s=1; s<BITSINWORD; s=s*2) { 
#else // STRENGTHREDUCTION 
    for(s=1; s<BITSINWORD; s=s+s) { 
#endif // STRENGTHREDUCTION 
     w = w XOR (w >> s); 
    } 

Что я заметил, что НКА БЫ раскатать S = S * 2, , но не петля s = s + s. Это немного неинтуитивно, поскольку анализ циклов для добавления должен, IMO быть проще , чем для умножения. Я подозреваю, что gcc знает значение цикла s = s + s и просто является coy.

Кто-нибудь знает, есть ли веские причины для этого поведения на стороне gcc? Я спрашиваю это из любопытства ...

[развернутая версия, кстати, провела изрядную немного медленнее, чем петли.]

Спасибо, Robert

Answer 1

Это интересно.

Первое предположение

Мой первый бы предположить, что анализ цикла развертываться GCC ожидает в случае добавления в пользу менее из петли разворачивания, потому что s растет медленнее.

I эксперимент на следующий код:

#include <stdio.h> 
int main(int argc, char **args) { 
    int s; 
    int w = 255; 
    for (s = 1; s < 32; s = s * 2) 
    { 
     w = w^(w >> s); 
    } 
    printf("%d", w); // To prevent everything from being optimized away 
    return 0; 
} 

И еще одна версия, что это то же самое, кроме петли имеет s = s + s. Я нахожу, что gcc 4.9.2 разворачивает цикл в мультипликативной версии, но не в аддитивной. Это компиляция с

gcc -S -O3 test.c 

Итак, мой первый догадаться, что GCC предполагает присадка версия, если раскатали, приведет к увеличению числа байтов кода, которые соответствуют в ICACHE и поэтому не оптимизировать. Однако изменение условия цикла от s < 32 до s < 4 в аддитивной версии по-прежнему не приводит к оптимизации, хотя кажется, что gcc должен легко распознать, что существует очень мало итераций цикла.

Моя следующая попытка (вернуться к s < 32 как условие), чтобы явно указать GCC раскатать петли до 100 раз:

gcc -S -O3 -fverbose-asm --param max-unroll-times=100 test.c 

Это до сих пор производит петлю в сборе. Попытка разрешить дополнительные инструкции в развернутых циклах с помощью -param max-unrolled-insns также сохраняет цикл. Поэтому мы можем в значительной степени исключить возможность того, что gcc считает, что он неэффективен для разворачивания.

Интересно, что попытка скомпилировать с clang на -O3 немедленно разворачивает петлю. clang - known to unroll more aggressively, но это не похоже на удовлетворительный ответ.

Я могу получить gcc, чтобы развернуть цикл добавок, сделав его добавлением константы, а не s, то есть s = s + 2. Затем цикл развернется.

Второе предположение

Это приводит ко мне теоретизировать, что НКУ не в состоянии понять, сколько итераций цикла будет выполняться для (необходимо для разворачивания), если увеличение значения Петля зависит от значения счетчика больше, чем один раз. Изменить цикл следующим образом:

for (s = 2; s < 32; s = s*s) 

И это не раскатывать с НКУ, а лязг разворачивает его. Поэтому, в конце концов, я думаю, что gcc не может вычислить количество итераций, когда оператор инкремента цикла имеет форму s = s (op) s.

Answer 2

Компиляторы обычно выполняют снижение силы, поэтому я ожидал бы, что gcc использовал бы его здесь, заменив s * 2 на s + s, после чего формы обоих выражений будут совпадать.

Если это не так, то я думаю, что это ошибка в gcc. Анализ для вычисления числа циклов с использованием s + s является (незначительно) более простым, чем с использованием s * 2, поэтому я ожидал бы, что gcc будет (незначительно) более вероятным развернуть случай s + s.