GCC: разница векторизации между двумя аналогичными циклами

При компиляции с gcc -O3, почему следующий цикл не векторизовать (автоматически):

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] = b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

когда выполняется следующее:

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foov () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] += b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

Единственное различие заключается в том, является ли результат выражения во внутреннем цикле назначенным [i] или добавлен к [i].

Для справки -ftree-vectorizer-verbose=6 выводится следующий вывод для первого (не-векторизованного) цикла.

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: not vectorized: live stmt not supported: D.2700_5 = c[j_20];

v.c:5: note: vectorized 0 loops in function.

И тот же вывод для цикла, который векторизован:

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: vect_model_load_cost: aligned.
v.c:9: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
v.c:9: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 1 .
v.c:9: note: vect_model_reduction_cost: inside_cost = 1, outside_cost = 6 .
v.c:9: note: cost model: prologue peel iters set to vf/2.
v.c:9: note: cost model: epilogue peel iters set to vf/2 because peeling for alignment is unknown .
v.c:9: note: Cost model analysis:
  Vector inside of loop cost: 3
  Vector outside of loop cost: 27
  Scalar iteration cost: 3
  Scalar outside cost: 7
  prologue iterations: 2
  epilogue iterations: 2
  Calculated minimum iters for profitability: 8

v.c:9: note:   Profitability threshold = 7

v.c:9: note: Profitability threshold is 7 loop iterations.
v.c:9: note: LOOP VECTORIZED.
v.c:5: note: vectorized 1 loops in function.

Ответ 1

В первом случае: код перезаписывает одну и ту же ячейку памяти a[i] на каждой итерации. Это по сути секвенирует цикл, поскольку итерации цикла не являются независимыми.
(На самом деле на самом деле нужна только последняя итерация. Таким образом, можно удалить весь внутренний цикл.)

Во втором случае: GCC распознает цикл как операцию сокращения - для которого он имеет специальную обработку case для векторизации.

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

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

Здесь соответствующая часть исходного кода GCC, которая выплевывает это сообщение "not vectorized: live stmt not supported: ":

http://svn.open64.net/svnroot/open64/trunk/osprey-gcc-4.2.0/gcc/tree-vect-analyze.c

if (STMT_VINFO_LIVE_P (stmt_info))
{
    ok = vectorizable_reduction (stmt, NULL, NULL);

    if (ok)
        need_to_vectorize = true;
    else
        ok = vectorizable_live_operation (stmt, NULL, NULL);

    if (!ok)
    {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
        {
            fprintf (vect_dump, 
                "not vectorized: live stmt not supported: ");
            print_generic_expr (vect_dump, stmt, TDF_SLIM);
        }
        return false;
    }
}

Только строка:

vectorizable_reduction (stmt, NULL, NULL);

Понятно, что GCC проверяет, соответствует ли он шаблону "вектурируемая редукция".

Ответ 2

GCC vectorizer, вероятно, недостаточно умен, чтобы векторизовать первый цикл. Случай сложения проще векторизовать, потому что a + 0 == a. Рассмотрим SIZE==4:

  0 1 2 3 i
0 X
1 X X
2 X X X
3 X X X X
j

X обозначает комбинации i и j, когда a будет присвоено или увеличено. Для случая сложения мы можем вычислить результаты b[i] > c[j] ? b[i] : c[j] для, скажем, j==1 и i==0..4 и поместить его в вектор D. Тогда нам нужно только нуль D[2..3] и добавить результирующий вектор к a[0..3]. Для случая назначения это немного сложнее. Нужно не только нуль D[2..3], но и нуль A[0..1], и только тогда объединить результаты. Я предполагаю, что это значит, что векторный указатель терпит неудачу.

Ответ 3

Первый цикл эквивалентен

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    a[i] = b[i] > c[SIZE - 1] ? b[i] : c[SIZE - 1];
  }
  return a[0];
}

Проблема с исходным выражением заключается в том, что он действительно не имеет большого смысла, поэтому не слишком удивительно, что gcc не может его векторизовать.

Ответ 4

Сначала один просто тривиально меняет [] много раз (временно). Второй использует последнее значение [] каждый раз (не временный).

До версии патча вы можете использовать "изменчивую" переменную для векторизации.

Использование

int * c=malloc(sizeof(int));

чтобы выровнять его;

v.c:9: note: Unknown alignment for access: c

Показывает "c", имеющую разную область хранения, чем b и a.

Я предполагаю, что "movaps" -подобные инструкции для "векторизации" (из списка инструкций SSE-AVX)

Здесь: http://gcc.gnu.org/projects/tree-ssa/vectorization.html#using

6-й и 7-й примеры показывают сходные трудности.