GCC : différence de vectorisation entre deux boucles similaires

Question

Lorsque vous compilez avec gcc -O3 pourquoi la boucle suivante ne se vectorise pas (automatiquement) :

#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];
}

alors que le suivant le fait ?

#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];
}

La seule différence est de savoir si le résultat de l'expression dans la boucle interne est affecté à a[i], ou ajouté à a[i] .

A titre de référence -ftree-vectorizer-verbose=6 donne la sortie suivante pour la première boucle (non vectorisée).

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.

Et la même sortie pour la boucle qui vectorise est :

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.

Answer 1

Dans le premier cas : le code écrase le même emplacement mémoire a[i] à chaque itération. Ceci séquentialise intrinsèquement la boucle puisque les itérations de la boucle ne sont pas indépendantes.
(En réalité, seule l'itération finale est nécessaire. Donc toute la boucle interne pourrait être retirée).

Dans le second cas : GCC reconnaît la boucle comme une opération de réduction - pour laquelle il dispose d'une gestion spéciale des cas pour vectoriser.

La vectorisation du compilateur est souvent implémentée comme une sorte de "pattern matching". Cela signifie que le compilateur analyse le code pour voir s'il correspond à un certain modèle qu'il est capable de vectoriser. Si c'est le cas, il est vectorisé. S'il ne l'est pas, il ne l'est pas.

Cela semble être un cas particulier où la première boucle ne correspond à aucun des modèles précodés que GCC peut gérer. Mais le second cas correspond au modèle de "réduction vectorisable".

---

Voici la partie pertinente du code source de GCC qui donne ce résultat "not vectorized: live stmt not supported: " message :

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;
    }
}

De juste la ligne :

vectorizable_reduction (stmt, NULL, NULL);

Il est clair que GCC vérifie si cela correspond à un modèle de "réduction vectorisable".

Answer 2

La première boucle est équivalente à

#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];
}

Le problème avec l'expression originale est qu'elle n'a pas vraiment de sens, il n'est donc pas surprenant que gcc ne soit pas capable de la vectoriser.

Answer 3

Le vectoriseur du GCC n'est probablement pas assez intelligent pour vectoriser la première boucle. Le cas de l'addition est plus facile à vectoriser car a + 0 == a . Considérons SIZE==4 :

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

X désigne les combinaisons de i y j cuando a sera affecté à ou augmenté. Pour le cas de l'addition, nous pouvons calculer les résultats de b[i] > c[j] ? b[i] : c[j] pour, disons, j==1 y i==0..4 et le mettre dans le vecteur D . Il ne nous reste plus qu'à mettre à zéro D[2..3] et ajoute le vecteur résultant à a[0..3] . Pour le cas de l'affectation, c'est un peu plus délicat. Nous devons non seulement mettre à zéro D[2..3] mais aussi zéro A[0..1] et seulement ensuite combiner les résultats. Je suppose que c'est là que le vectoriseur échoue.

Answer 4

La première consiste à changer trivialement a[] plusieurs fois (temporaire). La seconde utilise la dernière valeur de a[] à chaque fois (non temporaire).

Jusqu'à une version de patch, vous pouviez utiliser une variable "volatile" pour vectoriser.

Utilisez

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

pour l'aligner ;

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

Montre que "c" a une zone de stockage différente de celle de b et a.

Je suppose que les instructions de type "movaps" sont "vectorisées" (d'après la liste des instructions SSE-AVX).

Ici : http://gcc.gnu.org/projects/tree-ssa/vectorization.html#using

les 6ème et 7ème exemples montrent des difficultés similaires.