GCC compile mal le nombre de zéro menant à moins que Haswell ne l'ait spécifié

Question

GCC prend en charge le code interne __builtin_clz(int x), qui compte le nombre de premiers zéros (zéros consécutifs les plus significatifs) dans l'argument.

entre autres , ce qui est grand pour mettre en œuvre efficacement la fonction lg(unsigned int x), qui prend la base 2 logarithme de x, arrondi vers le bas :

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

Cela fonctionne de la manière simple - En particulier, considérons le cas x == 1 et clz(x) == 31 - puis x == 2^0 donc lg(x) == 0 et 31 - 31 == 0 et nous obtenons le bon résultat. Des valeurs plus élevées de x fonctionnent de manière similaire.

En supposant que la version intégrée est implémentée de manière efficace, ceci se termine beaucoup mieux que l'alternative pure C solutions.

Maintenant, en fait, l'opération compte les zéros est essentiellement le dual de l'instruction bsr en x86. Cela renvoie l'indice du bit 112 le plus significatif dans l'argument. Donc s'il y a 10 zéros en tête, le premier 1 bit est dans le bit 21 de l'argument. En général, nous avons 31 - clz(x) == bsr(x) et ainsi bsr en fait directement implémente notre fonction désirée lg(), sans le superflu 31U - ... partie.

En fait, vous pouvez lire entre la ligne et de voir que la fonction __builtin_clz a été mis en œuvre avec bsr à l'esprit: il est défini comme un comportement non défini si l'argument est nul, quand bien sûr l'opération « menant des zéros » est parfaitement bien défini comme 32 (ou quelle que soit la taille de bit de int est) avec un argument nul. Donc, __builtin_clz a certainement été implémenté avec l'idée d'être efficacement mappé à une instruction bsr sur x86.

Cependant, en regardant ce que GCC ne fait, à -O3 avec des options autrement par défaut: il adds a ton of extra junk:

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 bits inférieurs qui en fait la matière, qui est hors de -un de neg edi qui transforme le résultat de bsr en clz. Ensuite, le 31 - clz(x) est effectué.

Cependant, avec -mtune=haswell, le code simplifies dans exactement la seule instruction bsr attendue:

lg(unsigned int): 
     bsr  eax, edi 
     ret 

Pourquoi est-ce que le cas est très clair pour moi. L'instruction bsr a été autour pendant quelques décennies avant Haswell, et le comportement est, AFAIK, inchangé.Ce n'est pas seulement un problème de de réglage pour un arc particulier, puisque bsr + un tas d'instructions supplémentaires ne va pas être plus rapide qu'un bsr ordinaire et en outre en utilisant still results dans le code le plus lent.

La situation des 64 bits entrées et sorties est even slightly worse: il y a une movsx supplémentaire dans le chemin critique qui semble ne rien faire puisque le résultat de clz ne sera jamais négatif. Encore une fois, la variante -march=haswell est optimale avec une seule instruction bsr.

Enfin, vérifions les acteurs principaux dans l'espace du compilateur non-Windows, icc and clang. icc fait juste un mauvais travail et ajoute des choses redondantes comme neg eax; add eax, 31; neg eax; add eax, 31; - wtf? clang fait du bon travail indépendamment de -march.

---

Tels que le balayage d'une image bitmap pour le premier bit de consigne.

Le logarithme de 0 est undefinited, et ainsi appeler notre fonction avec un argument 0 est un comportement non défini.

Ici, le LSB est le 0ème bit et le MSB est le 31ème. Rappelons que -x == ~x + 1 en deux-complément.

Answer 1

Cela ressemble à un problème connu avec gcc: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50168