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

Original author: Tyler Nowicki
  • Translation
Часто программисты полагаются на компилятор в вопросе векторизации циклов. Но компилятор не всесилен, ему зачастую тоже требуется помощь при разборе трудных участков. В данной статье есть ответ на вопрос: как узнать, где компилятор испытывает сложности с векторизацией и как помочь ему их преодолеть?

Векторизация циклов в LLVM впервые была представлена в версии 3.2, в версии 3.3 она стала включена по умолчанию. Векторизация уже обсуждалась в этом блоге в 2012 г. и в 2013 г., а также на конференциях FOSDEM 2014 и WWDC 2013. Векторизатор LLVM выполняет многочисленные итеративные операции над циклами для увеличения производительности. Современные процессоры могут распараллеливать выполнение идущих друг за другом и независимых друг от друга инструкций используя поддержку на уровне железа — множественные исполнительные блоки и внеочередное исполнение команд.
К сожалению, в случае, когда векторизация цикла невозможна, либо не ведет к увеличению эффективности, компилятор без всякого уведомления просто пропустит этот цикл. Это проблема для многих приложений, которые полагаются на то, что компилятор правильно векторизует имеющиеся циклы. Недавние обновления LLVM до версии 3.5 добавили новые аргументы командной строки, которые могут помочь определить причины, мешающие векторизации.

Сообщения об анализе циклов


Данные сообщения предоставляют пользователю информацию от оптимизатора LLVM, включая данные о развертке циклов, изменении порядка выполнения инструкций (также называется чередование или интерливинг от английского interleaving) и векторизации. Для вывода этих сообщений компилятору нужно передать аргумент '-Rpass' с параметром 'loop-vectorize'. Приведенный ниже пример показывает цикл, который был векторизован с параметром 4 и команды которого подверглись чередованию с параметром 2.
void test1(int *List, int Length) {
  int i = 0;
  while(i < Length) {
    List[i] = i*2;
    i++;
  }
}

clang -O3 -Rpass=loop-vectorize -S test1.c -o /dev/null

test1.c:4:5: remark: 
 vectorized loop (vectorization factor: 4, unrolling interleave factor: 2)
     while(i < Length) {
     ^

Много циклов не может быть векторизовано из-за сложного потока управления (например, много блоков if), а также если цикл содержит типы данных, не подлежащих векторизации, или невекторизуемые вызовы функций.
Например, для векторизации представленного ниже кода нужно сначала убедиться, что массив 'A' не является псевдонимом для 'B' (не указывает на тот же адрес, да и вообще не пересекается с ним). Но оптимизатор не сможет это узнать, так как не знает количество элементов в 'A'.
void test2(int *A, int *B, int Length) {
  for (int i = 0; i < Length; i++)
    A[B[i]]++;
}

clang -O3 -Rpass-analysis=loop-vectorize -S test2.c -o /dev/null

test2.c:3:5: remark:
 loop not vectorized: cannot identify array bounds
     for (int i = 0; i < Length; i++)
     ^

Список невекторизуемых операторов можно получить используя аргумент командной строки '-Rpass-analysis=loop-vectorize'. Например, во многих случаях 'break' и 'switch' нельзя векторизовать.
В первом примере можем увидеть, что векторизации мешает простейший условный переход
for (int i = 0; i < Length; i++) {
  if (A[i] > 10.0)
    break;
  A[i] = 0;

}

control_flow.cpp:5:9: remark: loop not vectorized: loop control flow is not understood by vectorizer
    if (A[i] > 10.0)
        ^

Второй пример демонстрирует неудачу векторизации из-за того, что цикл просто содержит switch
for (int i = 0; i < Length; i++) {
  switch(A[i]) {
  case 0: B[i] = 1; break;
  case 1: B[i] = 2; break;
  default: B[i] = 3;
  }

}

no_switch.cpp:4:5: remark: loop not vectorized: loop contains a switch statement
    switch(A[i]) {
    ^


Новая pragma-директива для циклов

Явный контроль над векторизацией, созданием чередующихся команд и разверткой циклов необходим для оптимальной настройки производительности программы. Например, когда компиляция проводится с флагом -Оs, то есть с оптимизацией по размеру, векторизация наиболее часто вызываемых циклов является отличной идеей. Векторизация, чередование команд и развертка циклов могут быть явно специфицированы с использованием директивы #pragma clang loop для любого цикла for, while, do-while или range-based for из стандарта C++11. Например, величина векторизации и количество чередующихся команд указываются с использованием директивы pragma для циклов.
void test3(float *Vx, float *Vy, float *Ux, float *Uy, float *P, int Length) {
#pragma clang loop vectorize_width(4) interleave_count(4)
#pragma clang loop unroll(disable)
  for (int i = 0; i < Length; i++) {
    float A = Vx[i] * Ux[i];
    float B = A + Vy[i] * Uy[i];
    P[i] = B;
   }
}

clang -O3 -Rpass=loop-vectorize -S test3.c -o /dev/null

test3.c:5:5: remark:
 vectorized loop (vectorization factor: 4, unrolling interleave factor: 4)
     for (int i = 0; i < Length; i++) {
     ^


Целочисленные константные выражения

Параметры рассмотренной выше pragma-директивы (vectorize_width, interleave_count и unroll_count) принимают целочисленные константы, но также туда можно передать и результат выражения, вычисленного во время компиляции, как в следующем примере:

template <int ArchWidth, int ExecutionUnits>
void test4(float *Vx, float *Vy, float *Ux, float *Uy, float *P, int Length) {
#pragma clang loop vectorize_width(ArchWidth)
#pragma clang loop interleave_count(ExecutionUnits * 4)
  for (int i = 0; i < Length; i++) {
    float A = Vx[i] * Ux[i];
    float B = A + Vy[i] * Uy[i];
    P[i] = B;
   }
}

void compute_test4(float *Vx, float *Vy, float *Ux, float *Uy, float *P, int Length) {
  const int arch_width = 4;
  const int exec_units = 2;
  test4<arch_width, exec_units>(Vx, Vy, Ux, Uy, P, Length);
}


Теперь соберем это:
clang++ -O3 -Rpass=loop-vectorize -S test4.cpp -o /dev/null

test4.cpp:6:5: remark:
 vectorized loop (vectorization factor: 4, unrolling interleave factor: 8)
     for (int i = 0; i < Length; i++) {
     ^


Предупреждения о невозможности векторизации

Конечно же, даже при явном указании не всегда возможна векторизация. Например, из-за сложного потока управления. Если явно объявленная векторизация сталкивается с подобными проблемами, то выводится предупреждающее сообщение что данная директива не может быть выполнена. Ниже представлен пример функции, возвращающей индекс последнего положительного числа из цикла, и этот цикл не может быть векторизован по причине использования переменной 'last_positive_index' за его пределами:
int test5(int *List, int Length) {
  int last_positive_index = 0;
  #pragma clang loop vectorize(enable)
  for (int i = 1; i < Length; i++) {
    if (List[i] > 0) {
      last_positive_index = i;
      continue;
    }
    List[i] = 0;
  }
  return last_positive_index;
}

clang -O3 -g -S test5.c -o /dev/null

test5.c:5:9: warning:
 loop not vectorized: failed explicitly specified loop vectorization
    for (int i = 1; i < Length; i++) {
        ^

Строку начала цикла, который не удается векторизовать, в этом случае можно получить только при использовании аргумента '-g'

Заключение

Диагностические сообщения и pragma-директива для циклов — это два нововведения, которые довольно полезны для настройки производительности программ. Особое спасибо всем, кто сделал вклад в разработку этих дополнений. В будущем нужно будет добавить вывод диагностических сообщений для SLP-векторизатора и дополнительные параметры для pragma-директивы. Если есть еще какие-то идеи о том, как и что сделать лучше — буду рад услышать.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 17

    +3
    Ну в кои-то веки разработчики догадались, что компилятор должен сообщать о своей кухне и причинах того, что он делает. Интересно, почему до этого столько времени все гадали на кофейной гуще?
      +6
      Вы так говорите, как будто бы 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
      

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

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

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

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

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

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

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

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

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

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

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

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

              Вот в том-то и дело, что зависимости с точки зрения шедулера не нарушаются, а логика программы может поменяться. Особенно, если это часть многопоточного кода (конечно, тут может быть ошибка из-за не выставленного барьера памяти, но ведь компилятор таким бы образом смог бы предупредить о ней, а не молча проглотить).
        0
        Специально ради вашего поста обновил 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
          +1
          Все сам разобрался. Clang 3.5 нужен. минимум: llvm.org/releases/3.5.0/tools/clang/docs/ReleaseNotes.html#improvements-to-clang-s-diagnostics
            0
            Действительно, стоило отметить используемую версию. Добавил в первый абзац перевода.
            0
            Спасибо за замечание по примеру №4. Там неточность в расширении файла. Исправил.
              +1
              У вас в 4-м примере. Шаблоны, так что это именно c++. Т.е. Расширение правильное было. Нужен именно clang++.
                +1
                Спасибо. Поторопился, извиняюсь за недоразумение. Исправил.
            +1
            Спасибо за статью.

            По поводу векторизации в LLVM, мне кажется, стоит отметить, что LLVM умеет векторизовывать логику самого вложенного цикла очень сильно включая конструкции if, else и даже goto (см. ссылку). Не очень понятно, почему в статье switch считается невекторизуемой конструкцией, хотя если применить фантазию то становится понятно, что switch конструкции можно свести к серии условий.
              0
              Ценное дополнение. По поводу switch мне тоже кажется не очень ясным, почему при хорошей векторизации if,else простейший switch лишает цикл шанса быть векторизованным (там же, чуть выше).
                +1
                Кстати, если использовать OpenMP SIMD конструкцию collapse (OMP 4.0+), то векторизовать можно и гнезда циклов:

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


                Поддержка OMP SIMD в некотором виде в транковом LLVM уже есть.
                +1
                Есть еще один способ дампить логи векторизатора. При этом дампятся более низкоуровневые вещи, типа вычислений стоимостей отдельных IR-инструкций. Я в своё время добавлял к этим логам красоты и подробностей.
                clang foo.c -mllvm -debug-only=loop-vectorize
                

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

                Для тех, у кого есть много свободного времени, можно вывести логи всего:
                clang foo.c -mllvm -debug
                

                Only users with full accounts can post comments. Log in, please.