Auto-vectorization

Version imprimable

Auto-vectorization

Bonjour,

j'ai ce simple morceau de code pour calculer le maximum entre deux tableaux et placer le résultat dans un troisième :
Code:

1 2 3 4 5 6 template<class T> inline void Maximum(const T *array1, const T *array2, const size_t size, T *result) { for (size_t i=0 ; i < size ; i++) result[i] = array1[i] > array2[i] ? array1[i] : array2[i] ; }
Ce code fonctionne très bien, mais je souhaitais qu'il soit auto-vectorisé et il ne l'est pas.
Comment faire ?
J'avoue que ça me dépasse et je souhaiterai comprendre svp :-)

[EDIT]
Lorsque j'utilise le flag "-fopt-info-vec-missed", j'ai le message suivant disant que la boucle n'est pas auto-vectorisée, avec "ArrayMM.h:19:2:" faisant référence aux deux lignes en question :

Citation:

ArrayMM.h:19:2: note: versioning for alias required: can't determine dependence between *_31 and *_30
ArrayMM.h:19:2: note: versioning for alias required: can't determine dependence between *_33 and *_30
ArrayMM.h:19:2: note: Unknown misalignment, is_packed = 0
ArrayMM.h:19:2: note: Unknown misalignment, is_packed = 0
ArrayMM.h:19:2: note: Unknown misalignment, is_packed = 0
ArrayMM.h:19:2: note: virtual phi. skip.
ArrayMM.h:19:2: note: not ssa-name.
ArrayMM.h:19:2: note: use not simple.
ArrayMM.h:19:2: note: not ssa-name.
ArrayMM.h:19:2: note: use not simple.
ArrayMM.h:19:2: note: not ssa-name.
ArrayMM.h:19:2: note: use not simple.
ArrayMM.h:19:2: note: not ssa-name.
ArrayMM.h:19:2: note: use not simple.
ArrayMM.h:19:2: note: virtual phi. skip.
ArrayMM.h:19:2: note: virtual phi. skip.
...
ArrayMM.h:20:9: note: not consecutive access _160 = *_159;

ArrayMM.h:20:9: note: not consecutive access _162 = *_161;

ArrayMM.h:20:9: note: not consecutive access *_158 = iftmp.2_163;

ArrayMM.h:20:9: note: Failed to SLP the basic block.
ArrayMM.h:20:9: note: not vectorized: failed to find SLP opportunities in basic block.
ArrayMM.h:20:9: note: not consecutive access _173 = *_172;

ArrayMM.h:20:9: note: not consecutive access _175 = *_174;

ArrayMM.h:20:9: note: not consecutive access *_171 = iftmp.2_176;

ArrayMM.h:20:9: note: Failed to SLP the basic block.
ArrayMM.h:20:9: note: not vectorized: failed to find SLP opportunities in basic block.
ArrayMM.h:20:9: note: not consecutive access _88 = *_87;

ArrayMM.h:20:9: note: not consecutive access _90 = *_89;

ArrayMM.h:20:9: note: not consecutive access *_86 = iftmp.2_91;

ArrayMM.h:20:9: note: Failed to SLP the basic block.
ArrayMM.h:20:9: note: not vectorized: failed to find SLP opportunities in basic block.
...
ArrayMM.h:20:21: note: not vectorized: no vectype for stmt: vect__32.38_132 = MEM[(int *)vectp.36_130];
scalar_type: vector(4) int
ArrayMM.h:20:21: note: not vectorized: not enough data-refs in basic block.
ArrayMM.h:20:9: note: not consecutive access _112 = *_111;

ArrayMM.h:20:9: note: not consecutive access _114 = *_113;

ArrayMM.h:20:9: note: not consecutive access *_110 = iftmp.2_115;

ArrayMM.h:20:9: note: Failed to SLP the basic block.
ArrayMM.h:20:9: note: not vectorized: failed to find SLP opportunities in basic block.
arrayTiTi_ArrayMM.cpp:20:24: note: not vectorized: not enough data-refs in basic block.
ArrayMM.h:20:9: note: not consecutive access _74 = *_99;

ArrayMM.h:20:9: note: not consecutive access _30 = *_29;

ArrayMM.h:20:9: note: not consecutive access *_51 = iftmp.2_31;

ArrayMM.h:20:9: note: Failed to SLP the basic block.
ArrayMM.h:20:9: note: not vectorized: failed to find SLP opportunities in basic block.
ArrayMM.h:20:9: note: not consecutive access _148 = *_147;

ArrayMM.h:20:9: note: not consecutive access _150 = *_149;

ArrayMM.h:20:9: note: not consecutive access *_146 = iftmp.2_151;

ArrayMM.h:20:9: note: Failed to SLP the basic block.
ArrayMM.h:20:9: note: not vectorized: failed to find SLP opportunities in basic block.
...
ArrayMM.h:20:9: note: SLP: step doesn't divide the vector-size.
ArrayMM.h:20:9: note: Unknown alignment for access: *_67
ArrayMM.h:20:9: note: SLP: step doesn't divide the vector-size.
ArrayMM.h:20:9: note: Unknown alignment for access: *_69
ArrayMM.h:20:9: note: SLP: step doesn't divide the vector-size.
ArrayMM.h:20:9: note: Unknown alignment for access: *_66
ArrayMM.h:20:9: note: Failed to SLP the basic block.
ArrayMM.h:20:9: note: not vectorized: failed to find SLP opportunities in basic block.

En revanche lorsque j'utilise le flag "-fopt-info-vec", j'ai alors :

Citation:

ArrayMM.h:19:2: note: loop vectorized
ArrayMM.h:19:2: note: loop versioned for vectorization because of possible aliasing
ArrayMM.h:19:2: note: loop peeled for vectorization to enhance alignment

Qui semblerait dire que la boucle a été vectorisée...

Hello,

Citation:

Envoyé par ToTo13

Qui semblerait dire que la boucle a été vectorisée...

Et à quoi ressemble le binaire généré ?

Tu as peut être 1 version vectorisée et une autre non.

Code:

1
2
Maximum<float>(); // vectorisée
Maximum<double>(); // non vectorisée à cause de problèmes d'aliasing / trop peu d'itérations ou autre.

Après un rapide test avec MSVC 2015, c'est vectorisé correctement et la boucle à été en partie unroll chez moi (16 itérations, 2 x 256 bits / itération pour 256 floats).

Code:

1
2
3
4
5
6
7
int main(int argc, char **argv) {
	float arr0[256], arr1[256], res[256];
	Maximum(arr0, arr1, 256, res);
	std::cout << res[42];
 
	return 0;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
template<class T> inline void Maximum(const T *array1, const T *array2, const size_t size, T *result) {
01301060  push        ebp  
01301061  mov         ebp,esp  
01301063  push        ecx  
01301064  push        ebx  
01301065  push        esi  
	for (size_t i = 0; i < size; i++)
01301066  mov         esi,dword ptr [result]  
01301069  lea         eax,[edx+20h]  
0130106C  push        edi  
0130106D  mov         edi,ecx  
0130106F  mov         ecx,esi  
01301071  sub         ecx,edx  
01301073  mov         ebx,edi  
01301075  mov         dword ptr [ebp-4],ecx  
01301078  sub         ebx,edx  
0130107A  mov         edx,dword ptr [ebp-4]  
0130107D  sub         edi,esi  
0130107F  mov         ecx,10h // 16 itérations
01301084  lea         esi,[esi+40h]  
01301087  lea         eax,[eax+40h]  
0130108A  vmovups     ymm0,ymmword ptr [edi+esi-40h]  
01301090  vmaxps      ymm0,ymm0,ymmword ptr [eax-60h]  
		result[i] = array1[i] > array2[i] ? array1[i] : array2[i];
01301095  vmovups     ymmword ptr [esi-40h],ymm0  
0130109A  vmovups     ymm0,ymmword ptr [ebx+eax-40h]  
013010A0  vmaxps      ymm0,ymm0,ymmword ptr [eax-40h]  
013010A5  vmovups     ymmword ptr [edx+eax-40h],ymm0  
013010AB  sub         ecx,1  
013010AE  jne         Maximum<float>+24h (01301084h)  
013010B0  pop         edi  
013010B1  pop         esi  
013010B2  pop         ebx  
013010B3  vzeroupper  
}
013010B6  mov         esp,ebp  
013010B8  pop         ebp  
013010B9  ret

Merci pour ta réponse !

Citation:

Envoyé par Iradrille

Et à quoi ressemble le binaire généré ?

Je ne lis pas le binaire :-(
Citation:
Envoyé par Iradrille
Tu as peut être 1 version vectorisée et une autre non.
Code:

1 2 Maximum<float>(); // vectorisée Maximum<double>(); // non vectorisée à cause de problèmes d'aliasing / trop peu d'itérations ou autre.
Ok, peut être.
En fait, j'ai quelque chose du style:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 template<class T> inline void Maximum(const T *array1, const T *array2, const size_t size, T *result) { for (size_t i=0 ; i < size ; i++) result[i] = array1[i] > array2[i] ? array1[i] : array2[i] ; } #ifdef __SSE2__ template<> inline void Maximum<UINT8>(const UINT8 *array1, const UINT8 *array2, const size_t size, UINT8 *result) { // Même chose avec SSE2 fonctions } // Idem avec UINT16 #endif
Citation:

Envoyé par Iradrille

Après un rapide test avec MSVC 2015, c'est vectorisé correctement et la boucle à été en partie unroll chez moi (16 itérations, 2 x 256 bits / itération pour 256 floats).

Cela ne devrait pas arriver dans mon cas car je travaille sur des images, donc des tableaux au minium 512x512.

27/08/2015, 10h52
Iradrille
Citation:

Envoyé par ToTo13

Je ne lis pas le binaire :-(

C'est pourtant le seul moyen de savoir ce qui se passe vraiment. :)

Pour que GCC te génère le code assembleur : http://www.delorie.com/djgpp/v2faq/faq8_20.html
Après avec quelques recherches dedans tu devrais trouver le code de ta (tes) fonction(s) Maximum.

Une autre méthode (bien moins fiable) est de forcer la désactivation de la vectorisation et de comparer les temps d’exécutions.

Sinon, tu n'as pas de problèmes d'aliasing ?
Code:

1 2 float arr0[257], arr1[256]; Maximum(arr0, arr1, 256, arr0 +1); // le tableau résultat chevauche un des deux autres
Ou alors des tableaux dont la taille n'est pas un multiple de 16 octets ?
Ou des petits tableaux ? Il suffit d'un appel à Maximum avec un tableau trop petit pour que tu ai un warning (reste à savoir si tous les autres appels sont vectorisés ou pas).
27/08/2015, 10h58
ToTo13
Citation:

Envoyé par Iradrille

C'est pourtant le seul moyen de savoir ce qui se passe vraiment. :)

Pour que GCC te génère le code assembleur : http://www.delorie.com/djgpp/v2faq/faq8_20.html
Après avec quelques recherches dedans tu devrais trouver le code de ta (tes) fonction(s) Maximum.

:weird: fait ***** :aie:
Citation:
Envoyé par Iradrille

Sinon, tu n'as pas de problèmes d'aliasing ?

Code:

1 2 float arr0[257], arr1[256]; Maximum(arr0, arr1, 256, arr0 +1); // le tableau résultat chevauche un des deux autres

Ou alors des tableaux dont la taille n'est pas un multiple de 16 octets ?
Ou des petits tableaux ? Il suffit d'un appel à Maximum avec un tableau trop petit pour que tu ai un warning (reste à savoir si tous les autres appels sont vectorisés ou pas).
Le compilateur n'en a ABSOLUMENT aucune idée au moment de la compilation.
Ces codes seront appelés sur des images, donc tant que l'image n'a pas été lu...
Citation:
Envoyé par Iradrille

Sinon, tu n'as pas de problèmes d'aliasing ?

Code:

1 2 float arr0[257], arr1[256]; Maximum(arr0, arr1, 256, arr0 +1); // le tableau résultat chevauche un des deux autres
J'aimerai dans un futur TRES proche faire ce genre de choses... mais comment ?
Je comprends d'après ce que tu dis que l'auto-vectorisation ne marchera jamais dans ce cas, donc il me reste le SSE2.
D'ailleurs, est ce qu'il y a eu des tests de fait au niveau écart de performances entre code auto-vectorisé et code appelant du SSE2 ? (code réalisant la même opération bien entendu).
28/08/2015, 09h41
Iradrille

Citation:

Envoyé par ToTo13

Le compilateur n'en a ABSOLUMENT aucune idée au moment de la compilation.
Ces codes seront appelés sur des images, donc tant que l'image n'a pas été lu...

Si le compilo n'en sait pas assez il ne prendra pas le "risque" de vectoriser le code : vaut mieux du code qui marche lentement que du code qui ne marche pas rapidement.

Faut réussir à identifier les cas où le code à été vectorisé et les cas où ça n'a pas été fait et comprendre pourquoi : fouiller dans le binaire et comprendre ces messages un peu cryptiques du compilo.

Citation:

Envoyé par ToTo13

J'aimerai dans un futur TRES proche faire ce genre de choses... mais comment ?

C'est au cas par cas :
un petit décalage entre les tableaux (< 128 bits) -> il te faudra soit un algo différent soit ça sera impossible (ou possible mais trop lent).
un "grand" décalage (>= 128 bits) -> le compilo risque de ne pas vectoriser ça s'il le détecte, ça ne devrait pas poser problème au niveau des calculs, mais faut voir comment ça se comporte niveau temps d’exécution.

Citation:

Envoyé par ToTo13

Je comprends d'après ce que tu dis que l'auto-vectorisation ne marchera jamais dans ce cas, donc il me reste le SSE2.
D'ailleurs, est ce qu'il y a eu des tests de fait au niveau écart de performances entre code auto-vectorisé et code appelant du SSE2 ? (code réalisant la même opération bien entendu).

C'est strictement équivalent.

Tu dis à ton compilo quels jeux d'instructions il peut utiliser (SSE / AVX / etc...) et il les utilises. Que ce soit fait à la main ou automatiquement ne change rien.
Tu pourras éventuellement optimiser le code plus agressivement à la main, mais à moins d'avoir détecté quelle partie du code pose un problème de performance (via profiling) c'est inutile.
28/08/2015, 09h43
ToTo13

merci...
28/08/2015, 11h06
Arzar

Si tu sais que les tableaux ne se chevauchent pas ça vaudrait le coup d'essayer d'ajouter des restrict et voir ce que ça donne, comme l'a dit Iradrille assez souvent les compilos renoncent à optimiser à cause des problèmes d'aliasing.

La syntaxe dépends du compilo, ça ressemble un peu à ça :

Code:

template<class T> inline void Maximum(const T * restrict array1, const T * restrict array2, const size_t size, T * restrict result)
28/08/2015, 11h14
ToTo13

Effectivement, mais le tableau résultat peut être un des deux premiers tableaux, du genre : Maximum(Array1, Array1, length, Array1).