Почему оптимизирован простой цикл, когда ограничение составляет 959, но не 960?

Рассмотрим этот простой цикл:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 959; i++)
    p += 1;
  return p;
}

Если вы компилируете с помощью gcc 7 (снимок) или clang (ствол), -march=core-avx2 -Ofastвы получите что-то очень похожее на.

.LCPI0_0:
        .long   1148190720              # float 960
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Другими словами, он просто устанавливает ответ на 960 без зацикливания.

Однако если вы измените код на:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 960; i++)
    p += 1;
  return p;
}

Произведенная сборка действительно выполняет сумму цикла? Например, clang дает:

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   1086324736              # float 6
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        vxorps  ymm1, ymm1, ymm1
        mov     eax, 960
        vbroadcastss    ymm2, dword ptr [rip + .LCPI0_1]
        vxorps  ymm3, ymm3, ymm3
        vxorps  ymm4, ymm4, ymm4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vaddps  ymm0, ymm0, ymm2
        vaddps  ymm1, ymm1, ymm2
        vaddps  ymm3, ymm3, ymm2
        vaddps  ymm4, ymm4, ymm2
        add     eax, -192
        jne     .LBB0_1
        vaddps  ymm0, ymm1, ymm0
        vaddps  ymm0, ymm3, ymm0
        vaddps  ymm0, ymm4, ymm0
        vextractf128    xmm1, ymm0, 1
        vaddps  ymm0, ymm0, ymm1
        vpermilpd       xmm1, xmm0, 1   # xmm1 = xmm0[1,0]
        vaddps  ymm0, ymm0, ymm1
        vhaddps ymm0, ymm0, ymm0
        vzeroupper
        ret

Почему это так и почему это точно так же для clang и gcc?

Предел для того же цикла при замене floatна double479. То же самое для gcc и снова clang.

Обновление 1

Оказывается, gcc 7 (снимок) и clang (ствол) ведут себя по-разному. clang оптимизирует циклы для всех лимитов меньше 960, насколько я могу судить. gcc с другой стороны, чувствителен к точному значению и не имеет верхнего предела. Например , он не оптимизирует из цикла , когда предел равен 200 (а также множество других значений) , но это делает , когда предел составляет 202 и 20002 (равно как и многие другие значения).

TL; DR

По умолчанию текущий моментальный снимок GCC 7 ведет себя непоследовательно, тогда как предыдущие версии имеют ограничение по умолчанию, равное PARAM_MAX_COMPLETELY_PEEL_TIMES16. Его можно переопределить из командной строки.

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

Версия GCC <= 6.3.0

Соответствующий вариант оптимизации для GCC -fpeel-loops, который включается косвенно вместе с флагом -Ofast(выделено мной):

Удаляет петли, для которых достаточно информации, чтобы они не сильно катились (из отзывов профиля или статического анализа ). Он также включает полное удаление петель (т.е. полное удаление петель с небольшим постоянным числом итераций ).

Включено с помощью -O3и / или -fprofile-use.

Более подробную информацию можно получить, добавив -fdump-tree-cunroll:

$ head test.c.151t.cunroll 

;; Function f (f, funcdef_no=0, decl_uid=1919, cgraph_uid=0, symbol_order=0)

Not peeling: upper bound is known so can unroll completely

Сообщение от /gcc/tree-ssa-loop-ivcanon.c:

if (maxiter >= 0 && maxiter <= npeel)
    {
      if (dump_file)
        fprintf (dump_file, "Not peeling: upper bound is known so can "
         "unroll completely\n");
      return false;
    }

следовательно, try_peel_loopфункция возвращается false.

Более подробный вывод можно получить с помощью -fdump-tree-cunroll-details:

Loop 1 iterates 959 times.
Loop 1 iterates at most 959 times.
Not unrolling loop 1 (--param max-completely-peeled-times limit reached).
Not peeling: upper bound is known so can unroll completely

Можно настроить лимиты по Тропангпланга с max-completely-peeled-insns=nи max-completely-peel-times=nТитулы:

max-completely-peeled-insns

Максимальное количество петель полностью очищенной петли.

max-completely-peel-times

Максимальное количество итераций цикла, подходящее для полного пилинга.

Чтобы узнать больше о insns, вы можете обратиться к GCC Internals Manual .

Например, если вы компилируете со следующими параметрами:

-march=core-avx2 -Ofast --param max-completely-peeled-insns=1000 --param max-completely-peel-times=1000

тогда код превращается в:

f:
        vmovss  xmm0, DWORD PTR .LC0[rip]
        ret
.LC0:
        .long   1148207104

лязг

Я не уверен, что на самом деле делает Clang и как настроить его пределы, но, как я заметил, вы можете заставить его оценить окончательное значение, пометив цикл с помощью прагмы unroll , и он полностью удалит его:

#pragma unroll
for (int i = 0; i < 960; i++)
    p++;

приводит к:

.LCPI0_0:
        .long   1148207104              # float 961
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Прочитав комментарий Султана, я думаю, что:

1. Компилятор полностью разворачивает цикл, если счетчик цикла постоянный (и не слишком высокий).

2. После его развертывания компилятор видит, что операции суммирования можно сгруппировать в одну.

Если цикл по какой-то причине не развернут (здесь: он генерирует слишком много операторов с 1000), операции не могут быть сгруппированы.

Компилятор мог видеть, что развертывание 1000 операторов составляет одно добавление, но шаги 1 и 2, описанные выше, представляют собой две отдельные оптимизации, поэтому он не может брать на себя «риск» развертывания, не зная, можно ли сгруппировать операции (пример: вызов функции не может быть сгруппирован).

Примечание. Это угловой случай: кто использует цикл, чтобы добавить одно и то же снова? В этом случае не полагайтесь на возможную развертку / оптимизацию компилятора; прямо напишите правильную операцию в одной инструкции.

Очень хороший вопрос!

Похоже, вы достигли предела количества итераций или операций, которые компилятор пытается встроить при упрощении кода. Как задокументировано Гжегожем Шпетковским, существуют специфические для компилятора способы настройки этих ограничений с помощью прагм или параметров командной строки.

Вы также можете поиграть с обозревателем компиляторов Godbolt, чтобы сравнить, как различные компиляторы и параметры влияют на сгенерированный код: gcc 6.2и по- icc 17прежнему встраивают код для 960, тогда как clang 3.9нет (с конфигурацией Godbolt по умолчанию он фактически прекращает встраивание на 73).