kpdev Dec 4 2014 at 18:41

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

5 min

20K

C++*Compilers*C*

Translation

+32

Comments 17

Mingun Dec 4 2014 at 19:43

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

ilammy Dec 4 2014 at 22:10

Вы так говорите, как будто бы 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 Dec 6 2014 at 12:40

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

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

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

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

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

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

ilammy Dec 6 2014 at 13:09

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

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

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

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

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

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

Mingun Dec 6 2014 at 13:45

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

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

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

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

Gumanoid Dec 7 2014 at 14:20

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

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

Mingun Dec 7 2014 at 16:44

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

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

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

rotor Dec 4 2014 at 20:51

Специально ради вашего поста обновил 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 Dec 4 2014 at 21:45

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

kpdev Dec 5 2014 at 01:51

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

kpdev Dec 5 2014 at 01:56

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

rotor Dec 5 2014 at 09:42

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

kpdev Dec 5 2014 at 09:55

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

Halt Dec 5 2014 at 14:31

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

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

kpdev Dec 5 2014 at 17:02

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

irishrover Dec 10 2014 at 17:35

Кстати, если использовать 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 Dec 10 2014 at 09:10

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

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

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

LV:

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

clang foo.c -mllvm -debug