Les valeurs booléennes sont 8 bits dans les compilateurs. Les opérations sur eux sont inefficaces?

TL: DR : les compilateurs actuels ont toujours des optimisations manquées lors de l’exécution de tâches telles que
(a&&b) ? x : y (a&&b) ? x : y . Mais la raison n’est pas qu’ils n’assument pas 0/1, ils ne font que sucer.

De nombreuses utilisations de bool sont pour les locaux, ou des fonctions inline, donc la booléenisation à 0/1 peut optimiser la sortie et la twig (ou cmov ou autre) sur la condition d’origine. Ne vous bool optimisation des entrées / sorties bool lorsqu’il doit être transmis / renvoyé sur quelque chose qui n’est pas en ligne ou réellement stocké en mémoire.

Guide d’optimisation possible : combinez des bool s de sources externes (fonction args / mémoire) avec des opérateurs binarys, comme a&b . MSVC et ICC font mieux avec cela. IDK si c’est de pire en pire pour les bool s locaux. Attention, a&b n’est équivalent qu’à a&&b pour les types bool et non des entiers. 2 && 1 est vrai, mais 2 & 1 vaut 0, ce qui est faux. Bitwise OR n’a pas ce problème.

IDK si cette directive risque de nuire aux sections locales définies à partir d’une comparaison au sein de la fonction (ou de quelque chose qui est intégré). Par exemple, cela peut amener le compilateur à créer des booléens entiers au lieu d’utiliser directement les résultats de la comparaison lorsque cela est possible. Notez également que cela ne semble pas aider avec gcc et clang actuels.

---

Oui, les implémentations C ++ sur x86 stockent bool dans un octet qui est toujours égal à 0 ou 1 (au moins à travers les limites des appels de fonctions où le compilateur doit respecter la convention ABI / appelant cela).

Les compilateurs en tirent parfois profit, par exemple pour bool -> int conversion même gcc 4.4 simplement une extension zéro à 32 bits ( movzx eax, dil ). Clang et MSVC le font aussi. Les règles C et C ++ nécessitent que cette conversion produise 0 ou 1, ce comportement est donc sûr uniquement s’il est toujours prudent de supposer qu’une fonction bool arg ou une variable globale a une valeur 0 ou 1.

Même les anciens compilateurs en profitaient généralement pour bool -> int , mais pas dans d’autres cas. Ainsi, Agner a tort sur la raison pour laquelle il dit:

La raison pour laquelle le compilateur ne fait pas une telle hypothèse est que les variables peuvent avoir d’autres valeurs si elles ne sont pas initialisées ou proviennent de sources inconnues.

---

MSVC CL19 rend le code qui suppose que les bool fonction bool sont 0 ou 1, donc l’ABI Windows x86-64 doit le garantir.

Dans l’ ABI System x86-64 (utilisé par tout autre que Windows), le journal des modifications pour la révision 0.98 dit “Spécifiez que _Bool (aka bool ) est booléen à l’appelant.” Je pense que même avant ce changement, les compilateurs le supposaient, mais cela ne fait que documenter ce sur quoi les compilateurs comptaient déjà. La langue actuelle de l’ABI SysV x86-64 est la suivante:

3.1.2 Représentation des données

Les booléens, lorsqu’ils sont stockés dans un object mémoire, sont stockés sous la forme d’objects à un seul octet dont la valeur est toujours 0 (faux) ou 1 (vrai). Lorsqu’elles sont stockées dans des registres entiers (sauf pour passer en argument), tous les 8 octets du registre sont significatifs; toute valeur non nulle est considérée comme vraie.

La deuxième phrase est absurde: l’ABI n’a pas à dire aux compilateurs comment stocker les choses dans des registres à l’intérieur d’une fonction, uniquement aux limites entre les différentes unités de compilation (arguments mémoire / fonction et valeurs de retour). J’ai signalé ce défaut ABI il y a quelque temps sur la page github où il est maintenu .

3.2.3 Passage des parameters :

Lorsqu’une valeur de type _Bool est renvoyée ou transmise dans un registre ou sur la stack, le bit 0 contient la valeur de vérité et les bits 1 à 7 sont zéro ¹⁶ .

(note de bas de page 16): Les autres bits ne sont pas spécifiés, de sorte que le côté consommateur de ces valeurs peut compter sur 0 ou 1 lorsqu’il est tronqué à 8 bits.

La langue utilisée dans l’IBI i386 System V est la même, IIRC.

---

Tout compilateur qui suppose 0/1 pour une chose (par exemple, la conversion en int ) mais qui n’en profite pas dans d’autres cas a une optimisation manquée . Malheureusement, ces optimisations manquées existent toujours, bien qu’elles soient plus rares que lorsque Agner a écrit ce paragraphe sur les compilateurs qui se re-boolent toujours .

(Source + asm sur l’ explorateur de compilateurs Godbolt pour gcc4.6 / 4.7, et clang / MSVC. Voir aussi la discussion CppCon2017 de Matt Godbolt. Qu’est- ce que mon compilateur a fait pour moi récemment?

 bool logical_or(bool a, bool b) { return a||b; } # gcc4.6.4 -O3 for the x86-64 System V ABI test dil, dil # test a against itself (for non-zero) mov eax, 1 cmove eax, esi # return a ? 1 : b; ret 

Donc, même gcc4.6 n’a pas été re-booléen b , mais l’optimisation que gcc4.7 a faite n’a pas été faite:

  # gcc4.7 -O3 to present: looks ideal to me. mov eax, esi or eax, edi ret 

(Clang’s or dil, sil / mov eax, edi est idiot: il est garanti de provoquer un blocage de registre partiel sur Nehalem ou plus tôt Intel lors de la lecture d’ edi après avoir écrit dil , et sa taille de code ne nécessite pas de préfixe REX Un meilleur choix pourrait être or dil,sil / movzx eax, dil si vous voulez éviter de lire des registres 32 bits au cas où votre appelant laisserait des registres d’arguments avec des registres partiels “sales”.

MSVC émet ce code qui vérifie séparément a puis b , omettant complètement de tirer parti de quoi que ce soit , et même en utilisant xor al,al au lieu de xor eax,eax . Donc, il a une fausse dépendance sur l’ancienne valeur de eax sur la plupart des processeurs ( y compris Haswell / Skylake, qui ne renomme pas les registres partiels à faible 8 séparément de l’ensemble du registre, mais seulement AH / BH / … ). C’est juste bête. La seule raison d’utiliser xor al,al est quand vous voulez explicitement conserver les octets supérieurs.

 logical_or PROC ; x86-64 MSVC CL19 test cl, cl ; Windows ABI passes args in ecx, edx jne SHORT $LN3@logical_or test dl, dl jne SHORT $LN3@logical_or xor al, al ; missed peephole: xor eax,eax is ssortingctly better ret 0 $LN3@logical_or: mov al, 1 ret 0 logical_or ENDP 

ICC18 ne tire pas non plus parti de la nature 0/1 connue des entrées, il utilise simplement une instruction or pour définir des indicateurs en fonction de la OU setcc des deux entrées et de la valeur setcc 0/1.

 logical_or(bool, bool): # ICC18 xor eax, eax #4.42 movzx edi, dil #4.33 movzx esi, sil #4.33 or edi, esi #4.42 setne al #4.42 ret #4.42 

ICC émet le même code même pour bool bitwise_or(bool a, bool b) { return a|b; } bool bitwise_or(bool a, bool b) { return a|b; } . Il promeut vers int (avec movzx ), et utilise or pour définir des drapeaux en fonction du OU binary. Ceci est stupide comparé à or dil,sil / setne al .

Pour bitwise_or , bitwise_or utilise simplement une instruction or une instruction (après movzx sur chaque entrée), mais ne re-boole pas de toute façon.

---

Optimisations manquées dans gcc / clang actuel:

Seul ICC / MSVC faisait du code muet avec la fonction simple ci-dessus, mais cette fonction donne toujours des problèmes à gcc et à clang:

 int select(bool a, bool b, int x, int y) { return (a&&b) ? x : y; } 

Source + asm sur l’explorateur du compilateur Godbolt (même source, différents compilateurs sélectionnés par rapport à la dernière fois).

Semble assez simple vous espérez qu’un compilateur intelligent le fasse sans un test / cmov . L’instruction de test de x86 définit les drapeaux en fonction d’un ET binary. C’est une instruction AND qui n’écrit pas réellement la destination. (Tout comme cmp est un sub qui n’écrit pas la destination).

 # hand-written implementation that no comstackrs come close to making select: mov eax, edx # retval = x test edi, esi # ZF = ((a & b) == 0) cmovz eax, ecx # conditional move: return y if ZF is set ret 

Mais même les versions quotidiennes de gcc et de clang sur l’explorateur du compilateur Godbolt rendent le code beaucoup plus compliqué, vérifiant chaque booléen séparément. Ils savent comment optimiser bool ab = a&&b; Si vous retournez ab , mais même si vous écrivez de cette manière (avec une variable booléenne séparée pour contenir le résultat), vous n’arrivez pas à les tenir en main pour créer du code qui ne soit pas nul.

Notez que test same,same est exactement équivalent à cmp reg, 0 , et est plus petit, donc c’est ce que les compilateurs utilisent.

La version de Clang est ssortingctement pire que ma version manuscrite. (Notez que cela nécessite que l’appelant étende à zéro les bool à 32 bits, comme c’est le cas pour les types entiers étroits en tant que partie non officielle de l’ABI implémenté par gcc mais dont seul le clang dépend ).

 select: # clang 6.0 trunk 317877 nightly build on Godbolt test esi, esi cmove edx, ecx # x = b ? y : x test edi, edi cmove edx, ecx # x = a ? y : x mov eax, edx # return x ret 

gcc 8.0.0 20171110 crée tous les soirs du code branché, similaire à ce que font les anciennes versions de gcc.

 select(bool, bool, int, int): # gcc 8.0.0-pre 20171110 test dil, dil mov eax, edx ; compiling with -mtune=intel or -mtune=haswell would keep test/jcc together for macro-fusion. je .L8 test sil, sil je .L8 rep ret .L8: mov eax, ecx ret 

MSVC x86-64 CL19 crée un code branchy très similaire. Il cible la convention d’appel Windows, où les arguments entiers sont en rcx, rdx, r8, r9.

 select PROC test cl, cl ; a je SHORT $LN3@select mov eax, r8d ; retval = x test dl, dl ; b jne SHORT $LN4@select $LN3@select: mov eax, r9d ; retval = y $LN4@select: ret 0 ; 0 means rsp += 0 after popping the return address, not C return 0. ; MSVC doesn't emit the `ret imm16` opcode here, so IDK why they put an explicit 0 as an operand. select ENDP 

ICC18 fait également du code branchy , mais avec les deux instructions mov après les twigs.

 select(bool, bool, int, int): test dil, dil #8.13 je ..B4.4 # Prob 50% #8.13 test sil, sil #8.16 jne ..B4.5 # Prob 50% #8.16 ..B4.4: # Preds ..B4.2 ..B4.1 mov edx, ecx #8.13 ..B4.5: # Preds ..B4.2 ..B4.4 mov eax, edx #8.13 ret #8.13 

---

Essayer d’aider le compilateur en utilisant

 int select2(bool a, bool b, int x, int y) { bool ab = a&&b; return (ab) ? x : y; } 

amène MSVC à créer un code hilarant :

 ;; MSVC CL19 -Ox = full optimization select2 PROC test cl, cl je SHORT $LN3@select2 test dl, dl je SHORT $LN3@select2 mov al, 1 ; ab = 1 test al, al ;; and then test/cmov on an immediate constant!!! cmovne r9d, r8d mov eax, r9d ret 0 $LN3@select2: xor al, al ;; ab = 0 test al, al ;; and then test/cmov on another path with known-constant condition. cmovne r9d, r8d mov eax, r9d ret 0 select2 ENDP 

Ceci est seulement avec MSVC (et ICC18 a la même optimisation manquée de test / cmov sur un registre qui a juste été mis à une constante).

gcc et clang comme d’habitude ne rendent pas le code aussi mauvais que MSVC; ils font la même chose qu’ils font pour select() , qui n’est toujours pas bon, mais au moins en essayant de les aider ne le rend pas pire qu’avec MSVC.

---

Combiner bool avec les opérateurs binarys aide MSVC et ICC

Dans mes tests très limités, | et & semblent fonctionner mieux que || et && pour MSVC et ICC. Regardez le résultat du compilateur pour votre propre code avec vos options de compilation + compilateur pour voir ce qui se passe.

 int select_bitand(bool a, bool b, int x, int y) { return (a&b) ? x : y; } 

Gcc se twig toujours séparément sur des test séparés des deux entrées, même code que les autres versions de select . clang fait toujours deux test/cmov , identiques à ceux des autres versions source.

MSVC intervient et optimise correctement, en battant tous les autres compilateurs (du moins dans la définition autonome):

 select_bitand PROC ;; MSVC test cl, dl ;; ZF = !(a & b) cmovne r9d, r8d mov eax, r9d ;; could have done the mov to eax in parallel with the test, off the critical path, but close enough. ret 0 

ICC18 gaspille deux instructions movzx étendant les bool s en int , mais crée le même code que MSVC

 select_bitand: ## ICC18 movzx edi, dil #16.49 movzx esi, sil #16.49 test edi, esi #17.15 cmovne ecx, edx #17.15 mov eax, ecx #17.15 ret #17.15 

Je pense que ce n’est pas le cas.

Tout d’abord, ce raisonnement est totalement inacceptable:

La raison pour laquelle le compilateur ne fait pas une telle hypothèse est que les variables peuvent avoir d’autres valeurs si elles ne sont pas initialisées ou proviennent de sources inconnues.

Vérifions du code (compilé avec Clang 6, mais GCC 7 et MSVC 2017 produisent un code similaire).

Booléen ou:

 bool fn(bool a, bool b) { return a||b; } 0000000000000000 : 0: 40 08 f7 or dil,sil 3: 40 88 f8 mov al,dil 6: c3 ret 

Comme on peut le voir, pas de contrôle 0/1 ici, simple or .

Convertir bool en int:

 int fn(bool a) { return a; } 0000000000000000 : 0: 40 0f b6 c7 movzx eax,dil 4: c3 ret 

Encore une fois, pas de chèque, simple mouvement.

Convertissez le char en bool:

 bool fn(char a) { return a; } 0000000000000000 : 0: 40 84 ff test dil,dil 3: 0f 95 c0 setne al 6: c3 ret 

Ici, on vérifie si 0 est ou non et que la valeur bool est définie sur 0 ou 1 en conséquence.

Donc, je pense qu’il est prudent de dire que le compilateur utilise bool d’une certaine manière, donc il contient toujours un 0/1. Il ne vérifie jamais sa validité.

A propos de l’efficacité: je pense que bool est optimal. Le seul cas que je puisse imaginer, où cette approche n’est pas optimale, est la conversion en char-> bool. Cette opération pourrait être un simple mov, si la valeur bool ne serait pas limitée à 0/1. Pour toutes les autres opérations, l’approche actuelle est tout aussi bonne ou meilleure.

---

EDIT: Peter Cordes a mentionné ABI. Voici le texte pertinent de l’ABI System V pour AMD64 (le texte pour i386 est similaire):

Les booléens, lorsqu’ils sont stockés dans un object mémoire, sont stockés sous forme d’objects à un seul octet dont la valeur est toujours 0 (faux) ou 1 (vrai) . Lorsqu’elles sont stockées dans des registres entiers (sauf pour passer en argument), tous les 8 octets du registre sont significatifs; toute valeur non nulle est considérée comme vraie

Donc, pour les plates-formes qui suivent SysV ABI, nous pouvons être sûrs qu’un bool a une valeur de 0/1.

J’ai cherché un document ABI pour MSVC, mais malheureusement je n’ai rien trouvé à propos de bool .

J’ai compilé ce qui suit avec clang ++ -O3 -S

 bool andbool(bool a, bool b) { return a && b; } bool andint(int a, int b) { return a && b; } 

Le fichier .s contient:

 andbool(bool, bool): # @andbool(bool, bool) andb %sil, %dil movl %edi, %eax retq andint(int, int): # @andint(int, int) testl %edi, %edi setne %cl testl %esi, %esi setne %al andb %cl, %al retq 

Clairement, c’est la version bool qui fait moins.