Векторизация циклов: диагностика и контроль

[Mingun]

Ну в кои-то веки разработчики догадались, что компилятор должен сообщать о своей кухне и причинах того, что он делает. Интересно, почему до этого столько времени все гадали на кофейной гуще?

[ilammy]

Вы так говорите, как будто бы gcc не умеет дампить информацию.

cat i.c

$ cat i.c
void func(int *data, int size)
{
        int i;

        i = 0;
        while (i < size)
        {
                data[i] = i * 2;
                i++;
        }
}

gcc -O3

$ gcc -O3 -march=native -c -fdump-tree-vect-details -ftree-vectorizer-verbose=1 i.c

Analyzing loop at i.c:6


Vectorizing loop at i.c:6

i.c:6: note: === vect_do_peeling_for_alignment ===
i.c:6: note: niters for prolog loop: MIN_EXPR <-(((unsigned int) vect_pdata.7_2 & 15) >> 2) & 3, niters.4_19>Setting upper bound of nb iterations for prologue loop to 5

i.c:6: note: === vect_update_inits_of_dr ===
i.c:6: note: === vect_do_peeling_for_loop_bound ===Setting upper bound of nb iterations for epilogue loop to 2

i.c:6: note: LOOP VECTORIZED.
i.c:1: note: vectorized 1 loops in function.

i.c:6: note: Completely unroll loop 2 times

i.c:1: note: Completely unroll loop 5 times

$ wc -l i.c.112t.vect
597 i.c.112t.vect

Ну, да, она несколько менее читабельна для казуалов:

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

Analyzing loop at i.c:6

i.c:6: note: ===== analyze_loop_nest =====
i.c:6: note: === vect_analyze_loop_form ===
i.c:6: note: === get_loop_niters ===Analyzing # of iterations of loop 1
  exit condition [1, + , 1](no_overflow) < size_4(D)
  bounds on difference of bases: 0 ... 2147483646
  result:
    # of iterations (unsigned int) size_4(D) + 4294967295, bounded by 2147483646

. . .

i.c:6: note: vectorization factor = 4
i.c:6: note: === vect_analyze_data_refs_alignment ===
i.c:6: note: vect_compute_data_ref_alignment:
i.c:6: note: can't force alignment of ref: *_8
i.c:6: note: === vect_analyze_data_ref_accesses ===
i.c:6: note: === vect_prune_runtime_alias_test_list ===
i.c:6: note: === vect_enhance_data_refs_alignment ===
i.c:6: note: Unknown misalignment, is_packed = 0
i.c:6: note: vect_can_advance_ivs_p:
i.c:6: note: Analyze phi: i_14 = PHI <i_11(7), 0(4)>

. . .

i.c:6: note: === vect_update_slp_costs_according_to_vf ===cost model: prologue peel iters set to vf/2.cost model: epilogue peel iters set to vf/2 because peeling for alignment is unknown.
i.c:6: note: Cost model analysis:
  Vector inside of loop cost: 4
  Vector prologue cost: 18
  Vector epilogue cost: 6
  Scalar iteration cost: 3
  Scalar outside cost: 7
  Vector outside cost: 24
  prologue iterations: 2
  epilogue iterations: 2
  Calculated minimum iters for profitability: 7

. . .

loop at i.c:8: if (ivtmp_77 < bnd.11_43)
;; Scaling loop 1 with scale 0.250000, bounding iterations to 2 from guessed 11
;; guessed iterations are now 1

Но кому действительно надо понимать, почему компилятор выдаёт такой код, а не другой, тот не будет гадать на кофейной гуще.

[Mingun]

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

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

А был бы вывод, например,

— обратите внимание: функция '%1' объявлена как inline, но генерируется отдельное тело, потому что в '%2' получается ее указатель
— обратите внимание: функция '%1' была встроена (inline) в месте вызова '%2'
— обратите внимание: операции '%1' и '%2' были переставлены местами
— обратите внимание: выражение '%1' вычислено при компиляции
— обратите внимание: условие всегда 'true/false', поэтому ветка 'then/else' выкинута из кода
— обратите внимание: цикл '%1' развернут

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

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

[ilammy]

Не знал, однако, с какой версии он это умеет?

С тех пор, как умеет выполнять автоматическую векторизацию.

перестановок в коде программы, которые могут дать неожиданный эффект

«Неожиданный эффект» — это растяжимое понятие. Компилятор же не знает, что именно вам показалось «очевидно оптимизируемым местом» для «достаточно сообразительного» компилятора.

И соль этих историй обычно заключается в том, что бравый разработчик с IDA наперевес и обложившись стандартом/мануалами по процессору/котом и чашками кофе, пытается понять, что сделал компилятор, почему компилятор сделал так, а главное, как заставить его этого НЕ делать. <...> Но в тех историях явно умные люди почему-то не использовали такие возможности компилятора, из чего я предполагаю, что их просто не было.

Дело больше в том, что компилятор — это невероятно сложная программа. Подобные дампы и есть отражением того, что на самом деле происходит. Но если быть честным, то разработчиков прикладных программ это мало волнует; у них есть своя сложная программа и последнее, что им хочется, — это разбираться в ещё одной. Именно поэтому проблема «у меня не оптимизирует» чаще решается вставкой подсказок компилятору в местах, обнаруженных Идой, а не исправлением компилятора в местах, обнаруженных по таким логам. Ведь проще переписать какой-нибудь невекторизиремый цикл самому, перебрав пяток вариантов, нежели научить компилятор это делать самостоятельно.

[Mingun]

«Неожиданный эффект» — это растяжимое понятие. Компилятор же не знает, что именно вам показалось «очевидно оптимизируемым местом» для «достаточно сообразительного» компилятора.

Я как раз говорю о том, что разработчику ни одно место не кажется очевидно оптимизируемым, но компилятор почему-то решил его соптимизировать, в результате чего программа перестала работать правильно. Вот я и спрашиваю, если такая оптимизация сломает программу, значит, это не преобразование 1:1 (хотя об этом может быть вообще неизвестно, и разработчики компилятора думают, что это преобразование 1:1). Почему компилятор не может сказать об этих опасных манипуляциях?

Дело больше в том, что компилятор — это невероятно сложная программа. Подобные дампы и есть отражением того, что на самом деле происходит.

Я понимаю, что компилятор сложен, но так ведь и больше причин сделать отладочный вывод! Да, какой-то есть, но он слишком подробен. Вы же в своих программах не логгируете все подряд с одним уровнем важности? Что-то более важное, что-то менее, что в большинстве случаев можно отключить, т.к. оно отлажено или наоборот, используется только в очень редких и специфических случаях и нет нужды тратить время/память на логгирование этого всегда. Почему в компиляторе нельзя сделать так же? Точнее, это сделано (разные уровни предупреждений), но почему-то на слишком высоком уровне, хотя можно было бы добавить еще несколько градаций важности, чтобы и лог не перегружать, и понимать, что происходит.

[Gumanoid]

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

Например, запустился instruction scheduling и начал таскать туда-сюда инструкции (зависимости по данным и по управлению с точки зрения скуделера не нарушаются), на какую перестановку он должен выдавать сообщение?

[Mingun]

На каждое изменение в конечном результате относительного порядка инструкций. Когда-то же он закончит их таскать туда-сюда и на каком-то варианте остановится?

зависимости по данным и по управлению с точки зрения скуделера не нарушаются

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

[rotor]

Специально ради вашего поста обновил Clang с 3.2 на

3.4

$ clang -v
Ubuntu clang version 3.4-1ubuntu1 (trunk) (based on LLVM 3.4)
Target: x86_64-pc-linux-gnu
Thread model: posix

Но во всех примерах получаю: clang: warning: argument unused during compilation: '-Rpass=loop-vectorize'
В примере #4 вы видимо имели ввиду clang++ -O3 -Rpass=loop-vectorize -S test4.cpp -o /dev/null

[rotor]

Все сам разобрался. Clang 3.5 нужен. минимум: llvm.org/releases/3.5.0/tools/clang/docs/ReleaseNotes.html#improvements-to-clang-s-diagnostics

[kpdev]

Действительно, стоило отметить используемую версию. Добавил в первый абзац перевода.

[kpdev]

Спасибо за замечание по примеру №4. Там неточность в расширении файла. Исправил.

[rotor]

У вас в 4-м примере. Шаблоны, так что это именно c++. Т.е. Расширение правильное было. Нужен именно clang++.

[kpdev]

Спасибо. Поторопился, извиняюсь за недоразумение. Исправил.

[Halt]

Спасибо за статью.

По поводу векторизации в LLVM, мне кажется, стоит отметить, что LLVM умеет векторизовывать логику самого вложенного цикла очень сильно включая конструкции if, else и даже goto (см. ссылку). Не очень понятно, почему в статье switch считается невекторизуемой конструкцией, хотя если применить фантазию то становится понятно, что switch конструкции можно свести к серии условий.

[kpdev]

Ценное дополнение. По поводу switch мне тоже кажется не очень ясным, почему при хорошей векторизации if,else простейший switch лишает цикл шанса быть векторизованным (там же, чуть выше).

[irishrover]

Кстати, если использовать OpenMP SIMD конструкцию collapse (OMP 4.0+), то векторизовать можно и гнезда циклов:

#pragma omp simd collapse(3)
for(i=...
  for(j=...
    for(k=...
       body(i, j, k);

Поддержка OMP SIMD в некотором виде в транковом LLVM уже есть.

[irishrover]

Есть еще один способ дампить логи векторизатора. При этом дампятся более низкоуровневые вещи, типа вычислений стоимостей отдельных IR-инструкций. Я в своё время добавлял к этим логам красоты и подробностей.

clang foo.c -mllvm -debug-only=loop-vectorize

Логи векторизатора начинаются с символов

LV:

Для тех, у кого есть много свободного времени, можно вывести логи всего:

clang foo.c -mllvm -debug