Странность развертывания цикла gcc

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

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

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

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

#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, как известно, разворачивается более агрессивно, но это не не кажется удовлетворительным ответом.

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

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

Это наводит меня на мысль, что gcc не может понять, сколько итераций будет выполнять цикл (необходимо для развертывания), если значение увеличения цикла зависит от значения счетчика более одного раза. Я меняю цикл следующим образом:

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

И он не разворачивается с помощью gcc, а clang разворачивает его. Итак, мое лучшее предположение, в конце концов, заключается в том, что gcc не может рассчитать количество итераций, когда оператор приращения цикла имеет форму s = s (op) s.

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

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