gcc constant folding , dela

Добрый день.

Возьмем такой исходник:

template<int n>
inline bool constexpr cmp(int const *a, int const *b) {
  for(int i = 0; i < n; ++i)
    if(a[i] != b[i]) return false;
  return true;
}
 
bool f3() {
  int const a[3] = { 0, 1, 3};
  int const b[3] = { 0, 1, 3};
 
  return cmp<3>(a, b);
}

f3() сворачивается в 'return true;' (objdump -drC):

0000000000000000 <f3()>:
   0: b8 01 00 00 00        mov    $0x1,%eax
   5: c3                    retq

Это нормально. Это называется contant folding, как я понял.

Развлекаемся дальше (это все про gcc-6.1.0, со снапшотом из SVN (Rev: 238307) дела обстоят еще хуже и о нем здесь не будем).

Аналогичная функция 'f4()' выглядит так:

0000000000000220 <f4()>:
 220: 66 0f 6f 05 00 00 00  movdqa 0x0(%rip),%xmm0        # 228 <f4()+0x8>
 227: 00
      224: R_X86_64_PC32  .LC0-0x4
 228: 0f 29 44 24 d8        movaps %xmm0,-0x28(%rsp)
 22d: 0f 29 44 24 e8        movaps %xmm0,-0x18(%rsp)
 232: 8b 44 24 f0           mov    -0x10(%rsp),%eax
 236: 39 44 24 e0           cmp    %eax,-0x20(%rsp)
 23a: 75 14                 jne    250 <f4()+0x30>
 23c: 8b 44 24 f4           mov    -0xc(%rsp),%eax
 240: 39 44 24 e4           cmp    %eax,-0x1c(%rsp)
 244: 0f 94 c0              sete   %al
 247: c3                    retq  
 248: 0f 1f 84 00 00 00 00  nopl   0x0(%rax,%rax,1)
 24f: 00
 250: 31 c0                 xor    %eax,%eax
 252: c3                    retq

Ой! Он кладет одни и те же 16 байт в 2 места и потом сравнивает порциями с шагом по 8 байт (еще раз ой, я только сейчас заметил, что загружает и сравнивает
он 4-байтный eax, а не 8-байтный rax, ну да ладно пока). Короче, он явно старался, но что-то не срослось.

Примеры с аналогичным 'f6()', который тоже успешно сворачивается в 'return true;', хотя он и больше, чем 'f4()' и другими показывают, что получить финальную констату ему все-таки хочется, но не всегда получается из-за недостаточной мотивации или наличия каких-то дополнительных соблазнов типа поиспользовать mmx.

Так вот, собственно, о чем вопрос. Наверняка есть тут какая-то рукоятка, которая мотивацию эту повышает. Из разряда '--params', на которую посматривают из 'gcc/fold-const.c' я нашел только 'max-ssa-name-query-depth', но только дергать за нее тут почему-то без толку. Вдумчиво читать исходники gcc у меня сейчас нет времени и я прошу совета у тех, кто в теме.

Eugene513, а флаги оптимизации в первом и втором случае - одинаковые? Какие именно?

Для "исследований" рекомендую пользоваться онлайн сервисом http://godbolt.org/.

Второй вариант я так и не смог получить. Вот примеры.

Исходный код:

Скрытый текст

template<int n>
inline bool constexpr cmp(int const *a, int const *b) {
 for(int i = 0; i < n; ++i) if(a[i] != b[i]) return false;
 return true;
}
    
bool f3() {
 int const a[3] = { 0, 1, 3};
 int const b[3] = { 0, 1, 3};
 return cmp<3>(a, b);
}
 
int main() {
  f3();
  return 0;
}

x86 gcc 5.1 (-std=c++14 -O2)

f3():
        mov     eax, 1
        ret
main:
        xor     eax, eax
        ret

x86 gcc 6.1 (-std=c++14 -O2)

f3():
        mov     eax, 1
        ret
main:
        xor     eax, eax
        ret

x86 clang 3.8 (-std=c++14 -O2)

f3():                                 # @f3()
        mov     al, 1
        ret
 
main:                                   # @main
        xor     eax, eax
        ret

Цитата JoeUser @ 14.07.16, 07:23

Eugene513, а флаги оптимизации в первом и втором случае - одинаковые? Какие именно?

Да, разумеется, '-O3'.

На стенде (http://godbolt.org) дает то же самое.

Тут такое дело, если взять '-O2', то не сворачивается уже 'f6()'. С '-O3' успешно сворачивается вплоть до 'f17()' за пропуском кратных 4 ('f4()', 'f8()', 'f12()' и 'f16()'). Если '-O3 -mno-sse', то сворачиваются только нечетные, но тоже вплоть до 'f17()'. Очень странное поведение, одним словом.

Цитата Eugene513 @ 14.07.16, 11:27

то не сворачивается уже 'f6()'

А можно полный пример кода и условий компиляции (версия gcc и флаги) на стенде?

Вот ссылка на вариант '-О3' (чтоб не копипастить и не промахнуться на копипасте).

godbolt.org

Цитата Eugene513 @ 14.07.16, 13:26

Вот ссылка на вариант '-О3' (чтоб не копипастить и не промахнуться на копипасте).

Увы, ссылка нерабочая - мне показывается какой-то из моих тестов двухмесячной давности. Видать "особенности" этого сайте. Так что, если не сложно, приведи код, используемый компилятор, и ключи командной строки. Иначе я и не знаю чего обсуждать - нужен работающий, воспроизводимый пример.

Да уж. Ну и сервис у них

Вот исходник.

Скрытый текст

template<int n>
inline bool constexpr cmp(int const *a, int const *b) {
  for(int i = 0; i < n; ++i)
    if(a[i] != b[i]) return false;
  return true;
}
 
bool f18() {
  int const a[18] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6 };
  int const b[18] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6 };
 
  return cmp<18>(a, b);
}
 
bool f17() {
  int const a[17] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5 };
  int const b[17] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5 };
 
  return cmp<17>(a, b);
}
 
bool f16() {
  int const a[16] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4 };
  int const b[16] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4 };
 
  return cmp<16>(a, b);
}
 
bool f15() {
  int const a[15] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3 };
  int const b[15] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3 };
 
  return cmp<15>(a, b);
}
 
bool f14() {
  int const a[14] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1 };
  int const b[14] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1 };
 
  return cmp<14>(a, b);
}
 
bool f13() {
  int const a[13] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0 };
  int const b[13] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0 };
 
  return cmp<13>(a, b);
}
 
bool f12() {
  int const a[12] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6 };
  int const b[12] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6 };
 
  return cmp<12>(a, b);
}
 
bool f11() {
  int const a[11] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5 };
  int const b[11] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5 };
 
  return cmp<11>(a, b);
}
 
bool f10() {
  int const a[10] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4 };
  int const b[10] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4 };
 
  return cmp<10>(a, b);
}
 
bool f9() {
  int const a[9] = { 0, 1, 3, 4, 5, 6, 0, 1, 3 };
  int const b[9] = { 0, 1, 3, 4, 5, 6, 0, 1, 3 };
 
  return cmp<9>(a, b);
}
 
bool f8() {
  int const a[8] = { 0, 1, 3, 4, 5, 6, 0, 1 };
  int const b[8] = { 0, 1, 3, 4, 5, 6, 0, 1 };
 
  return cmp<8>(a, b);
}
 
bool f7() {
  int const a[7] = { 0, 1, 3, 4, 5, 6, 0 };
  int const b[7] = { 0, 1, 3, 4, 5, 6, 0 };
 
  return cmp<7>(a, b);
}
 
bool f6() {
  int const a[6] = { 0, 1, 3, 4, 5, 6 };
  int const b[6] = { 0, 1, 3, 4, 5, 6 };
 
  return cmp<6>(a, b);
}
 
bool f5() {
  int const a[5] = { 0, 1, 3, 4, 5 };
  int const b[5] = { 0, 1, 3, 4, 5 };
 
  return cmp<5>(a, b);
}
 
bool f4() {
  int const a[4] = { 0, 1, 3, 4 };
  int const b[4] = { 0, 1, 3, 4 };
 
  return cmp<4>(a, b);
}
 
bool f3() {
  int const a[3] = { 0, 1, 3};
  int const b[3] = { 0, 1, 3};
 
  return cmp<3>(a, b);
}

x86 gcc 6.1

Интересные сочетания ключей:

-O3
-O3 -mno-sse
-O2

Ну компилятор конечно что-то мудрит. Я немного укоротил код:

    template<int n>
    inline bool constexpr cmp(int const *a, int const *b) {
      for(int i = 0; i < n; ++i)
        if(a[i] != b[i]) return false;
      return true;
    }
    
    bool f17(int const *a,int const *b) {
      return cmp<17>(a, b);
    }
 
    bool f18(int const *a,int const *b) {
      return cmp<18>(a, b);
    }
 
int main() {
  int const a[18] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6 };
  int const b[18] = { 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6 };
  f17(a,b);
  f18(a,b);
  return 0;
}

Различия наблюдаются только при -O3, там в случае "17" генерируется "борода" из 17-ти сравнений. А для 18 строится цикл. И похоже для n>17 будет всегда строится цикл. До этого компилятор пытается "инлайнить".

Добавлено 14.07.16, 14:51

Цитата Eugene513 @ 14.07.16, 11:27

Очень странное поведение, одним словом.

В случае компилятора clang 3.8 - n>29. Есть подозрение, что такое поведение забито хардкодом. Не уверен, что там идет просчет по тактам процессора.

Цитата JoeUser @ 14.07.16, 14:46

Я немного укоротил код

Так не видно спецеффектов, о котрых я говорил выше:

Цитата Eugene513 @ 14.07.16, 11:27

С '-O3' успешно сворачивается вплоть до 'f17()' за пропуском кратных 4 ('f4()', 'f8()', 'f12()' и 'f16()'). Если '-O3 -mno-sse', то сворачиваются только нечетные, но тоже вплоть до 'f17()'. Очень странное поведение, одним словом.

Цитата JoeUser @ 14.07.16, 14:46

И похоже для n>17 будет всегда строится цикл. До этого компилятор пытается "инлайнить".

Это понятно, как и понятно то, что при -O2 он перестает инлайнить при n>5.

Странно то, что иногда эти инлайны заканчиваются сверткой констант, а иногда нет, и то что это зависит не от размера, а от каких-то побочных обстоятельств.

Вот если обратить внимание на 'f4()' при '-O3', ведь он же понял, что массивы одинаковые. Он же для сравнения берет один и тот же xmm0, причем попрошу заметить, что сравнивает он только последние два числа из четырех, а про первые два он уже все понял.

Особенно феерически это выглядит если вызвать 'cmp<4>' от массивов различающихся в первой паре:

bool f4() {
  int const a[4] = { 0, 1, 3, 4 };
  int const b[4] = { 0, 2, 3, 4 };
 
  return cmp<4>(a, b);
}

Получается такой почти 'return false;' с мусором:

f4():
        movdqa  .LC0(%rip), %xmm0
        xorl    %eax, %eax
        movaps  %xmm0, -40(%rsp)
        movdqa  .LC3(%rip), %xmm0
        movaps  %xmm0, -24(%rsp)
        ret

Я уже склоняюсь к тому, что это явный баг и пора о нем сообщать разработчикам.

M

Пожалуйста, веди себя прилично!

Сообщение отредактировано: JoeUser - 14.07.16, 16:35

Цитата Eugene513 @ 14.07.16, 15:46

Я уже склоняюсь к тому, что это явный баг и пора о нем сообщать разработчикам.

Немного, имхо, преждевременное предположение. Если бы "оптимизация" явно вела к ухудшению качества кода (я имею ввиду соотношение "размер кода/скорость исполнения"), тогда безусловно репортить нужно. Пока же мы только видим различные варианты герерации, но о качестве ничего сказать не можем. Да, вариации с размером кода очевидны. Но скорость исполнения нужно оценивать. Как в процессорных тактах, так и в эффективности кэша. С тактами - по справочникам пройтись конечно можно. Но с "порчей" кэша - я пасс, как говорится "слышал звон"

Цитата JoeUser @ 14.07.16, 16:45

Цитата Eugene513 @ 14.07.16, 15:46

Я уже склоняюсь к тому, что это явный баг и пора о нем сообщать разработчикам.

Немного, имхо, преждевременное предположение. Если бы "оптимизация" явно вела к ухудшению качества кода (я имею ввиду соотношение "размер кода/скорость исполнения"), тогда безусловно репортить нужно. Пока же мы только видим различные варианты герерации, но о качестве ничего сказать не можем. Да, вариации с размером кода очевидны. Но скорость исполнения нужно оценивать. Как в процессорных тактах, так и в эффективности кэша. С тактами - по справочникам пройтись конечно можно. Но с "порчей" кэша - я пасс, как говорится "слышал звон"

Не, ну глянь внимательно на последний фрагмент.
Он перекладывает в стек 32 байта в два приема и ничего с ними там не делает.
Единственная содержательная инструкция там — это обнуление eax, а остальное бесполезный мусор, которого там быть не должно.

Цитата Eugene513 @ 14.07.16, 15:46

Я уже склоняюсь к тому, что это явный баг и пора о нем сообщать разработчикам.

Хотя ... мож ты и прав. Почему на 5 элементах выдает либо

f4():
        movl    $1, %eax
        ret
main:
        xorl    %eax, %eax
        ret

Если массивы идентичны. И

f4():
        xorl    %eax, %eax
        ret
main:
        xorl    %eax, %eax
        ret

... если различны. Т.е. налицо предварительный просчет и просто занесение результата в EAX (читай расчет времени компиляции). А в "иных" случаях просчет генерируется для рантайма, хотя те же заранее и явно заданные константы.

Добавлено 14.07.16, 17:07

Цитата Eugene513 @ 14.07.16, 16:56

Единственная содержательная инструкция там — это обнуление eax, а остальное бесполезный мусор, которого там быть не должно.

Не не не ... вот очередной тест, чтобы захватило SSE4:

-std=c++14 -O3 -mtune=corei7

f4():
        movdqa  .LC0(%rip), %xmm0
        movaps  %xmm0, -40(%rsp)
        movdqa  .LC1(%rip), %xmm0
        movaps  %xmm0, -24(%rsp)
        movl    -16(%rsp), %eax
        cmpl    %eax, -32(%rsp)
        jne     .L4
        movl    -12(%rsp), %eax
        cmpl    %eax, -28(%rsp)
        sete    %al
        ret
.L4:
        xorl    %eax, %eax
        ret
main:
        xorl    %eax, %eax
        ret
.LC0:
        .long   0
        .long   1
        .long   3
        .long   4
.LC1:
        .long   0
        .long   1
        .long   0
        .long   4

Есть и копирование по регистрам и сравнение частей. Тут все, имхо, норм. Вопрос я уже озвучил ранее - почему запилили расчет в рантайм. Вот это имхо баг.

Добавлено 14.07.16, 17:23
Add: кстати, если не лениво - запили багрепорт с расчетами 4 и 5, пусть растолкуют ху из ху.

Цитата JoeUser @ 14.07.16, 17:03

Не не не ... вот очередной тест, чтобы захватило SSE4

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

Цитата JoeUser @ 14.07.16, 17:03

кстати, если не лениво - запили багрепорт с расчетами 4 и 5, пусть растолкуют ху из ху.

Что-то запилить конечно полезно будет. Но тут ведь как. В контексте gcc-6.1, который находится в стадии «regression fixes & docs only», такое врядли будет воспринято с энтузиазмом и кто-то кинется сразу фиксить. Это же не неверный код и даже не ICE. Ну подумаешь, в коде какая-то лишняя суета, причем на каком-то экзотическом синтетическом примере, который в реальном софтверном мире всречается редко. Не, на серьёзный regression это не тянет. Тут надо смотреть как это обстоит в gcc-7.0, а там это сильно иначе и даже несколько хуже. Если будет скучно на выходных, то можно будет заняться.

Скрытый текст

Eugene513 красавчик развел суету

Добавлено 15.07.16, 03:51
а потом да фиг с ним будет следить

Добавлено 15.07.16, 03:52
нет чувак так не пойдет нашел баг теперь репорт в контору или ты балабол

Добавлено 15.07.16, 03:53
а может это не баг а твое буйное воображение

Добавлено 15.07.16, 03:54
JoeUser сори за оффтоп

Сообщение отредактировано: JoeUser - 15.07.16, 05:01

Upd: В стандарт не заглядывал, поверил хабру

Цитата

constexpr-функция

constexpr возвращаемое_значение имя_функции (параметры)
Ключевое слово constexpr, добавленное в C++11, перед функцией означает, что если значения параметров возможно посчитать на этапе компиляции, то возвращаемое значение также должно посчитаться на этапе компиляции. Если значение хотя бы одного параметра будет неизвестно на этапе компиляции, то функция будет запущена в runtime (а не будет выведена ошибка компиляции).

В наших примерах компилятору все известно, но в ряде случаев ... "функция будет запущена в runtime"

Цитата JoeUser @ 15.07.16, 05:00

В наших примерах компилятору все известно, но в ряде случаев ... "функция будет запущена в runtime"

Да не в этом же дело. В моем примере он родил код, эквивалентный следующему:

struct x_t {
    int x0, x1, x2, x3;
};
 
x_t a = { 0, 1, 3, 4 }, b = { 0, 2, 3, 4 };
 
bool f4() {
    x_t a0 = a, b0 = b;
    return false;
}

и в этом к нему претензии. Если бы он действительно в коде стал сравнивать и нашел разницу между 'a.x1' и 'b.x1', то и пес бы с ним, так ведь нет же.

Скрытый текст

Cfon, твое мнение чрезвычайно важно для меня.

Цитата Eugene513 @ 15.07.16, 11:23

и в этом к нему претензии.

Ну получается да, намусорил. Но константу же вернул верную (типа не равны)?