Pull to refresh

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

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

Векторизация циклов в 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-директивы. Если есть еще какие-то идеи о том, как и что сделать лучше — буду рад услышать.
Tags: cc++llvmкомпиляторыоптимизация кода
Hubs: C++ Compilers C
Total votes 32: ↑32 and ↓0 +32
Comments 17
Comments Comments 17

Popular right now

Top of the last 24 hours