GCC comstack mal le zéro devant sauf si spécifié par Haswell

GCC prend en charge la commande __builtin_clz(int x) , qui compte le nombre de zéros non significatifs ( zéros consécutifs les plus significatifs) dans l’argument.

Entre autres choses, ⁰ est idéal pour implémenter efficacement la fonction lg(unsigned int x) , qui prend le logarithme en base 2 de x , arrondissant à ¹ :

 /** return the base-2 log of x, where x > 0 */ unsigned lg(unsigned x) { return 31U - (unsigned)__builtin_clz(x); } 

Cela fonctionne de manière simple – considérons en particulier le cas x == 1 et clz(x) == 31 – alors x == 2^0 donc lg(x) == 0 et 31 - 31 == 0 et nous obtenons le résultat correct. Les valeurs plus élevées de x fonctionnent de la même manière.

En supposant que la fonction intégrée soit efficacement mise en œuvre, cela se termine bien mieux que les solutions alternatives en C pur .

• Est-il préférable de classer le pointeur renvoyé par malloc?
• strncpy ou strlcpy dans mon cas
• Puis-je libérer () des variables statiques et automatiques en C?
• cvCreateCameraCapture renvoie la valeur null
• Comment utiliser int16_t ou int32_t avec des fonctions comme scanf

En l’ bsr , le décompte des zéros est essentiellement le double de l’instruction bsr en x86. Cela retourne l’index du bit le plus significatif ² dans l’argument. Donc, s’il y a 10 zéros en tête, le premier bit est dans le bit 21 de l’argument. En général, nous avons 31 - clz(x) == bsr(x) et donc bsr implémente directement notre fonction lg() souhaitée, sans la partie superflue 31U - ...

En fait, vous pouvez lire entre les lignes et constater que la fonction __builtin_clz été implémentée avec bsr à l’esprit: il est défini comme un comportement indéfini si l’argument est égal à zéro, alors que l’opération “zéros au début” est parfaitement définie comme 32 (ou quelle que soit la taille de bit de int est) avec un argument zéro. Donc, __builtin_clz a certainement été implémenté avec l’idée d’être mappé efficacement à une instruction bsr sur x86.

Cependant, en regardant ce que fait GCC, à -O3 avec d’autres options par défaut: cela ajoute une tonne de bric -à- brac :

 lg(unsigned int): bsr edi, edi mov eax, 31 xor edi, 31 sub eax, edi ret 

La ligne xor edi,31 est effectivement un not edi pour les 4 derniers bits qui importent, c’est-à-dire ³ par neg edi qui transforme le résultat de bsr en clz . Ensuite, le 31 - clz(x) est effectué.

Cependant, avec -mtune=haswell , le code simplifie exactement l’instruction unique attendue de bsr :

 lg(unsigned int): bsr eax, edi ret 

Pourquoi est-ce le cas est très peu clair pour moi. L’instruction bsr existe depuis une vingtaine d’années avant Haswell, et le comportement est, autant que je sache, inchangé. Ce n’est pas juste un problème de réglage pour une arche particulière, car bsr + un paquet d’instructions supplémentaires ne sera pas plus rapide qu’un bsr simple et en outre, l’utilisation de -mtune=haswell entraîne toujours le code plus lent.

La situation pour les entrées et les sorties 64 bits est même légèrement pire : il y a un movsx supplémentaire dans le chemin critique qui semble ne rien faire car le résultat de clz ne sera jamais négatif. De nouveau, la variante -march=haswell est optimale avec une seule instruction bsr .

Enfin, vérifions clang les principaux acteurs dans l’espace compilateur non-Windows, icc et clang . icc ne fait que du mauvais travail et ajoute des éléments redondants comme neg eax; add eax, 31; neg eax; add eax, 31; neg eax; add eax, 31; neg eax; add eax, 31; – wtf? clang fait du bon travail, indépendamment du -march .

---

^{0 Par} exemple, numériser une image bitmap pour le premier bit défini.

¹ Le logarithme de 0 étant indéfini, appeler notre fonction avec un argument de 0 équivaut à un comportement indéfini .

² Ici, le bit de poids faible est le 0ème bit et le bit de poids fort est le 31ème.

³ Rappelez-vous que -x == ~x + 1 en complément de deux.

• Pourquoi ne puis-je pas utiliser ce code pour écraser une chaîne?
• Ecriture de firmware: assemblage ou haut niveau?
• Caractère non imprimable après la génération d’une chaîne base64 aléatoire sur n octets
• Comparaison des variables float et double
• Comment prouver que les énoncés C -x, ~ x + 1 et ~ (x-1) donnent les mêmes résultats?